Logo
Section 1 / 2

简介

在了解了顺序容器之后，让我们进入关联容器的世界，学习键值对的基本原理。

导入

简介

在了解了顺序容器之后，让我们进入关联容器的世界，学习键值对的基本原理。

C++ 有八种不同的关联容器。其中四种是键值有序的关联容器：std::set、std::map、std::multiset 和 std::multimap。另外四种是键值无序的关联容器：std::unordered_set、std::unordered_map、std::unordered_multiset 和 std::unordered_multimap。这些关联容器是特殊的容器，意味着它们支持本章“通用容器”中描述的所有操作。

概览

这八种有序和无序容器有一个共同点：它们都将一个键与一个值关联起来。我们可以使用键来获取对应的值。为了对关联容器进行分类，需要回答以下三个简单问题：

  • 键是否有序？
  • 键是否关联一个值？
  • 键是否可以重复出现？

下表包含 23=82^{3} = 8 行，给出了这三个问题的答案。第四个问题的答案也包含在表中：在最佳情况下，访问键的时间复杂度是多少？

关联容器有序关联值允许重复键访问时间
std::set是否否对数级
std::unordered_set否否否常数级
std::map是是否对数级
std::unordered_map否是否常数级
std::multiset是否是对数级
std::unordered_multiset否否是常数级
std::multimap是是是对数级
std::unordered_multimap否是是常数级

关联容器特性

自 C++98 起，就存在有序关联容器；从 C++11 开始引入了无序关联容器。这两类容器具有非常相似的接口。因此，下面的代码示例对于 std::map 和 std::unordered_map 是相同的。更准确地说，std::unordered_map 的接口是 std::map 接口的超集。其余三组无序关联容器也遵循同样的规律。因此，将代码从有序容器迁移到无序容器非常容易。

我们可以使用初始化列表来初始化容器，并通过下标运算符添加新元素。要访问键值对 p 的第一个元素，使用 p.first；第二个元素使用 p.second。其中 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++ 中会有如此相似的容器？我们已经在上表中指出原因。根本原因通常是性能。无序关联容器中访问键的时间复杂度为常数，因此与容器大小无关。当容器足够大时，这种性能差异会非常明显。请参阅“性能”小节。

更多信息

  • 关联容器

  • 通用容器（见本课程相关章节）

  • 性能（见本课程相关章节）

在下一课中，我们将探讨有序和无序容器在插入和删除操作上的区别。

1.1 顺序容器

插入和删除