~~1C++ STL 容器是使用频率超高的基础设施，只有了解各个容器的底层原理，才能得心应手地用好不同的容器，做到用最合适的容器干最合适的事情^[1]。~~看了文章[1]，可惜其中对容器方法的底层几乎没有提及，那就自己边查边写吧。本文大部分内容来自cplusplus.com/reference/ 。

C++ STL(Standard Template Library)中的容器主要有array, vector, deque, list, forward_list, queue, priority_queue, stack, map, multimap, set, multi_set, unordered_map, unordered_multimap, unordered_set, unordered_multiset 这16种。

Array

容器属性：顺序容器（支持随机访问）

内存空间：连续内存空间

容器尺寸：固定大小

头文件：#include <array>

类模板头：template < class T, size_t N > class array;

声明方式： std::array<int,110> arr { };

如果array未初始化，会随机分配值。

数组大小固定，不支持添加或删除元素等改变大小的操作，所有的元素严格按照内存地址线性排列。

此外C++中的数组要于C风格数组，也就是使用[]操作符声明的数组区分开。C++的数组支持begin(), end(), front(), back(), at(), empty(), data(), fill(), swap() 等标准接口，但是C风格数组不支持这些方法。

front() ：返回数组第一个元素的引用。如果数组为空，调用front() 是未定义行为；否则直接通过索引访问第一个元素。时间复杂度O(1)。
back() ：返回数组最后一个元素的引用，通过索引直接访问最后一个元素，其他同上。
at(i)：返回数组中i位置元素的引用。如果超出数组尺寸，会抛出out_of_range异常。时间复杂度O(1)。
empty() ：返回bool类型结果，判断数组是否为空。时间复杂度O(1)。
data() ：返回数组第一个元素的指针，即数组的地址。时间复杂度O(1)。
fill(a) ：将数组所有内容填充为指定内容a。底层使用一个循环，遍历每个元素，然后将当前元素赋值为a。时间复杂度O(n)，n为元素数量。
swap(arr) ：将两个数组的元素进行交换，要求两数组类型和尺寸都必须相同，否则编译不通过。和其他容器不同的是，数组的swap() 方法交换了各个元素的值，但是容器中所存的元素的地址没有交换。底层使用一个循环遍历数组元素，然后swap()函数交换当前数组和另一个数组中对应位置的元素。要注意swap()之后迭代器，引用和指针都仍然有效。先说迭代器，由于内存地址没有变化，只是交换了元素内容，因此迭代器仍然指向相同的内存地址；引用一旦绑定就不会改变，即使交换了元素，引用仍然指向最初绑定元素的位置；指针和迭代器类似，仍然指向原来的地址。时间复杂度O(n)。举例：

std::array<int, 3> a = {1, 2, 3};
std::array<int, 3> b = {4, 5, 6};

int& ref_a = a[0]; // 绑定到 a 的第一个元素
int* ptr_b = &b[1]; // 指向 b 的第二个元素

// 交换 a 和 b 的元素
a.swap(b);

// 现在 ref_a 仍然绑定到 a[0]，但 a[0] 的值已经变成了 4
// ptr_b 仍然指向 b[1]，但 b[1] 的值已经变成了 2

vector

容器属性：顺序容器（支持随机访问）

内存空间：连续内存空间，使用内存分配器动态管理内存

容器尺寸：动态调整大小

头文件：#include <vector>

类模板头：template < class T, class Alloc = allocator<T> > class vector;

声明方式：std::vector<int> vec;

在底层上，vector 使用动态分配的 array，也就是说底层用array实现，当现有空间无法满足需求时，会重新分配（reallocate）一个更大的 array 并把所有元素移动过去。因此，vector 的 reallocate非常耗时。所以，每次 reallocate时会预留更多空间，也就是说，vector的capacity()通常会大于size()。当重新分配空间时，一般会预留出150%-200%的空间，一般200%空间，算法导论里证明这样均摊时间最少^[4]。

operator[] ：和数组一样，可以直接通过[]访问元素，时间复杂度O(1)。
at(i) ：vector.at(i)等同于vector[i] 。区别在于，vector[i] 效率（可能）更高，但不会做越界访问保护和异常抛出，需要自己做越界检查。时间复杂度O(1)。
front() 和back() ：分别返回第一个和最后一个元素。如数组一样，空vector会导致未定义行为。时间复杂度O(1)。
data() ：返回指向容器中第一个元素的指针。时间复杂度O(1)。
push_back(i)：在容器的尾部插入元素i，底层通过拷贝或者移动的方式，如果是拷贝，事后自行销毁先前创建的元素。调用push_back()时，若当前容量不够放入新元素，即capacity()==size()，vector会重新申请一块内存，把之前vector内存里的元素拷贝到新内存中，然后把push_back的元素拷贝到新的内存中，最后要析构原有的vector并释放原有内存。触发reallocate每次复制的时间复杂度O(n)，注意此时迭代器会失效，因为分配了新的内存，不触发时为O(1) ，均摊下来时间复杂度O(1)。根据代码^[5]：
```
#include <iostream>
#include <vector>
int main() {
	std::vector<int> v;
	int last = 0;
	for (int i = 1; i <= 1e5; i++) {
		v.push_back(1);
		if (last != (int)v.capacity()) {
			std::cout << v.capacity() << " ";
			last = v.capacity();
		}
	}
}
```
运行时输出 1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 ，都是2的次幂，因此每次push_back 的花销为：
c_i= \left\{ \begin{aligned} i && i-1为2的幂 \\ 1 && 其他情况 \\ \end{aligned} \right.

那么有：

\sum_{i-1}^n c_i \leq n + \sum_{j=0}^{\lg n}2^j < n+2n = 3n

也就是说，有n次插入操作，总时间复杂度为O(3n), 单次均摊时间复杂度为O(3) 。

在算法导论中，\lg一般以2为底，因为以2，10或e为底，最终结果只差一个常数，没有区别。关于求和那里为什么得出2n，可以参考几何级数（等比数列）的求和：

\sum_{j=0}^{k}r^j=\cfrac{r^{k+1}-1}{r-1}

关于扩容次数的解释^[6]，这里的倍增因子为m（此处为2），也就是容量到达上限后，新空间容量增长m 倍，假设扩容k 次，那么有1+m+m^2+...+m^k \geq n，根据上面的公式，化简为：

m^k -1 \geq n \times(m-1) \rarr k=\log_m n \times(m-1) = \log_m n + \log_m(n-1) \approx \log_m n

在这里扩容次数\log_m n就变成了\lg_2 n即\lg n。

pop_back()：删除最后一个元素。pop_back 之后end迭代器以及其他对已删除元素的引用和指针都会失效，但是要注意删除元素时capacity()并不会减少。时间复杂度O(1)。
insert() ：插入元素。可以在指定位置插入一个或者多个，也可以在指定区间插入元素。底层是把当前要插入元素位置后面的元素向后移动，然后把待插入元素插入到相应的位置，需要调用类的构造函数和移动构造函数，时间复杂度O(n)。

emplace()：插入元素，但是emplace() 每次只能插入一个元素，而不是多个。效率相比insert() 更高，只需要调用构造函数，避免产生不必要的临时变量。时间复杂度O(n)。
erase()：通过迭代器删除某个或某个范围的元素，并返回下一个元素的迭代器。底层在不删除最后一个元素的情况下，把这个元素后面的所有元素向前移动一位，这是一个拷贝的动作，然后把容器结束位置向前移动一位，并返回指向当前位置的迭代器。时间复杂度O(n)。

clear()：清空容器，size()==0，但capacity() 不变。时间复杂度O(n)。底层操作可以看STL源码，简单来说就是通过destroy 函数，destroy 函数内部进行遍历析构。

// 清除全部元素。注意并未释放空间，以备可能未来还会新加入元素。
void clear() { erase(begin(), end()); }
//调用vector::erase的两迭代器范围版本
	iterator erase(iterator first, iterator last) {
    	iterator i = copy(last, finish, first);
        //finish在vector中定义表示目前使用空间的尾，相当于end（），clear调用时last=finish
    	destroy(i, finish);	//全局函数，结构的基本函数
    	finish = finish - (last - first);
    	return first;
}

swap()：交换两个vector的内容，包括它们的start（指向第一个元素），finish（指向最后一个元素的下一个位置），和 end_of_storage（指向已分配内存的末尾）。两个容器可以尺寸不一致。底层是直接交换两个vector的地址，时间复杂度O(1) 。
assign()：分配新的内容至vector中，以覆盖现有内容(清除以前的内容)并修改其size()。底层先检查存储空间是否足够，如果不够就reallocate，然后清除掉之前的内容，再将新的内容赋值到当前vector，时间复杂度O(n)，取决于assign了多少个元素。
emplace_back()：在容器的尾部插入元素，和push_back不同。具体区别是push_back调用了一次构造函数，还调用了一次拷贝构造函数，但是emplace_back 则是直接在容器尾部创建这个元素，少了一次对象的构造和析构。均摊时间复杂度O(1)。

Vector释放内存的方法

上面已经说过，clear() 不会导致vector容量的变化，内存空间也就不能通过这种方式释放。先看看什么情况下需要释放^[6]

vector是局部变量的不用释放。
采用智能指针创建的vector不用释放。
动态分配出来的vector，但数据量不大，对内存影响很小不用释放，但未来重新使用这个vector，插入大量新元素，用swap清空比较好。
动态分配出来的vector且包含大数据集的需要。

可以用两种方法：

clear() + shrink_to_fit() ，shrink_to_fit()是C++11增加的函数，作用是释放掉未使用的内存。
swap() ：如 vector<int>().swap(v) 创建一个局部临时变量，仅在当前行有效。

deque

容器属性：顺序容器（支持随机访问）

内存空间：分段连续内存空间，使用内存分配器动态管理内存

容器尺寸：动态调整大小

头文件：#include <deque>

类模板头：template < class T, class Alloc = allocator<T> > class deque;

声明方式：std::deque<int> myDeque;

deque(double-ended queue)，是一个可以在首尾两端进行动态增删的顺序容器。如果说 vector是连续的，deque则是分段连续。deque会维护不同 array之间的关联信息，用户无需关心分段这件事。deque在 reallocate时，只需新增/释放两端的 storage chunk 即可，无需移动已有数据（vector的弊端），尤其在数据规模很大时，效率提升明显。但 deque并不适合遍历，因为每次访问元素时，deque底层都要检查是否触达了内存片段的边界，会造成额外开销。deque的核心优势是在双端都支持高效（时间复杂度O(1)）的增删操作，程序员选择使用 deque时必须有双端操作的需求。^[1]。deque的迭代器并不是普通指针，其底层实现非常复杂。因此，除非必要（双端操作），尽可能选用vector。对deque进行排序操作，可将deque先完整复制到一个vector上，对vector排序后，再复制到deque^[7]。

push_front()：在队列最前面添加一个元素，通过拷贝或者移动的方式添加。时间复杂度O(1)。

push_back()：在队列末尾添加一个元素。时间复杂度O(1)。
emplace_front()：在队列最前面添加一个元素。时间复杂度O(1)。
emplace_back() ：在队列末尾添加一个元素。和vector 类似，emplace_back 也只调用了构造函数（就地构造），而没有移动构造函数和拷贝构造函数，因此效率更高。时间复杂度O(1)。
resize()：改变容器中可存储元素的个数，如果重新扩展的容量小于现在的容量，多出的将会丢失，如果大于现在的容量，将会在现有容量的基础上进行扩充，并以0填充默认值。时间复杂度O(n)。
pop_front()：删除队列的第一个元素。时间复杂度O(1)。
pop_back()：删除队列末尾的元素。时间复杂度O(1)。
insert()：指定位置插入一个或多个元素。先检查容量，如果没有就先扩容，然后将插入点之后的所有元素向后移动，最后插入新元素。最好情况下时间复杂度O(1)，比如在尾部插入；最坏情况下比如在头部插入，时间复杂度O(n)。

queue

容器属性：顺序容器（支持随机访问）

内存空间：分段连续内存空间，使用内存分配器动态管理内存

容器尺寸：动态调整大小

头文件：#include <queue>

类模板头：template <class T, class Container = deque<T> > class queue;

声明方式：std::queue<int> myQueue;

FIFO设计，只能从一端插入，从另一端删除。

priority_queue

这个队列叫做优先级队列。它的特点是严格弱序，即 priority_queue 保证容器中的第一个元素始终是所有元素中最大的。默认情况下，priority_queue 使用 vector 作为底层容器。

list

容器属性：顺序容器（支持顺序访问，不支持随机访问）

内存空间：离散内存，使用内存分配器动态管理内存

容器尺寸：能够添加元素。

头文件：#include <list>

类模板头：template < class T, class Alloc = allocator<T> > class list;

声明方式： std::list<int> mylist;

由于list的底层是双链表，其支持在任意位置快速插入和删除元素，且支持双向遍历。双链表把各个元素保存在彼此不相干的内存地址，但是每个元素都会与前后相关联。如果想要访问某个元素，必须从一个已知元素朝一个方向（前后都行）遍历，直到需要的元素。因为需要保存元素间的关联信息，list需要更多内存空间。

下图展示了list双向链表是如何存储元素的。list通过指针来描述元素间的前后关系，每个元素都包含两个指针，注意第一个元素的前向指针和最后一个元素的后向指针都是null，因为没有元素。

特别的是，list有两种迭代器， begin()和end()，以及rbegin()和rend() 。begin 指向第一个元素，end 指向最后一个元素的下一个位置，即null。rbegin 指向最后一个元素，rend 指向第一个元素。这两种迭代器不能混用。

list结构.jpeg

既然list不支持随机访问，也就不提供下标操作符和at()函数。

push_back(const T& val) ：在容器尾部插入一个元素。底层上首先分配内存存储新元素，随后在list最后插入（若list为空则为第一个元素），更新链表最后的next指针，使之指向新元素。最后更新链表大小。时间复杂度O(1)。
push_front(const T& val) ：在容器头部插入一个元素。底层和push_back 差不多，只是需要更新链表的最前向的指针，指向新元素。时间复杂度O(1)。
emplace_back()：在容器尾部直接生成一个元素。和 push_back() 的功能相同，但效率更高。时间复杂度O(1)。
insert()：在指定迭代器的位置插入元素。在底层上，首先获取迭代器it指向的当前元素及其前一个元素。然后创建一个新元素。随后将前一个元素的next指向新元素，将新元素的prev指向前一个元素，至此新元素和前面元素的链接完成。然后将新元素的next指向当前元素，并将当前元素的prev指向新元素。至此新元素和当前元素的链接完成。时间复杂度O(n)。
pop_front() ：删除容器最前面的元素。底层上先检查容器是否为空。然后将第二个节点（如有）的prev设为null，将list头部指针删除。时间复杂度O(1)。
pop_back()：删除容器尾部的元素。时间复杂度O(1)。
erase()：删除指定位置或位置区间元素。底层上遍历链表，如果找到了要删除的元素，更新要删除的元素前面元素的next和后面元素的prev，然后删除当前元素。时间复杂度O(n)。
resize() ：如果小于当前size，容器会删除超出的元素；如果大于当前size，容器会在末尾插入指定元素，如不指定，执行默认初始化。一般认为时间复杂度O(n)。
swap()：交换两个类型相同的list的元素。底层上直接交换头部节点和尾部节点的指针。时间复杂度O(1)。
reverse()：反转list。通过迭代的交换所有元素的prev和next实现。时间复杂度O(1)。
assign()：将新内容分配给容器，替换掉当前内容。底层通过先清除掉现有内容，然后把新内容插入。时间复杂度O(n)。

forward_list

容器属性：顺序容器（支持顺序访问，不支持随机访问）

内存空间：离散内存，使用内存分配器动态管理内存

容器尺寸：能够添加元素。

头文件：#include <forward_list>

类模板头：template < class T, class Alloc = allocator<T> > class list;

声明方式： std::forward_list<int> values;

和list容器的区别在于，forward_list 是单链表。下图描述了单链表和双链表的区别。这两个容器的特性相近，擅长在任何位置插入或删除元素，但是访问元素的效率比较低。由于forward_list 只能从前向后遍历，不支持反向遍历，因此只有前向迭代器，没有rbegin()和rend() 之类的成员函数。相比list ，forward_list 使用单链表使用内存空间更少，空间利用率更高。

map

容器属性：关联容器，元素类型<key, value> ，其中key唯一，元素有序存储

内存空间：使用内存分配器动态管理内存

容器尺寸：能够添加元素

头文件：#include <map>

类模板头：typedef pair<const Key, T> value_type;

声明方式：std::map<char,int> mymap;

map底层是红黑树，具有高效的查找、插入和删除操作。元素类型是由 key 和 value 组成的 std::pair，实际上 map 中元素的数据类型就是 typedef pair<const Key, T> value_type;

at(const Key& k)：如果map中存在键k，则返回与键k关联的值的引用。时间复杂度O(\log{n})。比起operator[]，在找不到键时，会创建一个新的键值对，其中键是k，值是值类型的默认构造值，然后返回这个新插入值的引用。因此，operator[]不会抛出异常，但可能会导致意外的键值对插入。
emplace()：插入一个键值对，这个键值对是就地构造的，避免了创建临时对象。如果插入的key已经存在，那么不会进行任何操作并返回 false。时间复杂度O(\log{n})。
erase()：通过迭代器或者键来删除指定键值对。删除指定迭代器的键值对，时间复杂度O(1)。删除指定键的键值对，时间复杂度O(\log{n})。删除指定范围的键值对，时间复杂度O(n)。
insert()：若待插入元素的键值 key在 map中不存在，则 insert 插入成功，并返回插入后元素的迭代器和 true。若待插入元素的键值 key在 map 当中已经存在，则插入失败，并返回 map中键值为 key 的元素的迭代器和 false 。时间复杂度O(\log n)。
[] operator：底层是用insert实现的。时间复杂度O(\log n)。
find()：在容器中寻找值为k的元素，返回该元素的迭代器。否则，返回map.end()。时间复杂度O(\log n)。

multimap

容器属性：关联容器，元素类型<key, value> ，允许不同元素key相同

内存空间：使用内存分配器动态管理内存

容器尺寸：能够添加元素

头文件：#include <map>

multimap与 map底层原理完全一样，都是红黑树，区别在于multimap 允许同一个key拥有多个value。向 multimap中新增元素时，multimap 只会判断 key 是否相同，不会判断 value 是否相同。也就是说，多次插入相同的 <key, value> ，multimap 会全部保存下来。

set

容器属性：关联容器，有序，元素自身即key，元素有唯一性

内存空间：使用内存分配器动态管理内存

容器尺寸：能够添加元素

头文件：#include <set>

和map一样，底层是红黑树，set 中的元素必须是唯一的，且已经排序好（升序，从小到大），不允许出现重复的元素，且元素不可更改，但可以自由插入或者删除。

set提供了特殊的搜寻函数。

count (elem)：返回元素值为elem的个数，时间复杂度O(\log n)。
find(elem)：返回元素值为elem的第一个元素，如果没有返回end() ，时间复杂度O(\log n)。
lower_bound(elem)：返回元素值为elem的第一个可安插位置，也就是元素值 >= elem的第一个元素位置，时间复杂度O(\log n)。
upper_bound (elem)：返回元素值为elem的最后一个可安插位置，也就是元素值 > elem 的第一个元素位置，时间复杂度O(\log n)。
equal_range (elem)：返回elem可安插的第一个位置和最后一个位置，也就是元素值==elem的区间，时间复杂度O(\log n)。
insert(elem) ：插入一个elem副本，返回新元素位置，无论插入成功与否
erase(elem) ：删除与elem相等的所有元素，返回被移除的元素个数