STL各容器的实现细节

vector

连续型空间（具有类似数组的特性），仅允许在末尾进行插入操作，并且其容量能够持续扩展。值得注意的是，其容量的增长展现出显著优势。

增长三部曲：

1. 另觅更大空间
2. 将原数据复制过去
3. 释放原空间三部曲

list

环形双向链表

deque

deque空间被设计为分段连续的结构，并故意营造出一种令人误以为其整体呈现完全连贯效果的现象。每个元素都充当了一个指向器角色，在其指向的位置上存储了另一段真正实现上相互衔接且完全连贯的空间（称为缓冲区）。然而实际上只有这些缓冲区才是真正的数据存储场所

关联容器===============================================

二叉搜索树：任何结点大于左子树，小于右子树，

平衡二叉搜索树：查找的时间在（logN）

红黑树：规则如下

1. 每个节点只能是红色或黑色。
2. 根节点必为黑。
3. 若一个节点为红，则其子节点必为黑。
4. 对于任一节点而言，在通