深圳网站建设工作室,ktv网站模板,中英文网站模板源码,做网站用的云控制台1 概述
std::unordered_multimap 是一个哈希表实现的无序容器#xff0c;它存储的元素是键值对#xff0c;并且允许键的重复。这意味着同一个键可以关联多个值。在 std::unordered_multimap 中#xff0c;元素的插入顺序是不确定的#xff0c;并且不会因为元素的插入、删除…1 概述
std::unordered_multimap 是一个哈希表实现的无序容器它存储的元素是键值对并且允许键的重复。这意味着同一个键可以关联多个值。在 std::unordered_multimap 中元素的插入顺序是不确定的并且不会因为元素的插入、删除或查找而改变。
std::unordered_multimap 与 std::multimap 的主要区别如下
std::multimap 也是一个关联容器它存储的元素也是键值对并且同样允许键的重复。但是std::multimap 的内部实现是基于红黑树这种有序数据结构因此它存储的元素是按键的升序或降序取决于比较函数的定义排列的。而 std::unordered_multimap 则不保证元素的任何顺序它主要关注的是高效的查找、插入和删除操作。在性能上std::unordered_multimap 的查找、插入和删除操作的时间复杂度通常接近 O(1)这是因为它使用了哈希表这种数据结构。而 std::multimap 的这些操作的时间复杂度则是 O(log n)因为它基于红黑树实现。因此当对性能有较高要求且不需要元素有序时std::unordered_multimap 可能会是一个更好的选择。
std::unordered_multimap 的实现基于哈希表。哈希表是一种数据结构它使用哈希函数将键映射到数组的索引从而可以在常数时间内找到键对应的值。在 std::unordered_multimap 中由于允许键的重复所以每个哈希表槽位可能对应一个链表或其他动态数组结构用于存储具有相同哈希值的键值对。
当插入一个元素时首先计算键的哈希值然后使用该哈希值找到数组中的对应槽位。如果槽位为空则直接在该槽位插入新的键值对。如果槽位已有元素则将新的键值对添加到对应的链表或动态数组中。
查找和删除操作也类似首先计算键的哈希值找到对应的槽位然后在槽位对应的链表或动态数组中查找或删除指定的键值对。
需要注意的是哈希表的性能在很大程度上取决于哈希函数的质量。一个好的哈希函数应该能够将键均匀地映射到数组的各个槽位以减少哈希冲突的发生。
2 声明与初始化
2.1 声明
首先需要包含 unordered_map 头文件然后声明一个 std::unordered_multimap 变量并指定键和值的类型。
#include unordered_map std::unordered_multimapKeyType, ValueType mapName;其中 KeyType 是键的类型ValueType 是值的类型mapName 是你为该 unordered_multimap 变量选择的名称。
2.2 初始化
初始化 std::unordered_multimap 可以通过多种方式进行包括默认初始化、使用列表初始化器初始化、复制初始化、移动初始化等。
1默认初始化
如果没有提供任何初始化器std::unordered_multimap 将被默认初始化这意味着它将不包含任何元素并且会使用默认的哈希函数和键相等性比较对象。
std::unordered_multimapstd::string, int myMultimap; // 默认初始化2使用列表初始化器初始化
可以使用列表初始化器大括号 {}来初始化 std::unordered_multimap并直接添加一些元素。
std::unordered_multimapstd::string, int myMultimap { {apple, 1}, {banana, 2}, {apple, 3} // 注意允许相同的键
};在这个例子中myMultimap 初始时包含三个元素其中有两个元素具有相同的键 “apple”。
3注意事项
std::unordered_multimap 不保证元素的顺序因此不应该依赖特定的插入顺序。插入到 std::unordered_multimap 中的键可以重复。如果键类型没有提供默认的哈希函数和相等性比较对象则需要提供自定义的实现后面会详细讲解。
3 插入元素
3.1 插入方法
1使用 insert 成员函数
std::unordered_multimap 提供了一个 insert 成员函数用于向容器中插入元素。该函数接受一个键值对并将其添加到容器中。如果容器中已经存在具有相同键的元素insert 函数仍然会插入新的键值对因为 std::unordered_multimap 允许键的重复。
插入单个键值对
可以使用 insert 函数插入单个键值对。这通常通过创建一个 std::pair 对象来实现其中第一个元素是键第二个元素是值。
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap; // 插入单个键值对 myMultimap.insert(std::make_pair(apple, 10)); // 也可以直接使用花括号初始化列表来构造 pair 对象 myMultimap.insert({banana, 20}); return 0;
}这个例子创建了一个 std::unordered_multimap 对象 myMultimap并使用 insert 函数插入了两个键值对。第一个键值对是 (“apple”, 10)第二个键值对是 (“banana”, 20)。
插入多个键值对
也可以使用初始化列表一次性插入多个键值对。
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap; // 插入多个键值对 myMultimap.insert({ {apple, 10}, {banana, 20}, {orange, 30} }); return 0;
}在这个例子中使用初始化列表一次性插入了三个键值对。
2使用迭代器插入
insert 函数还有一个重载版本它接受一个迭代器和一个键值对尝试在迭代器指向的位置插入元素。如果插入成功函数返回一个指向新插入元素的迭代器如果插入失败例如由于内存不足则返回一个指向容器中下一个有效位置的迭代器。
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap; // 插入一个键值对并获取指向它的迭代器 auto it myMultimap.insert(myMultimap.begin(), std::make_pair(apple, 10)); return 0;
}这个例子使用 insert 函数的迭代器版本在容器的开始位置尝试插入一个键值对。返回的迭代器 it 指向新插入的元素。
3使用 emplace 成员函数
除了 insert 函数外std::unordered_multimap 还提供了 emplace 成员函数它可以在容器内直接构造元素避免了不必要的复制或移动操作。这对于大型对象或那些复制/移动成本较高的对象特别有用。
#include unordered_map
#include string struct LargeObject { std::string data; // ... 其他成员和数据 ... LargeObject(const std::string d) : data(d) { // 构造函数实现 }
}; int main()
{ std::unordered_multimapstd::string, LargeObject myMultimap; // 使用 emplace 插入元素直接在容器内构造 LargeObject 对象 myMultimap.emplace(key, large data); return 0;
}这个例子定义了一个名为 LargeObject 的结构它有一个接受 std::string 的构造函数。我们使用 emplace 函数直接向 myMultimap 中插入一个 LargeObject 对象避免了先构造对象再复制的额外开销。
3.2 注意事项
插入操作的时间复杂度在平均情况下是 O(1)但由于哈希冲突的存在最坏情况下的时间复杂度可能较高。因此为了获得最佳性能应确保键的哈希函数分布均匀并尽量减少哈希冲突。插入操作可能会导致容器的重新哈希rehashing这是一个相对昂贵的操作因为它涉及到重新分配内存和重新计算所有元素的哈希值。
4 访问元素
4.1 使用迭代器遍历元素
由于 std::unordered_multimap 是一种容器因此可以使用迭代器来遍历并访问其中的元素。迭代器类似于指针可以用来访问容器中的元素。
1遍历所有元素
可以使用 begin() 和 end() 成员函数来获取指向容器第一个元素和最后一个元素之后位置的迭代器然后使用这些迭代器遍历容器中的所有元素。
#include iostream
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40} }; // 使用迭代器遍历所有元素 for (auto it myMultimap.begin(); it ! myMultimap.end(); it) { std::cout it-first : it-second std::endl; } return 0;
}这个例子创建了一个 std::unordered_multimap 对象 myMultimap并使用 begin() 和 end() 获取迭代器来遍历容器中的所有元素。it-first 访问键it-second 访问值。
2遍历具有特定键的所有元素
由于 std::unordered_multimap 允许键的重复可能需要遍历具有特定键的所有元素。这可以通过结合 equal_range 函数和迭代器来实现。
#include iostream
#include unordered_map
#include string int main() { std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40} }; // 查找键为 apple 的所有元素 auto range myMultimap.equal_range(apple); for (auto it range.first; it ! range.second; it) { std::cout it-second std::endl; // 输出值 } return 0;
}上面代码的输出为
10
30在这个例子中equal_range 返回一个包含两个迭代器的 pair第一个迭代器指向第一个键为 “apple” 的元素第二个迭代器指向第一个键不为 “apple” 的元素。通过遍历这个范围来访问所有键为 “apple” 的元素。
4.2 使用 find 函数查找元素
如果只需要查找具有特定键的第一个元素可以使用 find 函数。如果找到了匹配的元素find 会返回一个指向该元素的迭代器如果没有找到则返回 end() 迭代器。
#include iostream
#include unordered_map
#include string int main() { std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40} }; // 查找键为 apple 的第一个元素 auto it myMultimap.find(apple); if (it ! myMultimap.end()) { std::cout Found apple with value: it-second std::endl; } else { std::cout Apple not found. std::endl; } return 0;
}这个例子使用 find 函数来查找键为 “apple” 的第一个元素。如果找到了就输出它的值否则输出 “Apple not found.”。
5 删除元素
5.1 使用 erase 成员函数删除单个元素
erase 成员函数可以用于删除容器中的单个元素。可以通过传递一个指向要删除元素的迭代器来调用它。
#include iostream
#include unordered_map
#include string int main() { std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40} }; // 假设我们有一个指向要删除元素的迭代器 auto it myMultimap.find(apple); // 查找键为 apple 的一个元素 if (it ! myMultimap.end()) { // 使用 erase 删除找到的元素 myMultimap.erase(it); } // 输出容器内容以验证元素已被删除 for (const auto pair : myMultimap) { std::cout pair.first : pair.second std::endl; } return 0;
}上面代码的输出为
apple: 30
banana: 20
orange: 40在这个例子中首先使用 find 函数找到一个键为 “apple” 的元素的迭代器。然后检查找到的迭代器是否不等于 end()以确保找到了有效的元素。最后调用 erase 并传入迭代器来删除该元素。
5.2 使用 erase 成员函数删除删除一系列元素
erase 成员函数还有一个重载版本它接受两个迭代器作为参数用于删除一个范围内的所有元素。这在你想要删除具有特定键的所有元素时非常有用。
#include iostream
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40} }; // 查找键为 apple 的元素范围 auto range myMultimap.equal_range(apple); // 删除范围内的所有元素 myMultimap.erase(range.first, range.second); // 输出容器内容以验证元素已被删除 for (const auto pair : myMultimap) { std::cout pair.first : pair.second std::endl; } return 0;
}上面代码的输出为
banana: 20
orange: 40这个例子使用 equal_range 函数来获取一个包含所有键为 “apple” 的元素的范围。然后调用 erase 并传入这个范围的开始和结束迭代器来删除所有这些元素。
5.3 使用 clear 成员函数删除所有元素
如果想要删除 std::unordered_multimap 中的所有元素可以使用 clear 成员函数。这将移除容器中的所有键值对并将容器的大小变为 0。
std::unordered_multimapint, std::string myMap;
// 假设 myMap 中已经填充了一些元素 myMap.clear(); // 删除所有元素myMap 现在为空5.4 遍历删除
在 std::unordered_multimap 中遍历并删除元素时需要特别小心因为删除操作会使指向已删除元素的迭代器失效。如果试图使用一个已经失效的迭代器程序可能会崩溃或产生不可预测的行为。
一种常见的策略是使用迭代器从 begin() 到 end() 遍历容器并在遍历过程中删除满足特定条件的元素。但是由于直接删除当前迭代器指向的元素会使迭代器失效需要在删除前获取下一个迭代器的位置。这可以通过递增当前迭代器来完成然后在递增之前检查它是否指向要删除的元素。
以下是一个示例展示如何在遍历 std::unordered_multimap 时删除所有键为 “apple” 的元素
#include iostream
#include unordered_map
#include string int main()
{ std::unordered_multimapstd::string, int myMultimap { {apple, 10}, {banana, 20}, {apple, 30}, {orange, 40}, {apple, 50} }; // 使用迭代器遍历并删除键为 apple 的所有元素 for (auto it myMultimap.begin(); it ! myMultimap.end(); ) { if (it-first apple) { // 删除元素并使迭代器指向下一个有效元素 it myMultimap.erase(it); } else { // 如果不删除则递增迭代器 it; } } // 输出容器内容以验证元素已被删除 for (const auto pair : myMultimap) { std::cout pair.first : pair.second std::endl; } return 0;
}上面代码的输出为
banana: 20
orange: 40这个例子使用了一个 for 循环来遍历 myMultimap。在循环内部首先检查当前迭代器的键是否为 “apple”。如果是则调用 erase 来删除该元素并更新迭代器 it 为 erase 返回的下一个有效迭代器。如果不删除当前元素就递增迭代器以继续遍历。
注意erase 成员函数返回指向被删除元素之后的那个元素的迭代器。如果 erase 被调用在最后一个元素上它将返回 end()。这就是为什么循环条件仍然是 it ! myMultimap.end()因为即使删除了当前元素it 在更新后仍然可能不是 end()。
这种遍历并删除元素的方法在大多数情况下都是安全的因为它避免了使用已经失效的迭代器。然而如果容器在遍历过程中被其他线程修改那么可能会出现数据竞争。在多线程环境中应确保适当的同步机制来避免这种情况。
6 使用自定义键类型
std::unordered_multimap 也可以使用自定义键类型。当使用自定义键类型时需要为该类型定义哈希函数和键相等性比较函数。哈希函数用于将键映射到哈希表中的位置而键相等性比较函数则用于确定两个键是否相等。
下面是一个示例展示了如何使用自定义键类型 Person 作为 std::unordered_multimap 的键
#include iostream
#include unordered_map
#include string
#include functional // 用于 std::hash 和 std::equal_to // 自定义键类型
struct Person { Person(const std::string name, int age) : name(name), age(age) {} // 为了简化示例这里只根据name字段进行比较和哈希 bool operator(const Person other) const { return name other.name; } std::string name; int age;
}; // 为Person定义哈希函数
struct PersonHash { std::size_t operator()(const Person p) const { std::size_t h1 std::hashstd::string()(p.name); // 可以在这里添加更多字段的哈希计算如果需要的话 return h1; }
}; // 为Person定义键相等性比较函数
struct PersonEqual { bool operator()(const Person lhs, const Person rhs) const { return lhs.name rhs.name; }
}; int main()
{ // 使用自定义键类型的unordered_multimap std::unordered_multimapPerson, int, PersonHash, PersonEqual peopleMap; // 插入元素 peopleMap.emplace(Person(Alice, 30), 1); peopleMap.emplace(Person(Bob, 25), 2); peopleMap.emplace(Person(Alice, 30), 3); // 相同的Person对象可以插入多次 // 遍历并打印元素 for (const auto pair : peopleMap) { std::cout pair.first.name : pair.first.age - pair.second std::endl; } return 0;
}上面代码的输出为
Alice: 30 - 1
Alice: 30 - 3
Bob: 25 - 2这个例子定义了一个 Person 结构体它包含 name 和 age 两个字段。此外还为 Person 定义了哈希函数 PersonHash 和键相等性比较函数 PersonEqual。
在创建 std::unordered_multimap 时将 Person 作为键类型并将 PersonHash 和 PersonEqual 作为模板参数传递给 std::unordered_multimap。这样unordered_multimap 就知道如何为 Person 对象计算哈希值以及如何比较两个 Person 对象是否相等。
注意在哈希函数和键相等性比较函数中只考虑了 Person 的 name 字段。在实际情况中可能需要根据 Person 的所有字段来计算哈希值和比较相等性以确保正确的行为。特别是当两个 Person 对象具有相同的 name 但不同的 age 时只根据 name 进行哈希和比较可能会导致意外的行为。
