STL六大组件与底层原理

II. list

数据结构：双向链表

特点：

1. 非连续存储，不支持随机访问。
2. 在任意位置的插入删除都是O(1)的效率。
3. 访问头尾效率O(1)，其他为O(n)。

III. deque

数据结构：双端队列(Double End Queue)

deque的中控器存储每个内存块的指针，每个内存块的cur记录当前数据的位置，first和last记录内存块的起始和末尾。

特点：

1. 支持随机访问，但由于不是顺序存储，所以性能较vector差一些。
2. 支持头尾的快速插入删除，但是中间的插入删除性能较差。

2、关联容器

I.map/set

数据结构：红黑树

特点：

1. map存储键值对，set存储键。
2. 增删查改效率为log(n)。
3. 节点根据键值进行按序存储。
4. 不允许相同的键值出现。
5. **map重载了operator[]**用于获取键对应的值。
6. 键不可修改，但是键值可以修改。

II.multimap/multiset

数据结构：红黑树

特点：

1. multimap存储键值对，multiset存储键。
2. 增删查改效率为log(n)。
3. 节点根据键值进行按序存储。
4. 允许相同的键值出现，但不保证它们之间的相对顺序。
5. multimap没有重载operator[]，因为键允许重复。
6. 键不可修改，但是键值可以修改。

III. unordered_map/unordered_set

数据结构：哈希表

特点：

1. unordered_map存储键值对，unordered_set存储键。
2. 增删查改的平均时间复杂度为O(1)。
3. 键值的存储是无序的。
4. 键必须是唯一的，不允许重复。
5. unordered_map重载了operator[]用于获取键对应的值。

3、容器适配器

I. stack

数据结构：栈，默认封装deque的接口，封装容器可根据传入的模板参数改变

特点：

1. 后进先出
2. 只允许从栈顶增删查数据。

II. queue

数据结构：队列，默认封装deque的接口，封装容器可根据传入的模板参数改变

特点：

1. 先进先出
2. 只允许从队头删查数据，队尾增数据。

III. priority_queue

数据结构：堆，默认封装vector的接口，封装容器可根据传入的模板参数改变

特点：

1. 最值存储在堆顶。
2. 只允许从堆顶增删查数据，不允许改数据。

容器迭代器失效问题

1. 对于顺序容器，如vector，删除前面的元素会导致后面元素的迭代器失效，但是可以通过erase获取到被删除元素的下一个元素的新迭代器。此外，增加元素可能会导致整个容器的扩容，从而使所有迭代器都失效。

   对于list，由于是非顺序存储，因此增删一个节点不会使其他节点的迭代器失效。

   对于deque，如果增加元素导致扩充，则会引起所有迭代器失效，因为迭代其内部有指向中控器的指针。其他情况下，对于头尾的插入删除，不会引起迭代器失效，但是对于中间元素的插入删除，会引起对应位置前或后的元素移动，具体哪些迭代器会失效根据当时的内存分布而定。

2. 对于关联容器，如map/set/multimap/multiset，底层使用红黑树，是非顺序存储，所以增删一个节点不会使其它迭代器失效。但是它们的erase不会返回下一个节点的迭代器。

   但是对于unordered_map/unordered_set，底层使用哈希表，增加节点可能会导致整个表的重映射，从而导致所有迭代器失效。

空间配置器

空间配置器是用来实现内存空间分配的工具，与容器联系紧密，每一种容器的空间分配都是通过空间分配器alloctor实现的。

1、空间配置器原理

空间配置器有两级结构，第一级用于处理128字节以上的大内存，其余小内存由第二级处理。

I. 第一级

直接使用malloc和free向系统申请和释放内存。

II. 第二级

维护了一个内存池，内存池中存有16种不同大小的内存块(128/8)，用于适应不同的内存需求。

2、空间配置器的优势

1. 内存池的介入能够极大地提高内存分配与回收的效率。
2. 更方便维护和管理内存块。