STL 的数据结构和内部实现

STL（Standard Template Library）是 C++ 泛型编程（Generic Programming）的体现，将算法从数据结构中抽象出来，以相同或相近的方式处理各种不同情形。

STL 的组件共分为六类：

Container（容器）——各种基本数据结构
Adapter（适配器）——可改变 containers、Iterators 或 Function object 接口的一种组件
Algorithm（算法）——各种基本算法如 sort、search…等
Iterator（迭代器）——连接 containers 和 algorithms
Function object（函数对象）
Allocator（分配器）

主要总结一下前两类：容器和容器适配器~

一、Container（容器）

顺序容器

1. vector

内部数据结构：连续存储，例如数组。
随机访问每个元素，所需要的时间为 O(1)。
在末尾增加或删除元素所需要时间为 O(1)，在中间或开头增加或删除元素所需时间为 O(n)。
可动态增加或减少元素，内存管理自动完成，但程序员可以使用 reserve() 成员函数来管理内存。
vector 的迭代器在内存重新分配时将失效（它所指向的元素在该操作的前后不再相同）。当把超过 capacity() - size() 个元素的插入 vector 中时，内存会重新分配，所有的迭代器都将失效；否则，指向当前插入元素以后的任何元素的迭代器都将失效。
建议：使用 vector 时，用 reserve() 成员函数预先分配需要的内存空间，它既可以保护迭代器使之不会失效，又可以提高运行效率。

2. deque

内部数据结构：连续存储或分段连续存储，具体依赖于实现（分段连续存储更常见）。
随机访问每个元素，所需要的时间为 O(1)。
在开头和结尾增加元素所需时间为 O(1)，在中间增加或删除元素所需时间为 O(n)（连续存储时）或 O(1)（分段连续存储时）。
可动态增加或减少元素，内存管理自动完成，不提供用于内存管理的成员函数。
增加任何元素都将使 deque 的迭代器失效。在 deque 的中间删除元素将使迭代器失效。在 deque 的头或尾删除元素时，只有指向该元素的迭代器失效。

3. list

内部数据结构：双向环状链表。
不能随机访问一个元素。
可双向遍历。
在开头、末尾和中间任何地方增加或删除元素所需时间都为 O(1)。
可动态增加或减少元素，内存管理自动完成。
增加任何元素都不会使迭代器失效。删除元素时，除了指向当前被删除元素的迭代器外，其他迭代器都不会失效。

4. slist

内部数据结构：单向链表。
不可双向遍历，只能从前向后遍历。
其他特性与 list 相同。
建议：尽量不要使用 slist 的 insert、erase、previous 等操作。因为这些操作需要向前遍历，但是 slist 不能直接向前遍历，所以它会从头开始向后搜索，所需时间与位于当前元素之前的元素个数成正比。虽然 slist 专门提供了 insert_after、earse_after 等函数进行优化。但若经常需要向前遍历，建议选用 list。

关联容器

1. set

内部数据结构：红黑树。
键和值相等。
键唯一（若插入的键已存在，此次插入不会成功，但也不会报错）。
元素默认按升序排列。
如果迭代器指向的元素被删除，则该迭代器失效。其他任何增加、删除元素的操作都不会使该迭代器失效。

2. multiset

内部数据结构：红黑树（一般红黑树以及其他的搜索二叉树是不允许重复键的，但这里在插入相同的 key 的时候，实现成了将 key 放在相等的 key 的右边，之后不管怎么进行插入或删除操作，后加入的 key 始终被认为比之前的大。这样就实现了一个 multiset，但根据 key 搜索的时候对于相同 key 的处理要我们自己来做）。
键可以重复。其他特点与 set 相同。

3. hash_set

内部数据结构：哈希表（数组 + 链表）。
与 set 相比较，它里面的元素不一定是经过排序的，而是按照所用的 hash 函数分派的，它能提供更快的搜索速度（当然跟 hash 函数有关）。
其他特点与 set 相同。

4. hash_multiset

内部数据结构：哈希表（数组 + 链表）。
键可以不唯一。其他特点与hash_set相同。

5. map

内部数据结构：红黑树。
键唯一。
元素默认按键的升序排列。
如果迭代器所指向的元素被删除，则该迭代器失效。其他任何增加、删除元素的操作都不会使迭代器失效。

6. multimap

内部数据结构：红黑树。
键可以不唯一。其他特点与map相同。

7. hash_map

内部数据结构：哈希表（数组 + 链表）。
与 map 相比较，它里面的元素不一定是按键值排序的，而是按照所用的 hash 函数分派的，它能提供更快的搜索速度（当然也与 hash 函数有关）。
其他特点与 map 相同。

8. hash_multimap

内部数据结构：哈希表（数组 + 链表）。
键可以不唯一。
其他特点与hash_map相同。

建议：
1）当元素的有序比搜索速度更重要时，应选用 set、multiset、map 或 multimap。否则，选用 hash_set、hash_multiset、hash_map 或 hash_multimap。
2）若经常需要在序列容器的开头或中间增加或删除元素时，应选用 list。
3）当容器作为参数被传递时，请采用引用传递方式。否则将调用容器的拷贝构造函数，其开销是难以想象的。

二、Adapter（适配器）

C++ 中定义了 3 种容器适配器，它们让容器提供的接口变成了我们常用的的 3 种数据结构：栈、队列和优先级队列。

1. stack

它可以将任意类型的序列容器转换为一个堆栈，一般使用 deque 或 list 作为支持的序列容器。
元素只能后进先出。
不支持遍历操作。

2. queue

它可以将任意类型的序列容器转换为一个队列，一般使用 deque 或 list 作为支持的序列容器。
元素只能先进先出。
不支持遍历操作。

3. priority_queue

它可以将任意类型的序列容器转换为一个优先队列，一般使用 vector 作为底层存储结构。
只能访问第一个元素，不支持遍历操作。
第一个元素始终是优先级最高的元素。

建议：当需要 stack、queue 或 priority_queue 这样的数据结构时，直接使用这些对应的容器类，不要使用 deque 去做它们类似的工作。