C++ STL容器底层学习（个人总结）

C++ STL容器底层学习（个人总结） 0、前言

声明： 本文是在阅读 STL 源码剖析这本书后做的个人笔记，算法 *** 作的具体实现原理建议直接阅读 《STL 源码剖析 – 侯捷》。
建议： 本文适合对数据结构有一定基础，熟悉各种容器的基本 *** 作。适合在看完书中容器的每一节后观看。
方便阅读： 本文针对每个容器，讨论问题主要有以下方面：

1. 容器是如何实现的
2. 容器的常用 *** 作
3. 容器一些算法需要注意的一些细节。

1、序列式容器 1.1 vector 描述

类似于 C 语言中的数组，vector 维护的是一段连续的线性空间，不同的是 vector 是可扩充的。

迭代器

vector 的迭代器类型是随机访问迭代器，就是一个普通的指针就可以。

vector 的数据结构

iterator start;				// 表示目前使用空间的头，一个指向头元素的指针
iterator finish;			// 表示目前使用空间的尾，指向尾元素后边一个元素的指针，这主要是满足一个设计原则 "前闭后开"
iterator end_of_storage;	// 表示目前可用空间的尾

vector 常用 *** 作 非元素 *** 作

iterator begin();		// 返回指向首元素的迭代器		
iterator end();			// 返回指向尾元素之后位置的迭代器
size_type size();		// 返回元素个数	
bool empty();			// 判断是否为空
reference front();		// 返回第一个元素
reference back();		// 返回最后一个元素
vi[i];					// 返回下标为 i 的元素

元素 *** 作

push_back();			// 向表尾插入元素
pop_back();				// 删除表尾元素
erase();				// 删除指定元素
clear();				// 清空容器(删除容器中的所有元素)
insert();				// 插入元素

vector 扩充方式

容量变化： 不同环境，扩充大小不同，经实验，在 linux 中容量通常扩充为原来的 2 倍，在 vs 中是 1.5 倍。
扩充时机： 发生扩充通常是插入元素时，在尾部插入属于特殊的插入，可以在任意位置插入(O(N))，这种情形下会发生扩充。
扩充步骤： 总共分为 3 步：

1. 首先将旧 vector 中插入点之前的元素复制到新的空间。
2. 将新增元素填入新空间。
3. 将旧 vector 中插入点之后的元素复制到新的空间。

1.2 list 描述

list 类似于 C 语言中的双向链表，多了一个空白节点 node（原因：满足前闭后开原则），node 的 next 指向 list 的首元素，node 的 prev 指向 list 的尾元素，则 node 就是 list 的 end()。

节点结构

node_pointer prev;		// 指向前驱节点的指针
node_pointer next;		// 指向后继节点的指针
T data;					// 节点值

迭代器

迭代器组成：
node_pointer node; // 一个指针，指向该迭代器所指的节点
迭代器类型： 双向迭代器。

list 的数据结构

node_pointer node;		// 一个迭代器，指向刻意置于尾端的空白节点

list 常用 *** 作 非元素 *** 作

iterator begin();		// 返回指向首元素的迭代器		
iterator end();			// 返回指向尾元素之后位置的迭代器
size_type size();		// 返回元素个数	
bool empty();			// 判断是否为空
reference front();		// 返回第一个元素
reference back();		// 返回最后一个元素

元素 *** 作

push_back();			// 向链尾插入元素
pop_back();				// 删除链尾元素
push_front();			// 向链头插入元素
pop_front();			// 删除链头元素
erase();				// 删除指定元素
clear();				// 清空容器(删除容器中的所有元素)
insert();				// 插入元素
transfer(iterator position,iterator first,iterator last)  //将 [first,last) 内的所有元素移动到 position 之前
splice(iterator position,iterator first,iterator last)	//将 [first,last) 内的所有元素插入到 position 之前
merge(list &x)	// 合并两个有序链表。将 x 有序链表与当前有序链表合并
reverse()				// 翻转链表
sort()					// 排序链表

1.3 forward_list 描述

forward_list 类似于 C 语言中的单向链表，多了一个空白节点 node（原因：满足前闭后开原则），node 的 next 指向 forward_list 的首元素，则 node 就是 forward_list 的 end()；

节点结构

forward_list 是通过继承来实现的，一个包含 next 的类 L1，一个包含 data 的类 L2，L2 继承于 L1。

node_pointer next;		// 指向后继节点的指针
T data;					// 节点值

迭代器

迭代器组成：
node_pointer node; // 一个指针，指向该迭代器所指的节点
迭代器类型： 单向迭代器。

forward_list 的数据结构

node_pointer node;		// 一个迭代器，指向刻意置于尾端的空白节点

forward_list 常用 *** 作 非元素 *** 作

iterator begin();		// 返回指向首元素的迭代器		
iterator end();			// 返回指向尾元素之后位置的迭代器
size_type size();		// 返回元素个数	
bool empty();			// 判断是否为空
reference front();		// 返回第一个元素
swap();					// 两个 forward_list 交换
// 注意没有 back()

元素 *** 作

push_front();			// 向链头插入元素，没有 push_back()
pop_front();			// 删除链尾元素，没有 pop_back()

需要注意的细节

1. forward_list 只支持头部的插入、删除和查看。
2. 因为 1，所以插入顺序与遍历时的输出顺序相反。

1.4 deque 描述

deque 是一段一段的定量连续空间构成（分段连续线性空间）。主要是由一个中控器来控制多个容量相同的缓冲区。

deque 与 vector 的差异

1. deque 允许在常数时间内对头(尾)端进行插入或移除 *** 作。（vector 只能对尾部）。
2. deque 没有所谓”容量“的概念，它是动态地以分段连续空间组合而成。所以 deque 没有必要提供所谓的空间保留功能。（个人看法：它的迭代器完成了这个功能，通过存储所指之缓冲区的头和尾）

中控器（管控中心） 结构

map_pointer map;		// 一个指针的指针，指向map(中控器)，map是块连续空间、其内的每个元素都是一个指针(称为节点)，指向一块缓冲区
size_type map_size; 	// map内可以容纳多少指针，也就是可以容纳多少个缓冲区

迭代器

迭代器结构

T* cur;		// 此迭代器所指之缓冲区中的现行元素
T* first;	// 此迭代器所指之缓冲区的头
T* last;	// 此迭代器所指之缓冲区的尾（含备用空间）
map_pointre node;	// 指向中控器

迭代器类型： 随机访问迭代器

deque 的数据结构

iterator start;		// 指向第一个节点
iterator finish;	// 指向最后一个节点之后的位置
map_pointer map;	// 指向中控器
size_type map_size;	// map 内有多少指针。

deque 常用 *** 作 非元素 *** 作

iterator begin();		// 返回指向首元素的迭代器		
iterator end();			// 返回指向尾元素之后位置的迭代器
size_type size();		// 返回元素个数	
bool empty();			// 判断是否为空
reference front();		// 返回第一个元素
reference back();		// 返回最后一个元素
vi[i];					// 返回下标为 i 的元素

元素 *** 作

push_back();			// 向表尾插入元素
pop_back();				// 删除表尾元素
push_front();			// 向表头插入元素
pop_front();			// 删除表头元素
erase();				// 删除指定元素
clear();				// 清空容器(删除容器中的所有元素)
insert();				// 插入元素

扩充方式 针对 map(中控器) 是否需要扩充：

扩充时机： 若在头/尾插入的元素个数大于节点备用空间，那么需要对 map 进行扩充。
扩充步骤： 1：配置一块空间，准备给新 map 使用。2：把原 map 内容拷贝过来。3：释放原 map。4：设定新 map 的起始地址和大小。

针对是否需要增加缓冲区

头部： 第一缓冲区已无备用空间。
尾部： 最后缓冲区只剩一个元素备用空间。

针对是否需要释放缓冲区

头部： 第一缓冲区没有元素。
尾部： 最后缓冲区仅有一个元素。
头尾不同的原因：因为前闭后开原则。

insert/erase *** 作

比较插入点/删除点左边的元素个数和右边的元素个数，那边少，就移动那边的元素。

需要注意的细节

当对 deque 进行排序 *** 作时，为了提高效率，可将 deque 先完整复制到一个 vector 身上，将 vector 排序后，再复制到 deque。

1.5 stack 与 queue 描述

1. stack 与 queue 可以看作是容器也可以是适配器。都是特殊的 deque。
2. stack 与 queue 的底层数据结构可以是 deque，也可以是 list。
3. stack 与 queue 没有迭代器，返回的 begin() 等都是底层数据结构的迭代器。

常用 *** 作 stack

empty();		// 判断栈是否为空
size();			// 返回栈的大小
top();			// 返回栈顶元素
push();			// 入栈
pop();			// 出栈

queue

empty();		// 判断队列是否为空
size();			// 返回队列大小
front();		// 返回队头元素
back();			// 返回队尾元素
push();			// 入队
pop();			// 出队

1.6 heap 和 priority_queue heap 描述

heap 就是我们通常所说的大根堆或者小根堆，它并不归属于 STL 容器组件，它是 priority_queue 的底层数据结构。它是一颗完全二叉树并且提供了一系列 *** 作（方法）来实现堆。

方法（这里我们都假设是大根堆）

make_heap(iterator first,iterator last)		// 通过这个 *** 作，该迭代器范围的元素调整为堆
push_heap(iterator first,iterator last)		//	根据传入的迭代器去调整堆，（新加入元素前的元素已经是堆了）这个时候新加入的元素已经放在尾部（这样才更具有泛化性）
pop_heap(iterator first,iterator last)		// 把最大的元素(第一个元素)与尾元素进行交换，然后进行调整，使每个节点都满足大根堆的性质
sort_heap(iterator first,iterator last)		// 通过这个 *** 作，该迭代器范围的元素将会有序

需要注意的细节

1. 传入 heap 的迭代器类型是随机访问迭代器。
2. heap 没有迭代器，只有传入的迭代器，不提供遍历功能。原因是：heap 所有元素都必须遵循特别的完全二叉树排列规则。

priority_queue 描述

priority_queue 和 stack 和 queue 一样都可以被认为是适配器，原因是它的底层是 heap，并且 heap 底层默认是 vector。
priority_queue 可以提供 comp。
priority_queue 可以看作是特殊的 queue，只能从底部加入元素，从顶部取出元素。

priority_queue 的数据结构

Sequence c;		// 底层容器，默认是 vector
Compare comp;	// 元素大小比较标准，默认是 less

priority_queue 常用 *** 作

empty();		// 判断是否为空
size();			// 获取队列大小
push();			// 入队
pop();			// 出队
top();			// 获取最大值(假如是大根堆)
// 并没有提供 back(); 因为最小元素不一定是最后一个(假如是大根堆)

需要注意的细节

priority_queue 不提供遍历功能，也不提供迭代器。

2、关联式容器

摘要： 关联式容器主要可以分为有序和无序两大类，主要是底层容器分别采用 RB-Tree 和 HashTable 的原因。所以理解这两个容器的实现对于理解关联式容器来说非常重要。

2.1 RB-Tree 描述

RB-Tree 是一个平衡的二叉搜索树，和 AVL-Tree (也是一颗平衡二叉搜索树)相比，由于 AVL-Tree 在插入和删除的时候会存在大量的旋转 *** 作，所以如果在应用涉及到频繁的插入和删除时，要放弃 AVL-Tree，选择性能更好的 RB-Tree。
注意： 红黑树在实现中，是一颗带头节点的红黑树，其中 header 颜色为红色，它的左孩子指向最左节点（最小值），它的右孩子指向最右节点（最大值），它的双亲指向根节点。

RB-Tree 的性质

1. 每个节点不是黑色就是红色
2. 根节点是黑色节点，NULL 节点认为是黑色节点
3. 树中不存在两个相邻的红色节点
4. 任一节点到 NULL(树尾端)的任何路径，所含的黑色节点数必须相同

新插入节点，默认为红色节点

变换规则

为了方便描述，设插入节点为 X，父亲节点为 P，叔叔节点为 S，祖父节点为 G，曾祖父节点为 GG。
总共包括四种情形：（详情见书本 P210）
很明显，要发生旋转，X 为红色，P 为红色，G 为黑色。

1. 当 S 为黑色且 X 为外侧插入时，需要对 P、G 做一次单旋转，并且改变 P、G颜色。（改变 G 的颜色，是为了确保性质 4）
2. 当 S 为黑色而 X 为内测插入时，需要进行二次旋转，记先对 P、X 做一次单旋转（个人理解：这个就相当于把外侧转换为了内测），然后对 X、G 进行一次单旋转，并且改变 X、G 颜色（改变 G 的颜色，是为了确保性质 4）
3. 当 S 为红色而 X 为外侧插入，并且 GG 为黑色时，对 P、G 做一次单旋转，并且改变 X 颜色（这个时候不能改变 P、G，也是为了确保性质 4）
4. 当 S 为红色而 X为外侧输入，并且 GG 为红色时，对 P、G 做一次单旋转，并改变 X 颜色，然后递归处理。
   针对这个递归，STL 底层做了处理（实行一个由上而下的程序），假设新增节点为 A，那么就沿着 A 的路径，只要看到有某节点 X 的两个子节点皆为红色，就把 X 改为红色，并把两个子节点改为黑色。
5. 当 S 为红色而 X 为内测插入时，可以通过一次旋转变为外侧插入，如同 2 变为 1 一样。

特别注意：每次旋转后，都要让根节点变为黑色（保持根节点始终为黑色）

节点结构

color_type color;		// 表示节点颜色
base_ptr parent;		// 指向该节点父亲节点的指针
base_ptr left;			// 指向该节点左孩子节点的指针
base_ptr right;			// 指向该节点右孩子节点的指针
value value_field;		// 节点值

迭代器

迭代器组成：
base_ptr node; // 指向该迭代器所指节点的指针
迭代器类型： 双向迭代器。

RB-Tree 的数据结构

size_type node_count;	// RB-Tree 的节点数量
link_type header;		// 指向头节点(header)的指针，其中 header 颜色为红色，它的左孩子指向最左节点（最小值），它的右孩子指向最右节点（最大值），它的双亲指向根节点。
Compare key_compare;	// 节点间键值大小的比较准则

RB-Tree 常用 *** 作

insert_unique();	// 插入，不允许有重复元素
insert_equal();		// 插入，允许有重复元素

主要注意一下旋转函数 __rb_tree_rebalance()

1. 判断是否会发生第 4 种情形，如果发生，直接变换颜色就可以了。
2. 根据情形判断属于其他 3 种情形的那一种，然后执行对应的 *** 作。
3. 重点注意：根节点要变为黑色（无论上述旋转是否把根节点变为红色）

2.2 map、set、multiset和multimap 四个的共同点

1. 它们的底层都是采用的 RB-Tree。
2. 对所有关联式容器，应该使用其所提供的 find 函数来搜寻元素，会比使用 STL 算法 find() 更有效率。
3. 它们的迭代器失效问题都类似于 list，因为底层都是 RB-Tree，节点是不连续的。

set 概述

set 的底层是 RB-Tree，它的所有元素都会根据元素的键值自动被排序，它的键值就是实值。它的键值不允许重复，并且键值也不允许修改（因为键值已经有序，修改会破坏结构）

迭代器类型

constant iterators (不允许改变“所指对象之内容”者)

set 常用 *** 作

begin()、end()、empty()、size()、max_size()

swap()、insert()、erase()、clear()

find(k);			// 返回一个迭代器，指向第一个关键字为 k 的元素
count(k);			// 返回关键字等于 k 的元素的数量
lower_bound(k);		// 返回一个迭代器，指向第一个关键字 不小于(大于等于) k 的元素
upper_bound(k);		// 返回一个迭代器，指向第一个关键字 大于 k 的元素
equal_range(k);		// 返回一个迭代器 pair，表示关键字等于 k 的元素的范围

map 概述

map 的底层是 RB-Treel，它的所有元素都会根据元素的键值自动被排序，map 的所有元素都是 pair，包括键值和实值。它的键值不允许重复，它的键值也不允许修改，但是实值允许修改。

pair 结构

T1 first;	// 元素的键值
T2 second	// 元素的实值

map 常用 *** 作

begin()、end()、empty()、size()、max_size()

swap()、insert()、erase()、clear()

[]、find()、count()、lower_bound()、upper_bound()、equal_range()

multiset 概述

multiset 的特性以及用法和 set 完全相同，唯一的区别是它允许键值重复。在源码中体现就是 insert *** 作调用是 insert_equal()，而不是insert_unique()

multimap 概述

multimap 的特性以及用法和 map 完全相同，唯一的区别是它允许键值重复。在源码中体现就是 insert *** 作调用是 insert_equal()，而不是insert_unique()

2.3 hashtable 概述

hashtable 在 SGI 中主要采用开链的方式来解决哈希冲突，即由一个 vector bucket(桶)（桶内元素是节点指针类型），桶后边跟一个链表(并不采用 list 或 forwward_list )构成。
一点细节：hashtable 的 vector bucket 大小每次扩充都是扩充到大于等于它的最小质数，规定当元素数量大于 vector bucket 长度的时候，对 vector bucket 进行扩充。（Redis 字典数据结构采用的扩充方式不太相同，感兴趣也可以研究一下，之后应该会再整理一下 Redis 数据结构的底层实现）

节点结构

_hashtable_node *next;		// 一个指针，指向下一个在同一个桶下的节点
value val;					// 节点实值

迭代器

迭代器结构：

node *cur;		// 一个指针，指向该迭代器所指节点
hashtable *ht;	// 一个指针，指向 vector bucket 的首地址，目的是为了保持和 vector bucket 的连接关系

hashtable 的数据结构

hasher hash;		// hash function 的函数类比，目的是实现元素->桶的映射
key_equal equals;	// 判读键值相同与否的方法(函数或仿函数)
extractkey get_key;	// 从节点中取出键值的方法(函数或仿函数)

vector buckets;	// (vector bucket)桶对象
size_type num_elements;			// hashtable 中的元素个数

需要注意的小细节

1. insert 插入位置：如果有重复元素，插入到重复元素之后。 如果插入时对应链为空，插入元素应该插入到链的链头部分。
2. 扩充容器之后，节点所对应桶可能发生改变。

解决哈希冲突的主要方法

• 开放地址法
• 开链法
• 再哈希法
• 建立公共溢出法：将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

什么是一致性哈希？

• 非常好的讲解：白话解析：一致性哈希算法 consistent hashing
• 目的： 一致性哈希可以有效地解决分布式存储结构下动态增加和删除节点所带来的的问题(缓存失效)。
  例如原本服务器有 3 台，我一个数据假如是 6，通过对 3 取余，存储到 0 号服务器，这时候服务器总数变为 4，6%4 = 2，并不是 0，这个时候就会造成之前的缓存全部失效。
• 原理： 数据和服务器都对应在 hash 环上，数据存储到顺时针第一个遍历到的服务器上。
• 优点： 如果增加或者减少服务器数量，不会导致所有缓存失效，而是会导致一小部分缓存失效，大部分还是可以使用。
• 存在问题： hash 偏斜
• 解决办法： 主要是通过增加服务器节点数。一种是增加物理服务器节点数量。另一种是采用虚拟节点，一个物理服务器节点分成多个虚拟节点。
  这种情况的数据读写情况：缓存读写 => 虚拟节点 => 真实节点 => 读写。

2.4 unordered_map、unordered_set、unordered_multiset和unordered_multimap 四个的共同点

1. 它们的底层都是采用 hashtable。
2. 对所有关联式容器，应该使用其所提供的 find 函数来搜寻元素，会比使用 STL 算法 find() 更有效率
3. 他们和对应的 map、set、multiset和multimap 相比，元素是无序的，查找速度平均能达到 O(1)，而有序的是 O(logN)，归根到底还是底层的不同。他们封装的 *** 作是一样的，这里就不再分别单独讨论了。

如果对其他数据结构的实现感兴趣，可以看一下 Redis 底层数据结构的实现，之后会总结一篇关于 Redis 底层数据结构实现的文章。