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 去做它们类似的工作。