C++ unordered_multimap用法详解
unordered_multimap 是一个允许有重复键的无序 map。因此，它支持的操作实际上和 unordered_map 容器是相同的，为了处理多个重复键所做的添加和更改除外。后面会对这些差别做些讨论。生成 unordered_multimap 的方式和 unordered_map 相同。例如：
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() 模板的实例，从而输出元素。
由于程序运行结果很占篇幅，各位读者可自行运行程序查看运行结果。
发表评论