【STL源码剖析】容器（待补充）

容器

第4章 序列式容器

根据数据在容器中的排列特性，容器可以分为序列式容器和关联式容器：

• 序列式容器：其中的元素都可序，但未必有序，数据以一串序列进行存储
• 关联式容器：数据key-value键值对进行存储
  

list与slist的区别？

• list：双向链表，list是双向迭代器
• slist：单向链表，slist是单向的 Forward Iterator

set、map、multiset、multimap的区别？
​ - set：去重、有序、数据是唯一的，底层是RBTree（因为RBTree所以是有序的）

• map：不允许重复、有序、底层是RBTree
• multiset：允许重复、有序、底层是RBTree
• multimap：可以重复插入、有序、底层是RBTree

hashtable、hash_set、hash_map、hash_multiset、hash_multimap的区别？

• hashtable：哈希表
• hash_set：特性与set完全相同，唯一的差别在于它的底层机制是hashtable，因此其无序
• hash_map：特性与map完全相同，唯一的差别在于它的底层机制是hashtable，因此其无序
• hash_multiset：特性与multiset完全相同，唯一的差别在于它的底层机制是hashtable，因此其无序
• hash_multimap：特性与multimap完全相同，唯一的差别在于它的底层机制是hashtable，因此其无序

4.2.1 vector概述

array与vector的区别

• array：静态数组
• vector：可变长数组，vector的核心在于自动扩容机制，扩容的过程包含三个步骤——配置新空间、数据移动、释放旧空间。

4.2.2 vector定义摘要

4.2.3 vector 的迭代器

vector 的迭代器需要满足operator++、operator–、operator*、operator->、operator+、operator+=、operator-=等操作，且支持随机存取，因此vector提供的是Random Access Iterators。

4.2.4 vector 的数据结构

主要是维护以下三个迭代器：

1. start：表示目前使用空间的头
2. finish：表示目前使用空间的尾，注意，finish 指向的是最后一个元素的下一个位置
3. end_of_storage：表示目前可用空间的尾

当容量不足时，vector 会扩容至当前的两倍大，如果还不够，就扩张至足够大的容量。

4.2.5 vector 的构造与内存管理：constructor，push_back

扩容并插入 insert_aux() 源码：

STL规范： 插入完成后，哨兵迭代器应指向插入的位置。

4.2.6 vector 的元素操作：pop_back,erase,clear,insert

删除操作总结（复制-移动-释放）：

1. 将删除区间后面的节点 复制 到前面来；
2. 移动 finish迭代器指向当前数据末尾
3. destory释放空间

删除源码：

插入源码：

其中， __STL_TRY 是一个宏，与下文的catch组成try-catch块来捕获异常。

插入操作主要是弄清 1. 插入点之后的元素个数小于等于新增元素个数 和 2. 插入点之后的元素个数大于新增元素个数 这两种特殊情况，其核心的思想就是把position之后的空间腾出来，因此要移动原来的元素来达到这一目标。

插入点之后的元素个数大于新增元素个数：

1. 首先将finish前移n个元素到finish后（同时改变finish的指向，这一步决定了插入点之后的元素个数必须大于新增元素个数，不然就超出左边position了）
2. 将position到原finish-n这之间的元素依次从原finish向前插（目的是腾出position后的n个位置）
3. 在position后插入这n个元素即可完成操作

插入点之后的元素个数小于等于新增元素个数：

1. 首先在finish后插入"新增元素个数减插入点之后的元素个数"个元素（同时移动finish，这一步决定了插入点之后的元素个数必须小于新增元素个数，不然就减出负值了）
2. 然后移动position到原finish位置这个区间的所有元素到现在的finish之后
3. 然后给腾出来的这段区间全部填充上需要插入的元素即可完成插入操作

4.3.1 list 概述

list（双向链表）优点： 插入、删除、元素移动都是O(1)的

4.3.2 list 的节点

list 的节点是双向的，因此 list容器 实际上是双向链表

template<class T>
struct __list_node {
    
	typedef void* void_pointer;
	void_pointer prev; // 指向前驱节点的指针
	void_pointer next; // 指向下一个节点的指针
	T data; // 存储数据
}

4.3.3 list 的迭代器

思考一下：list能和vector一样以普通指针作为迭代器吗？

实际上是不可以的，因此 list 不一定是一片连续的空间，因此要对++等运算符进行重载，由于 list 是双向链表，因此迭代器必须能够双向遍历，因此迭代器的类型是Bidirectional Iterator，即可双向移动的迭代器。

list 的迭代器设计：

其中，重点注意重载 operator-> 的写法：

pointer operator->() const {
     return &(operator*()); }

重要！

->这个符号的重载比较特殊，它的重载函数不能随便写，应该保持它的基本含义：进行成员访问，实际上，成员访问的实现是根据原生指针的->操作符来实现的。因此，假如point是一个自定义的类（而不是原生指针），那么point->重载后的operator->()函数，如果此时operator->()返回的是一个指针，那么就对这个返回的指针调用->，即它的默认的先解引用再访问成员member的功能，并将其作为point->member的最终返回结果；如果operator->()返回的仍然不是指针而是另一个自定义了->符号的类，那么继续上述的过程，直到最终能得到一个指针，对这个指针使用默认的->函数。
于是在这里，先是调用重载后的operator->()函数，它返回的 &(operator*()) 即为指向这个节点对象的指针（operator*()，这种表达是对运算符的显示调用），于是继续对这个指向节点对象的指针调用->运算符，所以迭代器才能够获得该对象的成员。

4.3.4 list 的数据结构

list 不仅是一个双向链表，还是一个环装双向链表。因为是环装的，定义指针node为元素的元素最后一个节点的下一个null节点后，node的next的节点就是首节点。

STL规范之一： 前闭后开 [start, end) ，即 end 指向的是元素最后一个节点的下一个null节点。

4.3.5 list 的构造与内存管理：constructor，push_back，insert

在容器中，都需要在template定义时传入空间配置器。list 自定义的空间配置器每次只需要配置一个节点的大小。

list 的 push_back() 底层还是调用的 insert()：

void push_back(const T& x){
     insert(end(),x); }

容器底层在实现时，每次插入都会申请一块内存，然后将要插入的值赋值到这块内存上：

4.3.6 list 的元素操作：push_front，push_back，erase，pop_front，pop_back，clear，remove，unique，splice，merge，reverse，sort

push_front 的底层实现与 push_back 差不多，都是由insert实现的。