C++ unordered_multimap用法详解
unordered_multimap 是一个允许有重复键的无序 map。因此,它支持的操作实际上和 unordered_map 容器是相同的,为了处理多个重复键所做的添加和更改除外。后面会对这些差别做些讨论。生成 unordered_multimap 的方式和 unordered_map 相同。例如:
unordered_map 支持的成员函数 at() 和 operator[]() 对于 unordered_multimap 来说并不可用,因为潜在的重复键。唯一的选择是使用 find() 和 equal_range() 来访问元素。find() 总会返回它所找到的第一个元素的迭代器,如果找不到这个键,会返回一个结束迭代器。可以以键为参数调用 count() 来发现容器中给定键的元素个数。下面展示实际用法:
让我们来看一个使用 unordered_multimap 的示例。在这个示例中也会展示一些定义函数模板来使用容器的方式。这个程序会实现一个电话簿,可以用姓名或名称来查找电话号码。此处用一个 pair 对象来封装名和姓,用一个元组来记录区号、交换码、电话号码,它们都是以 string 对象的形式保存的。使用下面的 using 简化代码:
为了从 istream 对象读取电话号码,对 >> 运算符进行了重载。函数如下:
我们可以为 Name 对象做相同的事:
为 Name 对象重载 << 是很简单的:
把这两个哈希函数类型的定义放在同一个头文件中,名为 Hash_Function_Objects.h,文件的开头是下面这些代码:
通过名称或号码来查找元素的过程本质上是相同的,所以我们也可以为它们定义一个函数模板:
为了能够使 C++11 编译器可以确定返回类型,必须使用尾部返回类型语法。这会允许编译器在处理完函数参数后再处理返回类型。注意,typename 关键字对模板类型的规范是至关重要的,它对于局部变量 key 的规范也至关重要。容器中 key 的类型是由容器类的成员变量 key_type 指定的,所以 key 的类型规范会自动从容器中选择正确的类型。如果需要和键关联的对象的类型,它是由成员 Container:mapped_type 指定的,Container::value_type 指定了容器元素的类型。
C++14 标准为编译器引入了推断函数返回类型的能力,因而函数模板可以这样写:
这个操作允许通过搜索名称或号码来查找元素,每种情况都会返回一个 pair 对象,它包含的迭代器定义了一种或另一种类型元素的范围。我们可以另外定义一个函数模板来输出这段元素:
main() 函数包含下面这些代码:
添加元素只涉及每个容器元素的生成,by_name 使用的键/对象值和 by_number 使用的是相反的。
可以用 find_elements() 来删除 by_name 容器的元素,为了保证两个容器中内容的同步,需要删除 by_number 容器的对应元素。为了能够从 by_name 容器移除多个元素,需要用定义元素范围的迭代器作为 erase() 的参数。如果所有元素的键相同,就可以以这个范围内的第一个元素的键为参数来删除它们,例如:
由于程序运行结果很占篇幅,各位读者可自行运行程序查看运行结果。
std:: unordered_multimap<std::string,size_t> people {{"Jim",33}, {"Joe",99}};可以使用 insert()、emplace()、emplace_hint() 来添加新元素,这和 unordered_multimap 相同,只要参数和容器中的元素类型一致。这些成员函数都会返回一个指向容器中新元素的迭代器;在使用 inserted emplace() 的情况下,unordered_multimap 和 unordered_map 有些不同,unordered_multimap 的这两个函数会返回一个 pair 对象,它用来说明插入是否成功。如果不成功,也是一个迭代器。例如:
auto iter = people.emplace("Jan", 45); people.insert({"Jan", 44}); people.emplace_hint(iter, "Jan", 46);第 3 条语句使用了第 1 条语句返回的迭代器作为插入元素的提示符。这个提示符有时会被容器或我们的实现所忽略。
unordered_map 支持的成员函数 at() 和 operator[]() 对于 unordered_multimap 来说并不可用,因为潜在的重复键。唯一的选择是使用 find() 和 equal_range() 来访问元素。find() 总会返回它所找到的第一个元素的迭代器,如果找不到这个键,会返回一个结束迭代器。可以以键为参数调用 count() 来发现容器中给定键的元素个数。下面展示实际用法:
std:: string key{"Jan"}; auto n = people.count(key);//Number of elements stored with key if(n == 1) std::cout << key << " is " << people.find(key)->second<<std::endl; else if (n > 1) { auto pr = people.equal_range (key); // pair of begin & end iterators returned while(pr.first != pr.second) { std::cout << key << " is " << pr.first->second << std::endl; ++pr.first; // Increment begin iterator } }当容器中只有一个 key 时,可以用 find() 来访问这个元素。如果超过一个,可以用 equal_range() 来访问这段元素。当然,在这两种情况下都可以使用 equal_range()。
让我们来看一个使用 unordered_multimap 的示例。在这个示例中也会展示一些定义函数模板来使用容器的方式。这个程序会实现一个电话簿,可以用姓名或名称来查找电话号码。此处用一个 pair 对象来封装名和姓,用一个元组来记录区号、交换码、电话号码,它们都是以 string 对象的形式保存的。使用下面的 using 简化代码:
using std::string; using std::unordered_multimap; using Name = std::pair<string, string>; using Phone = std::tuple<string, string, string>;电话号码可以用三个整数来表示,但这样组合起来更像编码而不是号码。电话号码中的每个元素都有固定个数的数字,有一些位数的组合是不允许的。如果想增加对号码检查的功能,显然用 string 对象可以使号码位数或区号的检查更简单。这里并没有包含这个功能,因为这会使本书的编码量大大增加。
为了从 istream 对象读取电话号码,对 >> 运算符进行了重载。函数如下:
inline std::istream& operator>>(std::istream& in, Phones phone) { string area_code {},exchange {}, number {}; in >> std::ws >> area_code >> exchange >> number; phone = std::make_tuple(area_code, exchange, number); return in; }phone 是元组模板类型。这里 make_tuple() 使用从 in 读出的局部变量的值生成了一个 phone 对象。
我们可以为 Name 对象做相同的事:
inline std::istream& operator>>(std::istream& in, Names& name) { in >> std::ws >> name.first >> name.second; return in; }这里会丢弃从 in 读入的任何前置空格,然后读出两个 name 字符串作为 pair 对象的成员。当然,我们也需要输出功能。这里定义了 operator<<() 来为 phone 对象提供输出:
inline std::ostream& operator<<(std::ostream& out, const Phone& phone) { std::string area_code {}, exchange {}, number {}; std::tie(area_codeA exchange, number) = phone; out << area_code <<" "<< exchange << " " << number; return out; }这里使用函数模板 tie<>() 生了一个包含三个局部变量引用的元组。然后为了将 phone 的成员变量的值保存到局部变量中,将 phone 赋值给 tie<>() 生成的元组,后面会输出这些局部变量。或者,使用函数模板 get<>() 来访问 phone 成员变量的值。这种方法显然更好,因为能够避免上面出现的 string 对象的副本,但这里是为了展示 tie<>() 函数的使用。
为 Name 对象重载 << 是很简单的:
inline std::ostream& operator<<(std::ostream& out, const Name& name) { out << name.first << " " << name.second; return out; }所有的这些 I/O 函数都是内联的,所以把它们放在叫作 Record_IO.h 的头文件中。文件的开头是 #include 和 using:
#include <string> // For string class #include <istream> // For istream class #include <ostream> // For ostream class #include <utility> // For pair type #include <tuple> // For tuple type using Name = std::pair <std::string, std::string>; using Phone = std::tuple <std::string, std::string,std::string>;这个程序会使用两个关联容器一其中一个以名称作为键,另一个以电话号码为键,所以它们都会包含相同的基本信息,但它们的访问方式不同。当然有更有效率的方式来做这些,但这里我们是为了尝试 unordered_multimap 容器的使用。main() 中定义的容器如下:
unordered_multimap<Name, Phone, NameHash> by_name {8, NameHash()}; unordered_multimap<Phone, Name, PhoneHash> by_number {8, PhoneHash()};这里并没有为 pair 或 tuple 对象提供默认的哈希能力,所以我们不得不自己定义它们。 这里它们分别是 NameHash 和 PhoneHash 类型的函数对象。构造函数中哈希函数对象之前的参数是格子的个数,所以这里的格子数是指定的。它们等于系统的默认值。
把这两个哈希函数类型的定义放在同一个头文件中,名为 Hash_Function_Objects.h,文件的开头是下面这些代码:
#include <string> // For string class #include <utility> // For pair type #include <tuple> // For tuple type using Name = std::pair < std::string, std::string >; using Phone = std::tuple < std::string, std::string, std::string >;按如下方式定义 PhoneHash 类型:
// Hash a phone number class PhoneHash { public: size_t operator()(const Phone& phone) const { return std::hash<std::string>()(std::get<0>(phone)+std::get<1>(phone)+std::get<2>(phone)); } };通过用定义在 string 头文件中的 hash<string>() 模板的特例化来处理电话号码中三个元素串联后的结果,对应地生成哈希值。下面以相似的方式定义了 HashName 类型:
// Hash a name class NameHash { public: size_t operator()(const Name& name) const { return std::hash<std::string>()(name.first + name.second); } };将输出操作打包放在单独的函数中:
void show_operations() { std::cout << "Operations:\n"<< "A: Add an element.\n"<< "D: Delete elements.\n"<< "F: Find elements.\n"<< "L: List all elements.\n"<< "Q: Quit the program.\n\n"; }通过名称或号码列出所有的元素。我们定义了一个函数模板来处理这两种可能:
template<typename Container> void list_elements(const Container& container) { for(const auto& element : container) std::cout << element.first << " " << element.second << std::endl; }当函数被调用时,这个模板会从使用的参数中推断出容器的类型。两个容器包含的元素是 pair 对象。by_name 容器包含的是 pair<Name,Phone>S 象类型的元素,by_number 容器包含的是 pair<Phone,Name> 对象类型的元素。因为我们己经为 Name 和 Phone 类型重载了 operator<<(),循环体会为 pair 元素的成员变量类型自动选择合适的函数输出。把这个函数模板和 My_Templates.h 头文件后面的模板放在完整的示例中。
通过名称或号码来查找元素的过程本质上是相同的,所以我们也可以为它们定义一个函数模板:
template<typename Container> auto find_elements(const Container& container) { typename Container::key_type key {}; std::cin >> key; auto pr = container.equal_range(key); return pr; }这段代码对应于 C++11 标准。返回类型是依赖容器类型的 pair<> 模板类型。这是因为返回的 pair 封装的迭代器类型是特定的容器类型。这就意味着编译器不能处理函数名之前的返回类型,因为容器的类型取决于函数参数的类型,这个类型稍后才用得到。
为了能够使 C++11 编译器可以确定返回类型,必须使用尾部返回类型语法。这会允许编译器在处理完函数参数后再处理返回类型。注意,typename 关键字对模板类型的规范是至关重要的,它对于局部变量 key 的规范也至关重要。容器中 key 的类型是由容器类的成员变量 key_type 指定的,所以 key 的类型规范会自动从容器中选择正确的类型。如果需要和键关联的对象的类型,它是由成员 Container:mapped_type 指定的,Container::value_type 指定了容器元素的类型。
C++14 标准为编译器引入了推断函数返回类型的能力,因而函数模板可以这样写:
template<typename Container> auto find_elements(const Container& container) -> std::pair<typename Container::const_iterator, typename Container::const_iterator> { typename Container::key_type key {}; std::cin >> key; auto pr = container.equal_range(key); return pr; }这里不需要尾部返回类型,因为编译器可以从返回值 pr 中推断出返回类型。
这个操作允许通过搜索名称或号码来查找元素,每种情况都会返回一个 pair 对象,它包含的迭代器定义了一种或另一种类型元素的范围。我们可以另外定义一个函数模板来输出这段元素:
template<typename T> void list_range(const T& pr) { if(pr.first != pr.second) { for(auto iter = pr.first; iter != pr.second; ++iter) std::cout << " " << iter->first << " " << iter->second << std::endl; } else std::cout << "No records found.\n"; }如果作为参数的 pair 对象的成员变量是相同的,那么范围为空,这种情况下我们只会输出一条消息。为 Name 和 Phone 类型实现的 << 运算符函数使这个模板可以正常使用。pair 成员变量的实际类型会自动选择合适的 operatorr<< 函数。需要注意的是,在已编译的代码中,这些模板不会减少代码量。它们只是提供了一种生成所使用函数的转换机制,提供了如何使用模板的简单演示。
main() 函数包含下面这些代码:
#include <iostream> // For standard streams #include <cctype> // For toupper() #include <string> // For string class #include <unordered_map> // For unordered_map container #include "Record_IO.h" #include "My_Templates.h" #include "Hash_Function_Objects.h" using std::string; using std::unordered_multimap; using Name = std::pair < string, string >; using Phone = std::tuple < string, string, string >; // Display command prompt void show_operations() { std::cout << "Operations:\n"<< "A: Add an element.\n"<< "D: Delete elements.\n"<< "F: Find elements.\n"<< "L: List all elements.\n"<< "Q: Quit the program.\n\n"; } int main() { unordered_multimap<Name, Phone, NameHash> by_name {8, NameHash()}; unordered_multimap<Phone, Name, PhoneHash> by_number {8, PhoneHash()}; show_operations(); char choice {}; // Operation selection Phone number {}; // Records a number Name name {}; // Records a name while(std::toupper(choice) != 'Q') // Go until you quit... { std::cout << "Enter a command: "; std::cin >> choice; switch(std::toupper(choice)) { case 'A': // Add a record std::cout << "Enter first & second names, area code, exchange, and number separated by spaces:\n"; std::cin >> name >> number; by_name.emplace(name, number); // Create in place... by_number.emplace(number, name); // ...in both containers break; case 'D': // Delete records { std::cout << "Enter a name: "; // Only find by name auto pr = find_elements(by_name); auto count = std::distance(pr.first, pr.second); // Number of elements if(count == 1) { // If there's just the one... by_number.erase(pr.first->second); // ...delete from numbers container by_name.erase(pr.first); // ...delete from names container } else if(count > 1) { // There's more than one std::cout << "There are " << count << " records for "<< pr.first->first << ". Delete all(Y or N)? "; std::cin >> choice; if(std::toupper(choice) == 'Y') { // Erase records from by_number container first for(auto iter = pr.first; iter != pr.second; ++iter) { by_number.erase(iter->second); } by_name.erase(pr.first, pr.second); // Now delete from by_name } } } break; case 'F': // Find a record std::cout << "Find by name(Y or N)? "; std::cin >> choice; if(std::toupper(choice) == 'Y') { std::cout << "Enter first name and second name: "; list_range(find_elements(by_name)); } else { std::cout << "Enter area code, exchange, and number separated by spaces: "; list_range(find_elements(by_number)); } break; case 'L': //List all records std::cout << "List by name(Y or N)? "; std::cin >> choice; if(std::toupper(choice) == 'Y') list_elements(by_name); else list_elements(by_number); break; case 'Q': break; default: std::cout << "Invalid command - try again.\n"; } } }这段代码很好理解。在输入选项后,程序就会执行相应的操作,直到输入 'q' 或 'Q'。 循环体是一条大的 switch 语句,用来选择合适的操作。
添加元素只涉及每个容器元素的生成,by_name 使用的键/对象值和 by_number 使用的是相反的。
可以用 find_elements() 来删除 by_name 容器的元素,为了保证两个容器中内容的同步,需要删除 by_number 容器的对应元素。为了能够从 by_name 容器移除多个元素,需要用定义元素范围的迭代器作为 erase() 的参数。如果所有元素的键相同,就可以以这个范围内的第一个元素的键为参数来删除它们,例如:
by_name.erase(pr.first->first); // Delete elements with the specified key为了查找操作,find_elements() 模板实例返回的 pair 必须直接传给 list_range() 模板的实例。编译器会自动保证生成合适的调用。最后,为了可以列出元素,必须用指定的键为参数来调用一个 list elements() 模板的实例,从而输出元素。
由于程序运行结果很占篇幅,各位读者可自行运行程序查看运行结果。
所有教程
- socket
- Python基础教程
- C#教程
- MySQL函数
- MySQL
- C语言入门
- C语言专题
- C语言编译器
- C语言编程实例
- GCC编译器
- 数据结构
- C语言项目案例
- C++教程
- OpenCV
- Qt教程
- Unity 3D教程
- UE4
- STL
- Redis
- Android教程
- JavaScript
- PHP
- Mybatis
- Spring Cloud
- Maven
- vi命令
- Spring Boot
- Spring MVC
- Hibernate
- Linux
- Linux命令
- Shell脚本
- Java教程
- 设计模式
- Spring
- Servlet
- Struts2
- Java Swing
- JSP教程
- CSS教程
- TensorFlow
- 区块链
- Go语言教程
- Docker
- 编程笔记
- 资源下载
- 关于我们
- 汇编语言
- 大数据
- 云计算
- VIP视频