C++ 关联式容器详解：map 与 set

1.关联式容器

根据应用场景的不同，STL 总共实现了两种不同结构的管理式容器：树型结构与哈希结构。树型结构的关联式容器主要有四种：map、set、multimap、multiset。这四种容器的共同点是：使用平衡搜索树（即红黑树）作为其底层结构，容器中的元素是一个有序的序列。

关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是<key, value>结构的键值对，在数据检索时比序列式容器效率更高。

键对值中的 key 表示键值，value 表示与 key 对应的信息。

SGI-STL 中关于键值对的定义：

template<class T1,class T2>
struct pair {
    typedef T1 first_type;
    typedef T2 second_type;
    T1 first;
    T2 second;
    pair():first(T1()),second(T2()){}
    pair(const T1& a,const T2& b):first(a),second(b){}
};

值得注意的是：pair 是有重载比较大小的，first 和 second 一起比。

2.set

set 的主要特征可总结为：

1. set 是按照一定次序存储元素的容器
2. 在 set 中，元素的 value 也标识它 (value 就是 key，类型为 T)，并且每个 value 必须是唯一的。set 中的元素不能在容器中修改 (元素总是 const)，但是可以从容器中插入或删除它们
3. 在内部，set 中的元素总是按照其内部比较对象 (类型比较) 所指示的特定严格弱排序准则进行排序
4. set 容器通过 key 访问单个元素的速度通常比 unordered_set 容器慢，但它们允许根据顺序对子集进行直接迭代
5. set 在底层是用二叉搜索树 (红黑树) 实现的

值得注意的是：

1. 与 map/multimap 不同，map/multimap 中存储的是真正的键值对<key, value>，set 中只放 value，但在底层实际存放的是由<value, value>构成的键值对
2. set 中插入元素时，只需要插入 value 即可，不需要构造键值对
3. set 中的元素不可以重复 (因此可以使用 set 进行去重)
4. 使用 set 的迭代器遍历 set 中的元素，可以得到有序序列
5. set 中的元素默认按照小于来比较，即 1、2、3…的顺序
6. set 中查找某个元素，时间复杂度为 O(logN)
7. set 中的元素不允许修改
8. set 中的底层使用二叉搜索树 (红黑树) 来实现

2.1 find

由于 set 的基本功能，像 insert、erase、迭代器等都和 string、vector 等差不多，这里就不过多解释，详细的可以自行查看官方文档，本文将针对部分特殊的函数进行解析。

find 简单来说，就是寻找特定的键值，那么可以提出一个问题：

set<int> s;
s.insert(3); s.insert(2); s.insert(4); s.insert(5); s.insert(1);
s.insert(5); s.insert(2); s.insert(5);
auto pos = s.find(3); // 第一种
// auto pos = find(s.begin(), s.end(), 3); // 第二种
s.erase(3);

哪一种 find 方式能更好的删除？显然是第一种。

因为第一种是 set 里面的 find，会以平衡二叉搜索树的方式去查找，大的往左走，小的往右走，时间复杂度为 O(logN)；第二种是 algorithm(算法头文件) 中的 find，是以依次遍历的方式，即中序遍历的方式进行的，时间复杂度为 O(N)。

2.2 lower_bound、upper_bound

set<int> myset;
set<int>::iterator itlow, itup;
for(int i = 1; i < 10; i++) myset.insert(i * 10); // 10 20 30 40 50 60 70 80 90
itlow = myset.lower_bound(30); // ^
itup = myset.upper_bound(65); // ^
myset.erase(itlow, itup); // 10 20 70 80 90
cout << "myset contains:";
for(set<int>::iterator it = myset.begin(); it != myset.end();++it) cout << ' ' << *it;
cout << '\n';

因为迭代器的区间遵循左闭右开原则，所以 lower_bound 用于查找第一个大于等于给定值 val 的元素位置，upper_bound 用于查找第一个大于给定值 val 的元素位置。

3.multiset

multiset 的主要特征可总结为：

1. multiset 是按照特定顺序存储元素的容器，其中元素是可以重复的
2. 在 multiset 中，元素的 value 也会识别它 (因为 multiset 中本身存储的就是<value, value>组成的键值对，因此 value 本身就是 key，key 就是 value，类型为 T)，multiset 元素的值不能在容器中进行修改 (因为元素总是 const 的)，但可以从容器中插入或删除
3. 在内部，multiset 中的元素总是按照其内部比较规则 (类型比较) 所指示的特定严格弱排序准则进行排序
4. multiset 容器通过 key 访问单个元素的速度通常比 unordered_multiset 容器慢，但当使用迭代器遍历时会得到一个有序序列
5. multiset 底层结构为二叉搜索树 (红黑树)

值得注意的是：

1. multiset 中再底层中存储的是<value, value>的键值对
2. multiset 的插入接口中只需要插入即可
3. 与 set 的区别是，multiset 中的元素可以重复，set 中 value 是唯一的
4. 使用迭代器对 multiset 中的元素进行遍历，可以得到有序的序列
5. multiset 中的元素不能修改
6. 在 multiset 中找某个元素，时间复杂度为 O(logN)
7. multiset 的作用：可以对元素进行排序

3.1 count

count 用于统计容器中某个值出现的次数。

3.2 equal_range

multiset<int> mySet = {1, 2, 3, 3, 4, 5};
auto result = mySet.equal_range(3);
for(auto it = result.first; it != result.second;++it){
    cout << *it << " ";
}
cout << endl;

equal_range 用于查找重复元素之间的区间，返回一个 pair 对象，该对象包含两个迭代器：

1. 第一个迭代器指向 multiset 中第一个等于 value 的元素（如果存在），或者指向第一个大于 value 的元素（如果不存在等于 value 的元素）
2. 第二个迭代器指向 set 中最后一个等于 value 的元素的下一个位置（如果存在等于 value 的元素），或者与第一个迭代器相等（如果不存在等于 value 的元素）

4.map

map 的主要特征可总结为：

1. map 是关联容器，它按照特定的次序 (按照 key 来比较) 存储由键值 key 和值 value 组合而成的元素
2. 在 map 中，键值 key 通常用于排序和唯一地标识元素，而值 value 中存储与此键值 key 关联的内容。键值 key 和值 value 的类型可能不同，并且在 map 的内部，key 与 value 通过成员类型 value_type 绑定在一起，为其取别名称为 pair: typedef pair<const key, T> value_type
3. 在内部，map 中的元素总是按照键值 key 进行比较排序的
4. map 中通过键值访问单个元素的速度通常比 unordered_map 容器慢，但 map 允许根据顺序对元素进行直接迭代 (即对 map 中的元素进行迭代时，可以得到一个有序的序列)
5. map 支持下标访问符，即在 [] 中放入 key，就可以找到与 key 对应的 value
6. map 通常被实现为二叉搜索树 (更准确的说：平衡二叉搜索树 (红黑树))

由于 map 的基本功能，像 insert、erase、迭代器等都和 string、vector 等差不多，这里就不过多解释，详细的可以自行查看官方文档，本文将针对部分函数进行解析。

4.1 insert

map 中的 insert 插入的是一个 pair 结构对象，下面将列举多种插入方式：

创建普通对象插入

pair<string, string> kv1("insert", "插入");
dict.insert(kv1);

创建匿名对象插入

dict.insert(pair<string, string>("sort", "排序"));

调用 make_pair 函数插入

dict.insert(make_pair("string", "字符串"));

调用 make_pair 省去了声明类型的过程。

隐式类型转换插入

dict.insert({"string", "字符串"});

通常 C++98 只支持单参数隐式类型转换，到 C++11 的时候就开始支持多参数隐式类型转换。

有这么一个问题：为什么加上了引用反而要加 const

pair<string, string> kv2 = {"insert", "插入"};
const pair<string, string>& kv2 = {"insert", "插入"};

**无引用情况：**对于 pair<string, string> kv2 = { "string", "字符串" };，编译器可能会执行拷贝省略（也叫返回值优化 RVO 或命名返回值优化 NRVO）。比如在创建 kv2 时，直接在其存储位置构造对象，而不是先创建一个临时对象再拷贝 / 移动过去。

**加引用情况：**使用 const pair<string, string>& kv2 = { "string", "字符串" }; 时，这里 kv2 是引用，它绑定到一个临时对象（由大括号初始化列表创建）。因为引用本身不持有对象，只是给对象取别名，所以不存在像非引用对象构造时那种在自身存储位置直接构造的情况。不过，这种引用绑定临时对象的方式，只要临时对象的生命周期延长到与引用一样长（C++ 规则规定，常量左值引用绑定临时对象时，临时对象生命周期延长），也不会额外增加拷贝 / 移动开销。

4.2 operator->

map<string, string>::iterator it = dict.begin();
while(it != dict.end()){
    // it->first = "xxx";
    // it->second = "xxx";
    // cout << (*it).first << ":" << (*it).second << endl;
    cout << it->first << ":" << it->second << endl;
    ++it;
}
cout << endl;

map 中并没有对 pair 进行流插入运算符重载，(*it).first 这样子的方式又不太简洁不好看，所以进行了 -> 运算符重载，返回的是 first 的地址，因此 (*it).first 等价于 it->->first，为了代码可读性，就省略一个 ->。

4.3 operator[]

map 中提供了 [] 运算符重载，可以通过 key 来访问 value。

首先我们知道 insert 的返回值 key 的部分是一个迭代器，value 的部分是个布尔值，文档中对该返回值的解释是：

1. key 已经在树里面，返回 pair<树里面 key 所在节点的 iterator，false>，false 表示不用插入了
2. key 不在树里面，返回 pair<树里面 key 所在节点的 iterator，true>，true 表示需要插入新节点

再来看，左边是官方文档的原始定义，那么转化成右边的定义能够更直观理解其底层。

这里 V 代表值类型，K 代表键类型。operator[] 是操作符重载函数，接受一个常量引用类型的键 key，返回值类型 V 的引用。这样设计是为了支持对容器内元素的读写操作。例如，可以通过 map[key] = newValue; 来修改值，或者通过 auto value = map[key]; 来读取值。

然后通过 insert 判断是否插入新节点，最后返回指定节点的 value 值。

4.4 map 的应用实践：随机链表的复制

题目描述：

示例：

传送门：随机链表的复制

题解:

利用 map 的映射机制，首先，在第一次遍历原链表时，为原链表的每个节点创建一个对应的新节点，并将原节点和新节点的映射关系存储在 map 中。然后，在第二次遍历原链表时，对于原链表中的每个节点 cur，我们可以通过 cur->random 找到其随机指针指向的原节点，再利用之前存储的映射关系，在 map 中查找该原节点对应的新节点，将这个新节点赋值给当前新节点 copynode 的随机指针 copynode->random。

值得注意的是：

记录的不是 cur 和 newnode 的关系吗，为什么可以通过 cur->random 找到 newnode->random？

假设原链表有三个节点 A、B、C，节点 A 的随机指针指向节点 C **建立映射阶段：**会为 A、B、C 分别创建对应的新节点 A'、B'、C'，并在 nodeCopyMap 中记录映射关系：{A -> A', B -> B', C -> C'}。 **设置随机指针阶段：**当处理节点 A 时，cur 指向 A，cur->random 指向 C。由于 C 作为键存在于 nodeCopyMap 中，通过 nodeCopyMap[cur->random] 也就是 nodeCopyMap[C] 可以找到 C'，接着把 C' 赋值给 A' 的随机指针 A'->random，这样新链表中节点 A' 的随机指针就正确地指向了节点 C'，和原链表中节点 A 的随机指针指向 C 相对应

代码实现：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        map<Node*, Node*> nodeCopyMap;
        Node* copyhead = nullptr;
        Node* copytail = nullptr;
        Node* cur = head;
        while(cur) {
            Node* copynode = new Node(cur->val);
            if(copytail == nullptr) {
                copyhead = copytail = copynode;
            } else {
                copytail->next = copynode;
                copytail = copynode;
            }
            nodeCopyMap[cur] = copynode;
            cur = cur->next;
        }
        Node* copy = copyhead;
        cur = head;
        while(cur) {
            if(cur->random == nullptr) {
                copy->random = nullptr;
            } else {
                copy->random = nodeCopyMap[cur->random];
            }
            cur = cur->next;
            copy = copy->next;
        }
        return copyhead;
    }
};

5.multimap

multimap 的主要特征可总结为：

1. multimaps 是关联式容器，它按照特定的顺序，存储由 key 和 value 映射成的键值对<key, value>，其中多个键值对之间的 key 是可以重复的。
2. 在 multimap 中，通常按照 key 排序和惟一地标识元素，而映射的 value 存储与 key 关联的内容。key 和 value 的类型可能不同，通过 multimap 内部的成员类型 value_type 组合在一起，value_type 是组合 key 和 value 的键值对：typedef pair<const Key, T> value_type;
3. 在内部，multimap 中的元素总是通过其内部比较对象，按照指定的特定严格弱排序标准对 key 进行排序的。
4. multimap 通过 key 访问单个元素的速度通常比 unordered_multimap 容器慢，但是使用迭代器直接遍历 multimap 中的元素可以得到关于 key 有序的序列
5. multimap 在底层用二叉搜索树 (红黑树) 来实现

注意：multimap 和 map 的唯一不同就是：map 中的 key 是唯一的，而 multimap 中 key 是可以重复的。

值得注意的是：

1. multimap 中的 key 是可以重复的
2. multimap 中的元素默认将 key 按照小于来比较
3. multimap 中没有重载 operator[] 操作，因为一个 key 对应多个 value，不知道找哪个 value
4. 使用时与 map 包含的头文件相同

multimap 和 multiset 是差不多的，而且在实际应用中用的不多，所以这里就不细讲了。