关联式容器

关联式容器概述

关联式容器的每个元素都有一个key值一个value值。当元素被插入到关联式容器时，容器内部结构便依照key值大小，按照某种规则将该元素置于适当位置。

关联式容器没有头尾之分，自然也就没有push_back()、pop_front()等操作。

关联式容器的内部结构只有两种：

以红黑树（RB-tree）为底层结构:
- set
- map
- multiset
- multimap
以哈希表（Hash-table）为底层结构:
- unordered_set
- unordered_map
- unordered_multiset
- unordered_multimap

Tree的导览

节点的大小：该节点及其所有子节点的节点总数；
路径长度：A节点到B节点的唯一路径经过的边数；
节点的高度：该节点到其最深子节点（叶节点）的路径长度；
节点的深度：根节点到该节点的路径长度

二叉搜索树

二叉搜索树的性质：左子树的节点值 < 根节点的值 < 右子树的节点值

查找：找最小就一直往左走，找最大就一直往右走；
插入：从根节点开始，遇到大的就向左，遇到小的就向右，一直到尾端，即为插入点。
删除：分两种情况：
- 目标节点只有一个子节点，直接将其子节点连至其父节点。
- 目标节点有两个子节点，以右子树中的最小值取而代之即可。

平衡二叉搜索树

所谓平衡，即没有任何一个节点过深。

平衡二叉搜索树是加了“额外平衡条件”的二叉搜索树。

平衡二叉搜索树比一般的二叉搜索树要复杂，插入节点和删除节点的平均时间也更长，但是它们可以避免极难应付的最坏（高度不平衡）情况，而且由于它们总是保持着某种程度的平衡，所以元素的查找时间平均而言就比较少。

平衡二叉搜索树相较一般的二叉搜索树：

查找更快；

插入和删除节点较慢。

常见的平衡二叉搜索树有AVL树、红黑树。

AVL树

为了确保整棵树的深度为O(logN)，AVL树的“额外平衡条件”是：

任何节点的左右子树高度相差最多为1。

最佳的平衡条件肯定是每个节点的左右子树有相同高度，但这个条件过于严苛，很难保证插入新元素而又保持这种平衡。所以AVL树退而求其次，允许每个节点的左右子树高度相差1，虽然这个条件会把平衡弱化，但仍能保证“对数深度”平衡状态。

插入新节点后，可能会有节点违反平衡条件，且只有插入点到根节点这条路径上的各节点可能违反平衡状态。只要调整其中最深的那个节点，便可使整棵树重新获得平衡。

假设该最深节点为X，由于节点最多有两个子节点，而所谓“平衡被破坏”意味着X的左右子树的高度相差2，因此可以分为四种情况：

插入点位于X的左子节点的左子树——左左；
插入点位于X的左子节点的右子树——左右；
插入点位于X的右子节点的左子树——右左；
插入点位于X的右子节点的右子树——右右。

左左和右右彼此对称，称为外侧插入，可用单旋转解决；左右和右左彼此对此，称为内侧插入，可用双旋转解决。

单旋转

对于外侧插入，以左左为例，情况肯定是这样的，X的左子节点的左子树因新节点插入而成长了一层，导致X的左子树比右子树深度多2.

调整方法（左左为例）：将X的左子节点提起来，使X自然下滑，并将X的左子节点的右子树挂到下滑后的X的左侧，即可重新获得平衡。

这么做的原因呢？

二叉树的规则使我们知道，X值肯定大于X的左子节点值，所以X必须成为调整后的X的左子节点的右子节点；
同时，X的左子节点的右子树的所有节点值肯定介于X和X的左子节点的值之间，所以X的左子节点的右子树应该落在调整后的X的左侧。

可以看出，左左的单旋转是一次顺时针旋转；右右的单旋转对称，是一次逆时针旋转。

双旋转

对于内侧插入，以左右为例，单旋转无法解决问题。

调整方法：双旋转利用两次单旋转完成：

先对X的左子节点和X的左子节点的右子节点做一次单旋转；
再对X和第一次调整后的新的X的左子节点（原来的X的左子节点的右子节点）做一次单旋转。

AVL树的平衡条件仍较为严苛，对于set和map来说，需要频繁的插入和删除，若用AVL树作底层结构，会影响性能。AVL树只适合查找较多而插入删除操作较少的情况。

RB-tree(红黑树)

红黑树不仅是二叉搜索树，而且满足以下规则：

每个节点不是红色就是黑色；
根节点是黑色；
如果节点为红，其子节点必须为黑；(即父子节点不得同时为红)；
任一节点至NULL的任何路径，所含黑节点树必须相同。

根据规则4，新增节点必须为红；
根据规则3，新增节点的父节点必须为黑。

当新节点按照二叉搜索树的规则到达插入点，却未能符合上述条件时，就必须调整颜色和旋转树形。

新插入节点导致破坏红黑树的规则肯定是破坏3，即父子节点同时为红了。 NULL节点可视为黑色。

设新节点为X，其父节点为P，伯父节点为S，祖父节点为G，曾祖父节点为GG。根据规则4，X必为红，若P亦为红（这就违反了规则3，需要调整），则G必为黑（因为原为RB-tree，得符合规则3）。那么，根据X的插入位置及外围节点（S和GG）的颜色，可分为以下四种情况：

S为黑且X为外侧插入。对这种情况，只需对P、G做一次单旋转，并更改P、G颜色，即可重新满足红黑树的规则3;
S为黑且X为内侧插入。对这种情况，必须先对P、X做一次单旋转，并更改G、X颜色，再将结果对G做一次单旋转，即可重新满足规则3；
S为红且X为外侧插入。对这种情况，先对P、G做一次单旋转，并改变X的颜色。此时如果GG为黑，一切搞定。若GG为红，见情况4；
S为红且X为外侧插入。对这种情况，先对P、G做一次单旋转，并改变X的颜色。如果此时GG为红，还得持续往上做，直到不再有父子连续为红的情况。

以红黑树为底层结构的关联容器

set

set的特性是，所有的元素都会根据key值自动被排序。

set的key值就是value值，value值就是key值。set不允许两个元素有相同的key值。

不能通过set的迭代器更改set的元素值。因为set元素值就是其key值，关系到set元素的排列规则。如果任意改变set元素值，会严重破坏set组织。set的迭代器其实被定义成底层红黑树的const迭代器了，杜绝写入操作。

对set进行插入和删除操作后，之前的迭代器不会失效。（当然，被删除元素的迭代器肯定是失效了）

map

map的特性是，所有元素会根据各自的key值自动被排序。

map的元素是pair类型，同时拥有key值和value值。pair的第一元素被视为key，第二元素被视为value。map不允许两个元素有相同的key值。

通过map的迭代器可以修改map元素的value值，不可以修改map的key值，因为key值关系到map的排列规则，任意更改map元素的key值会破坏map组织。

对map进行插入和删除操作后，之前的迭代器不会失效。（当然，被删除元素的迭代器肯定是失效了）

multiset

multiset的特性及用法与set完全相同，唯一的差别在于它允许key值重复。

multimap

multimap的特性及用法与set完全相同，唯一的差别在于它允许key值重复。

哈希表（Hash-table）

二叉搜索树具有对数平均时间的表现建立在“输入的数据有足够的随机性”这样一种假设上。

哈希表在查找、插入、删除等操作上具有“常数平均时间”的表现，且这种表现是以统计为基础的，不需依赖输入元素的随机性。

哈希函数：将哈希表中元素的键值映射为元素存储位置的函数。

$$ Address = Hash(key)$$

哈希冲突：可能出现不同的元素被映射到相同的位置。

比如采用求余的哈希函数的话，2和5对3求余都是2，这样2和5就都存到位置2上了，这就是哈希冲突。

解决哈希冲突的方法：

线性探测
二次探测
开链法

以哈希表为底层结构的关联容器

红黑树有自动排序功能，哈希表没有。所以以哈希表为底层的关联容器在C++标准里都以unordered_开头。

unordered_set

与set一样，unordered_set的key值就是value值，value值就是key值。

unordered_map

与map一样，unordered_map的元素是pair类型，同时拥有key值和value值。pair的第一元素被视为key，第二元素被视为value。

unordered_multiset

unordered_multiset与multiset的特性完全相同，唯一的差别在于其底层是哈希表，所以其元素不会被自动排序。

unordered_multimap

unordered_multimap与multimap的特性完全相同，唯一的差别在于其底层是哈希表，所以其元素不会被自动排序。

容器概述

C++标准里提供了以下容器或容器配接器：

序列式容器：
- array
- vector
- list
- deque
- forward_list
关联式容器
- set
- map
- multiset
- multimap
不定序关联容器
- unordered_set
- unordered_map
- unordered_multiset
- unordered_multimap
配接器
- stack
- queue
- priority_queue

序列式容器

array

array是静态连续空间，一经配置，大小不可改变。

就是数组，除了空间的灵活性不足，其他与vector很像。用的也比较少，一般都用vector了，这里就不多说了。

vector

vector的数据安排与操作方式，与array很相似。二者唯一的差别在于空间的运用的灵活性。

array是静态空间，一旦配置不能改变；
vector是动态空间，随着元素加入，内部机制会自行扩充空间以容纳新元素。

vector维护的是连续线性空间，其迭代器就是普通指针。

1

vector<int>::iterator iter;

那么iter其实就是int*类型。

两个迭代器start和finish之间是连续空间中目前已被使用的空间，end_of_storage指向整块连续空间的尾端。

为了降低频繁空间配置带来的成本开销，vector实际配置的大小会比客户需求的更大一些，以备将来可能的扩充。这便是capacity的概念。

[start,finish]是size();
[start, end_of_storage]是capacity();
[finish, end_of_storage]是备用空间。

一旦size() == capacity(),便是满载。下次再有新增元素，整个vector就要另觅他所了。“另觅他所”的过程会经历“重新配置大空间，元素移动，释放原空间”这一系列动作，工程浩大。

所谓动态增加大小，并不是在原空间之后接续新空间（因为无法保证原空间之后有可供配置的空间），而是以原空间大小的两倍另外配置一块较大空间，然后将原内容拷贝过来，然后才开始在原内容后边构造新元素，并释放原空间。

因此，对vector的任何操作，一旦引起空间重新配置，指向原vector的所有迭代器就都失效了，这是一个经常犯的错误，务必小心。

list

list是环状双向链表。它的好处在于每次插入或删除一个元素，就配置或释放一个元素空间，与vector相比，list对空间运用更加精准，绝不浪费。且对于任何位置的元素插入或移除，list永远是常数时间。

vector和list适用场景与以下有关：

元素多寡
元素的构造复杂度（有无non-trival copy constructor， non-trival copy assignment operator）
元素存取行为的特性

list的节点结构如下：

1
2
3
4
5
6
7


template <class T>
struct __list_node{
    typedef void* void_pointer;
    void_pointer prev;
    void_pointer next;
    T data;
};

由于list的内存空间无法保证是连续的，所以它的迭代器不再是普通指针。list的迭代器必须有能力指向list节点，并进行正确的递增、递减、取值、成员存取等操作。

list的操作大多不会使迭代器失效，即便是删除操作，也只有指向被删除元素的那个迭代器失效。

由于list是一个环状双向链表，所以它只需要一个指针，便可以完整遍历整个链表。

对于insert操作，新节点将位于哨兵迭代器（标示出插入点）所指节点的前方，这是STL对插入操作的标准规范。

deque

vector是单向开口的连续线性空间，deque则是一种双向开口的线性连续空间。所谓双向开口，即可以在首尾两端分别做元素的插入和删除操作。

deque其实是动态地以分段连续空间组合而成。但是这些分段的连续空间，在用户看来确实一整块连续空间，这其实是deque做出的假象。这种假象由deque的中控器map（注意，不是STL中的map容器）负责维持。

这个map可以理解为映射，它是一个指针，指向一小段连续内存空间，这块空间中的每个元素又都是一个指针，每个指针都指向deque的分段连续空间中的某一段。默认每一段是512字节。

forward_list

forward_list是单向链表。

前边说了，对于insert操作，新节点将位于哨兵迭代器（标示出插入点）所指节点的前方，这是STL对插入操作的标准规范。

但是forward_list作为单向链表，它没有什么方便方法回头定出前一个位置，它只能从头找起，所以除了forward_list起点处附近的区域外，在其他位置insert()或erase()就很慢，对此，forward_list特别提供了insert_after()和erase_after()。

同样出于效率考虑，它不提供push_back()，只提供push_front()。

Adapter（配接器）

stack

stack是先进后出（FILO）的数据结构。他只有一个出口，除了最顶端元素外，没有其他方法获得stack的其他元素。即stack是不允许有遍历行为的，自然也就没有迭代器了。

STL中的stack其实不算是container，而是adapter，因为其底层默认是deque，把deque的头端封闭，便形成一个stack。

具有“修改某物接口，形成另一种风貌”之性质者，谓之adapter。

除了deque，list也是双向开口的，所以list也可以做stack的底层结构。

queue

queue是先进先出（FIFO）的数据结构。它有两个出入口，但都是被限制的，尾端只进不出，头端只出不进。除了尾端进，头端出之外，没有其他方法存取queue的其他元素，即queue也是不允许遍历的，自然也就没有迭代器了。

queue也是一种adapter，它同stack一样，默认以deque作为底层结构，list同样也可以做其底层结构。

封闭deque的头端入口和尾端出口，就成了一个queue。

priority_queue

priority_queue是拥有权值观念的queue。

所谓拥有权值观念，可以理解为有序的，其内的元素并非按照加入的次序排列，而是按照元素的权值排列，权值最高者排在最前边。

默认状态下，priority_queue是用一个大根堆（max-heap）来完成，而大根堆是一个以vector表现得完全二叉树。

大根堆：max-heap，父节点值大于或等于子节点值的完全二叉树；小根堆：min-heap，父节点值小于或等于子节点值的完全二叉树。

所以，priority_queue是以vector为底层结构，辅以heap处理规则来实现的，所以它也是一种adapter。

priority_queue也不允许遍历，自然也没有迭代器。