简介

C++ 提供了八种不同的关联式容器。其中四种是按键有序排列的关联式容器：std::set、std::map、std::multiset 和 std::multimap；另外四种是按键无序的关联式容器：std::unordered_set、std::unordered_map、std::unordered_multiset 和 std::unordered_multimap。这些关联式容器属于特殊容器，意味着它们支持在“所有容器的接口”一章中描述的所有操作。

概述

这八种有序和无序容器的共同点在于，它们都将一个键与一个值相关联，可以通过键来获取对应的值。为了对关联式容器进行分类，只需回答三个简单问题：

• 键是否有序？
• 键是否有对应的值？
• 同一个键是否可以出现多次？

下表共有 $2^3 = 8$ 行，对应上述三个问题的所有组合，并额外回答第四个问题：在最佳情况下，通过键访问元素的速度有多快？

关联式容器特性汇总

自 C++98 起，C++ 支持有序关联式容器；从 C++11 开始，增加了无序关联式容器。这两类容器具有非常相似的接口。因此，以下代码示例对 std::map 和 std::unordered_map 都是通用的。更准确地说，std::unordered_map 的接口是 std::map 接口的一个超集，其余三对无序/有序容器也遵循这一规律。因此，将代码从有序容器迁移到无序容器非常容易。

你可以使用初始化列表初始化这些容器，并通过下标操作符添加新元素。对于键值对 p，p.first 表示键，p.second 表示其对应的值。

1// orderedUnorderedComparison.cpp 
2#include <iostream>
3#include <map>
4#include <unordered_map>
5
6// std::map
7int main(){
8  std::map<std::string, int> m {{"Dijkstra", 1972}, {"Scott", 1976}};
9  m["Ritchie"]= 1983;
10  std::cout << m["Ritchie"];            // 1983
11  std::cout<<"\n";
12  
13  for(auto p : m) std::cout << "{" << p.first << "," << p.second << "}";
14                // {Dijkstra,1972},{Ritchie,1983},{Scott,1976}
15  std::cout<<"\n";
16  
17  m.erase("Scott");
18  for(auto p : m) std::cout << "{" << p.first << "," << p.second << "}";
19                // {Dijkstra,1972},{Ritchie,1983}
20  std::cout<<"\n";
21  
22  m.clear();
23  std::cout << m.size() << std::endl;   // 0
24
25  // std::unordered_map
26
27  std::unordered_map<std::string, int> um {{"Dijkstra", 1972}, {"Scott", 1976}};
28  um["Ritchie"]= 1983;
29  std::cout << um["Ritchie"];          // 1983
30  std::cout<<"\n";
31  
32  for(auto p : um) std::cout << "{" << p.first << "," << p.second << "}";
33                 // {Ritchie,1983},{Scott,1976},{Dijkstra,1972}
34  std::cout<<"\n";
35  
36  um.erase("Scott");
37  for(auto p : um) std::cout << "{" << p.first << "," << p.second << "}";
38                 // {Ritchie,1983},{Dijkstra,1972}
39  std::cout<<"\n";
40  
41  um.clear();
42  std::cout << um.size() << std::endl;  // 0
43  
44  return 0;
45}

两次程序执行存在一个细微差别：std::map 中的键是有序的，而 std::unordered_map 中的键是无序的。那么，为什么 C++ 要提供如此相似的容器？答案已在上表中体现：根本原因通常是性能差异。无序关联式容器对键的访问时间为常数级，不随容器大小增长而变化。当容器规模较大时，这种性能差异会变得非常明显。