- 重要的C++参考网站：
cplusplus.com
CppReference
STL六大容器
Paste_Image.png
容器containers
- 容器的分类
容器的性质主要分为Sequence Container、Associative Containers、unordered Containers。STL只指出容器实现的功能，而不指出具体的实现方式。
Sequence Container
为数据按照一定序列存放的容器
Paste_Image.png
- Array前后端均固定；
- Vector后端不固定;Array和Vector可以通过索引进行访问。Vector当容量不够时会自动扩充容量，将当前容量扩大一倍，（在一块新的地方扩充容量，然后将以前的元素复制过去，非常浪费时间）
-
Deque前后端均不固定；其具体存储方式如下（即分段连续，不是物理上的连续）如果容量不够，每次扩充一个buffer：
Paste_Image.png
容器stack与queue其实是由deque来实现的。
- List与Forward_list数据不连续存放，List为一个双向环形链表，Forward_list为单项链表。 有其自己sort函数，比全局sort效率要高。
Associative Container
为数据按照一定关系进行联系的容器
Paste_Image.png
Map每一个节点分为2部分，key和value，Set只有一个部分即为key。Multiset和Multimap的key可以为多个。一般他们的实现方式为红黑树。插入元素比较费时间，但是查找非常迅速。
Unordered Container
一系列无序的元素的组合
Paste_Image.png
实现方式起始就是HashTable，一般选择Separate Chaining的形式，如下图
Paste_Image.png
插入比较迅速，查找没有Associative Container快。但是也比SequenceContainer快
allocator分配器
- 分配器是为容器分配内存空间的类。
- 除了C++ STL默认的分配器，g++编译器提供了自己的分配器，在ext文件夹下，可以通过#include <ext\...>来使用，例如
#include <ext\array_allocator.h>
这些分配器都命名在__gun_cxx的命名空间下；
例如：list<string,__gun_cxx::__pool_alloc<string>> c1;
就是使用gun独有的pool_alloc分配器（内存池分配器）。 - 分配器可以单独使用，但是比较麻烦，一般配合容器使用。
gun 2.9内各容器之间的关系，gun 4.9将其中许多非标准的容器标准化了。如下图：
Paste_Image.png
左右两部分蓝色部分为各种容器的大小，但不是包括具体元素的大小，而是控制这个容器所需的数据的大小。
