【STL 源码剖析】系列十一：关联式容器 --set、map、multiset 和 multimap

前言

在了解 STL 的 RB-tree（红黑树）数据结构之后，实现 set 和 map 就非常简单，因为 set 和 map 均以红黑树作为底层实现（因此 set 和 map 中的元素实际上均是一个有序的序列），其对外接口均是调用底层实现的接口。本篇主要内容：

1.set 和 map 的特性以及如何基于红黑树实现容器；

2.multiset 和 multimap 如何基于红黑树实现。

注：本篇基本上是对 set、map、multiset、multimap 源代码的注释，实现技巧在红黑树中已经说明。

因此比较枯燥。

set

set 概述

set（集合）中的所有元素都会根据元素的键自动被排序，每个元素的键 (key) 就是实值 (value)。

set 中不允许存在两个元素具有相同的键值，也就是不允许存在两个相同的元素。

正是由于 set 中实值就是键值，因此不能通过迭代器随意更改实值。set 容器中底层实现是 RB-tree，也就是说所有元素都是按照一定的键值顺序排列的，如果随意更改实值，那么键值也会随之改变，破坏了二叉搜索树的结构。

由于 set 和 list 一样均使用离散式存储结构（都以结点表示元素），因此当客户端进行新增操作或者删除操作时，操作之前的迭代器不会失效。

set 源代码摘录

由于 RB-tree 是一种平衡二叉搜索树，其自动排序以及查找的效率很不错，因此 STL set 以红黑树作为底层机制。

并且 set 需要对外开放的接口，均可以调用红黑树的接口来实现。

set 的 find 操作

对于关联式容器来说，应该使用其内部提供的 find 函数来进行查找元素，这样比使用 STL 算法的 find 更有效率。

这是因为 STL 的算法只是根据迭代器遍历搜寻，而关联式容器的搜寻会基于其底层实现来进行搜寻，比如 set 的底层实现是红黑树，那么对于 n 个元素的搜寻效率是 O (logn)，而 STL 的算法采用遍历搜寻，搜寻效率是 O (n)。

map

map 概述

map（字典）中的每一个元素都是一对键值（value）和实值（value），所有元素根根据键值（key）自动排序。

map 中不允许存在键值相同的两个元素。

map 中的每一个元素是一个 pair，pair 的第一元素是键值（key），第二元素是实值（value），定义如下：

对于 map 来说，如果想要通过迭代器修改键值（key），这是不被允许的，因为键值关系到所有元素的排列规则；如果想要通过迭代器改变实值（value）是可以的。

由于 map 和 set、list 一样采用离散式存储结构，所以当进行增加、删除等操作之后，原来的迭代器仍然可以正常使用。

map 源代码摘录

map 同样以 RB-tree 作为底层实现机制，并且 map 需要向外提供的接口，红黑树中已经提供，所以其实现比较简单：

注意，在 map 的实现中，只要返回值是迭代器的函数，一般都有两个版本，一个返回普通迭代器，一个返回 const 迭代器。

针对下标访问方式的说明

map 中可以使用下标加键值的方式访问元素的实值：

上面 A 式的说明：

// 首先，最内层创建一个元素对象：
// 这个元素对象的实值不重要
// 键值必须是通过[]传递的即可
value_type(k, T())；
    
    
// 接着，尝试调用insert函数将该元素根据键值key插入到红黑树中
// 假设键值已经存在，那么一定会找到这样一个键值为k的结点
insert(value_type(k, T()))；

    
// 插入操作返回值一个pair，第一个元素是迭代器，第二个元素表示是否能够插入
// 如果键值存在，那么第一个元素刚好就是要找的结点
(insert(value_type(k, T()))).first
// 解引用这个迭代器可以得到元素
*((insert(value_type(k, T()))).first)
// map的每个元素都是pair，第二个是value
(*((insert(value_type(k, T()))).first)).second

// 如果键值不存在就会报错
    

multiset

multiset 与 set 特性与用法与 set 基本相同，唯一的区别在于 multiset 允许键值重复，因此它的插入操作采用的是底层红黑树的 insert_equal（set 采用的是 insert_unique）。

下面是 multiset 的源代码摘要，只列出与 set 的不同之处：

multimap

multimap 的特性和用法与 map 完全相同，唯一的区别就是 multimap 允许键值重复，因此插入操作采用的是底层红黑树的 insert_equal。

下面是源代码摘要，只列出与 map 的不同之处：