突破编程_C++_C++11新特性（unordered_multimap）

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_multimap<KeyType, ValueType> mapName;

其中 KeyType 是键的类型，ValueType 是值的类型，mapName 是你为该 unordered_multimap 变量选择的名称。

2.2 初始化

初始化 std::unordered_multimap 可以通过多种方式进行，包括默认初始化、使用列表初始化器初始化、复制初始化、移动初始化等。

（1）默认初始化

如果没有提供任何初始化器，std::unordered_multimap 将被默认初始化，这意味着它将不包含任何元素，并且会使用默认的哈希函数和键相等性比较对象。

std::unordered_multimap<std::string, int> myMultimap; // 默认初始化

（2）使用列表初始化器初始化

可以使用列表初始化器（大括号 {}）来初始化 std::unordered_multimap，并直接添加一些元素。

std::unordered_multimap<std::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_multimap<std::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_multimap<std::string, int> myMultimap;  // 插入多个键值对  myMultimap.insert({  {"apple", 10},  {"banana", 20},  {"orange", 30}  });  return 0;  
}

在这个例子中，使用初始化列表一次性插入了三个键值对。

（2）使用迭代器插入

insert 函数还有一个重载版本，它接受一个迭代器和一个键值对，尝试在迭代器指向的位置插入元素。如果插入成功，函数返回一个指向新插入元素的迭代器；如果插入失败（例如，由于内存不足），则返回一个指向容器中下一个有效位置的迭代器。

#include <unordered_map>  
#include <string>  int main() 
{  std::unordered_multimap<std::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_multimap<std::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_multimap<std::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_multimap<std::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_multimap<std::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_multimap<std::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_multimap<std::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_multimap<int, 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_multimap<std::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::hash<std::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_multimap<Person, 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 进行哈希和比较可能会导致意外的行为。