C++ STL容器的底层原理

C++ 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, 3> arr { };

如果 array 未显式初始化，其元素值将处于未定义状态。数组大小固定，不支持添加或删除元素等改变大小的操作，所有的元素严格按照内存地址线性排列。

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

front()：返回数组第一个元素的引用。如果数组为空，调用 front() 是未定义行为；否则直接通过索引访问第一个元素。时间复杂度为 \text{O}(1)。
back()：返回数组最后一个元素的引用，通过索引直接访问最后一个元素，其他同上。时间复杂度为 \text{O}(1)。
at(i)：返回数组中 i 位置元素的引用。如果超出数组尺寸，会抛出 out_of_range 异常。时间复杂度为 \text{O}(1)。
empty()：返回 bool 类型结果，判断数组是否为空。时间复杂度为 \text{O}(1)。
data()：返回数组第一个元素的指针，即数组的地址。时间复杂度为 \text{O}(1)。
fill(a)：将数组所有内容填充为指定内容 a。底层使用一个循环，遍历每个元素，然后将当前元素赋值为 a。时间复杂度为 \text{O}(n)，n 为元素数量。
swap(arr)：将两个数组的元素进行交换，要求两数组类型和尺寸都必须相同，否则编译不通过。和其他容器不同的是，数组的 swap() 方法交换了各个元素的值，但是容器中所存的元素的地址没有交换。底层使用一个循环遍历数组元素，然后 swap() 函数交换当前数组和另一个数组中对应位置的元素。要注意 swap() 之后迭代器、引用和指针都仍然有效。先说迭代器，由于内存地址没有变化，只是交换了元素内容，因此迭代器仍然指向相同的内存地址；引用一旦绑定就不会改变，即使交换了元素，引用仍然指向最初绑定元素的位置；指针和迭代器类似，仍然指向原来的地址。时间复杂度为 \text{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[]：和数组一样，可以直接通过 [] 访问元素，时间复杂度为 \text{O}(1)。
at(i)：vector.at(i) 等同于 vector[i]。区别在于，vector[i] 效率（可能）更高，但不会做越界访问保护和异常抛出，需要自己做越界检查。时间复杂度为 \text{O}(1)。
front() 和 back()：分别返回第一个和最后一个元素。如数组一样，空 vector 会导致未定义行为。时间复杂度为 \text{O}(1)。
data()：返回指向容器中第一个元素的指针。时间复杂度为 \text{O}(1)。
push_back(i)：在容器的尾部插入元素 i，底层通过拷贝或者移动的方式；如果是拷贝，事后自行销毁先前创建的元素。调用 push_back() 时，若当前容量不够放入新元素，即 capacity() == size()，vector 会重新申请一块内存，把之前 vector 内存里的元素拷贝到新内存中，然后把 push_back 的元素拷贝到新的内存中，最后要析构原有的 vector 并释放原有内存。触发 reallocate 时复制的时间复杂度为 \text{O}(n)，注意此时迭代器会失效，因为分配了新的内存；不触发时为 \text{O}(1)，均摊下来时间复杂度为 \text{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 = \\begin{cases} i & i-1 \\text{ 为 2 的幂} \\\\ 1 & \\text{其他情况} \\end{cases}

那么有：

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

因此，push_back 的均摊时间复杂度为 \text{O}(1)。

pop_back()：移除最后一个元素。时间复杂度为 \text{O}(1)。
insert()：在指定位置插入元素。先检查容量，如果不够就先扩容，然后将插入点之后的所有元素向后移动，最后插入新元素。最好情况下时间复杂度为 \text{O}(1)，比如在尾部插入；最坏情况下比如在头部插入，时间复杂度为 \text{O}(n)。
erase()：删除指定位置或区间的元素。将删除点之后的所有元素向前移动。时间复杂度为 \text{O}(n)。
resize()：改变容器中元素的数量。如果新尺寸小于当前尺寸，多出的元素将被移除；如果大于当前尺寸，将在末尾插入新元素，默认值为 0 或默认构造值。时间复杂度为 \text{O}(n)。
clear()：清空所有元素。时间复杂度为 \text{O}(n)。
swap(v)：交换两个 vector 的内容。底层直接交换指针、容量和尺寸信息，不移动元素。时间复杂度为 \text{O}(1)。
shrink_to_fit()：请求缩减容量以适应尺寸。这是一个非绑定请求，具体实现可能忽略。时间复杂度取决于实现，通常为 \text{O}(n)。

vector 的内存释放技巧：

vector(v).swap(v) 或 vector().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 的核心优势是在双端都支持高效（时间复杂度为 \text{O}(1)）的增删操作，程序员选择使用 deque 时必须有双端操作的需求 [1]。deque 的迭代器并不是普通指针，其底层实现非常复杂。因此，除非必要（双端操作），尽可能选用 vector。对 deque 进行排序操作，可将 deque 先完整复制到一个 vector 上，对 vector 排序后，再复制到 deque [7]。

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

queue

容器属性：容器适配器，基于底层容器实现 FIFO 逻辑，不支持随机访问

内存空间：依赖底层容器（默认 deque）

容器尺寸：动态调整大小

头文件：#include <queue>

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

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

queue 是一种 FIFO（First In First Out，先进先出）的容器适配器，只能从一端插入（队尾），从另一端删除（队首）。它本身不是独立的容器，而是基于底层容器（默认 deque）封装了特定的接口。由于只暴露队首和队尾操作，queue 不支持遍历，也不提供迭代器。

push(val)：在队尾添加元素。底层调用底层容器的 push_back()。时间复杂度为 \text{O}(1)。
emplace(val)：在队尾就地构造元素。时间复杂度为 \text{O}(1)。
pop()：移除队首元素。底层调用底层容器的 pop_front()。时间复杂度为 \text{O}(1)。
front()：返回队首元素的引用。时间复杂度为 \text{O}(1)。
back()：返回队尾元素的引用。时间复杂度为 \text{O}(1)。
empty()：判断队列是否为空。时间复杂度为 \text{O}(1)。
size()：返回队列中元素的数量。时间复杂度为 \text{O}(1)。

priority_queue

容器属性：容器适配器，基于底层容器实现堆结构，不支持随机访问

内存空间：依赖底层容器（默认 vector）

容器尺寸：动态调整大小

头文件：#include <queue>

类模板头：template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;

声明方式：std::priority_queue<int> myPQ;

priority_queue 叫做优先级队列。它的特点是严格弱序，即 priority_queue 保证容器中的第一个元素始终是所有元素中最大的。默认情况下，priority_queue 使用 vector 作为底层容器，配合 heap 算法（默认大顶堆）来维护元素的优先级顺序。

push(val)：插入元素，并调整堆结构。时间复杂度为 \text{O}(\\log n)。
emplace(val)：就地构造元素并插入。时间复杂度为 \text{O}(\\log n)。
pop()：移除堆顶（优先级最高）元素，并调整堆结构。时间复杂度为 \text{O}(\\log n)。
top()：返回堆顶元素的引用。时间复杂度为 \text{O}(1)。
empty()：判断队列是否为空。时间复杂度为 \text{O}(1)。
size()：返回元素数量。时间复杂度为 \text{O}(1)。

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 不支持随机访问，也就不提供下标操作符和 at() 函数。

push_back(const T& val)：在容器尾部插入一个元素。底层上首先分配内存存储新元素，随后在 list 最后插入（若 list 为空则为第一个元素），更新链表最后的 next 指针，使之指向新元素。最后更新链表大小。时间复杂度为 \text{O}(1)。
push_front(const T& val)：在容器头部插入一个元素。底层和 push_back 差不多，只是需要更新链表的最前向的指针，指向新元素。时间复杂度为 \text{O}(1)。
emplace_back()：在容器尾部直接生成一个元素。和 push_back() 的功能相同，但效率更高。时间复杂度为 \text{O}(1)。
insert()：在指定迭代器的位置插入元素。在底层上，首先获取迭代器 it 指向的当前元素及其前一个元素。然后创建一个新元素。随后将前一个元素的 next 指向新元素，将新元素的 prev 指向前一个元素，至此新元素和前面元素的链接完成。然后将新元素的 next 指向当前元素，并将当前元素的 prev 指向新元素。至此新元素和当前元素的链接完成。时间复杂度为 \text{O}(1)（已知插入位置时）。
pop_front()：删除容器最前面的元素。底层上先检查容器是否为空。然后将第二个节点（如有）的 prev 设为 null，将 list 头部指针删除。时间复杂度为 \text{O}(1)。
pop_back()：删除容器尾部的元素。时间复杂度为 \text{O}(1)。
erase()：删除指定位置或位置区间元素。底层上遍历链表，如果找到了要删除的元素，更新要删除的元素前面元素的 next 和后面元素的 prev，然后删除当前元素。时间复杂度为 \text{O}(1)（已知删除位置时）。
resize()：如果小于当前 size，容器会删除超出的元素；如果大于当前 size，容器会在末尾插入指定元素，如不指定，执行默认初始化。时间复杂度为 \text{O}(n)。
swap()：交换两个类型相同的 list 的元素。底层上直接交换头部节点和尾部节点的指针。时间复杂度为 \text{O}(1)。
reverse()：反转 list。通过迭代地交换所有元素的 prev 和 next 实现。时间复杂度为 \text{O}(n)。
assign()：将新内容分配给容器，替换掉当前内容。底层通过先清除掉现有内容，然后把新内容插入。时间复杂度为 \text{O}(n)。
sort()：对链表进行排序。由于 list 不支持随机访问，不能使用标准 sort()，因此提供了专门的成员函数。底层通常使用归并排序实现。时间复杂度为 \text{O}(n \\log n)。
merge()：合并两个已排序的链表。时间复杂度为 \text{O}(n)。
splice()：将元素从一个链表转移到另一个链表，不拷贝或移动元素，仅修改指针。时间复杂度为 \text{O}(1)。
unique()：移除重复元素。时间复杂度为 \text{O}(n)。
remove(val)：移除所有值为 val 的元素。时间复杂度为 \text{O}(n)。
remove_if(pred)：移除满足条件的元素。时间复杂度为 \text{O}(n)。

forward_list

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

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

容器尺寸：能够添加元素

头文件：#include <forward_list>

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

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

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

push_front(const T& val)：在容器头部插入一个元素。时间复杂度为 \text{O}(1)。
emplace_front()：在容器头部就地构造一个元素。时间复杂度为 \text{O}(1)。
pop_front()：删除容器头部的元素。时间复杂度为 \text{O}(1)。
insert_after()：在指定位置之后插入元素。时间复杂度为 \text{O}(1)。
erase_after()：删除指定位置之后的元素。时间复杂度为 \text{O}(1)。
splice_after()：将元素从一个链表转移到另一个链表。时间复杂度为 \text{O}(1)。
remove(val)：移除所有值为 val 的元素。时间复杂度为 \text{O}(n)。
unique()：移除重复元素。时间复杂度为 \text{O}(n)。
sort()：对链表排序。时间复杂度为 \text{O}(n \\log n)。
merge()：合并两个已排序的链表。时间复杂度为 \text{O}(n)。
reverse()：反转链表。时间复杂度为 \text{O}(n)。
resize()：改变容器大小。时间复杂度为 \text{O}(n)。

map

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

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

容器尺寸：能够添加元素

头文件：#include <map>

类模板头：template < class Key, class T, class Compare = less<Key>, class Alloc = allocator<pair<const Key,T> > > class map;

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

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

at(const Key& k)：如果 map 中存在键 k，则返回与键 k 关联的值的引用。时间复杂度为 \text{O}(\\log n)。比起 operator[]，在找不到键时，at() 会抛出 out_of_range 异常。
operator[]：如果键存在，返回对应值的引用；如果不存在，会创建一个新的键值对，其中键是 k，值是值类型的默认构造值，然后返回这个新插入值的引用。因此，operator[] 不会抛出异常，但可能会导致意外的键值对插入。时间复杂度为 \text{O}(\\log n)。
emplace()：插入一个键值对，这个键值对是就地构造的，避免了创建临时对象。如果插入的 key 已经存在，那么不会进行任何操作并返回 false。时间复杂度为 \text{O}(\\log n)。
insert()：若待插入元素的键值 key 在 map 中不存在，则 insert 插入成功，并返回插入后元素的迭代器和 true。若待插入元素的键值 key 在 map 当中已经存在，则插入失败，并返回 map 中键值为 key 的元素的迭代器和 false。时间复杂度为 \text{O}(\\log n)。
erase()：通过迭代器或者键来删除指定键值对。删除指定迭代器的键值对，时间复杂度为 \text{O}(1)（均摊）。删除指定键的键值对，时间复杂度为 \text{O}(\\log n)。删除指定范围的键值对，时间复杂度为 \text{O}(n)。
find()：在容器中寻找键为 k 的元素，返回该元素的迭代器。否则，返回 map.end()。时间复杂度为 \text{O}(\\log n)。
count()：返回键为 k 的元素个数（对于 map 只能是 0 或 1）。时间复杂度为 \text{O}(\\log n)。
lower_bound(k)：返回第一个键值不小于 k 的元素的迭代器。时间复杂度为 \text{O}(\\log n)。
upper_bound(k)：返回第一个键值大于 k 的元素的迭代器。时间复杂度为 \text{O}(\\log n)。
equal_range(k)：返回键值等于 k 的区间范围。时间复杂度为 \text{O}(\\log n)。
clear()：清空所有元素。时间复杂度为 \text{O}(n)。
swap()：交换两个 map 的内容。时间复杂度为 \text{O}(1)。
size()：返回元素数量。时间复杂度为 \text{O}(1)。
empty()：判断是否为空。时间复杂度为 \text{O}(1)。

multimap

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

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

容器尺寸：能够添加元素

头文件：#include <map>

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

insert()：插入一个键值对。时间复杂度为 \text{O}(\\log n)。
erase()：删除指定键的所有元素，或删除指定迭代器的元素。时间复杂度为 \text{O}(\\log n) 或 \text{O}(1)。
find()：查找键为 k 的第一个元素。时间复杂度为 \text{O}(\\log n)。
count()：返回键为 k 的元素个数。时间复杂度为 \text{O}(\\log n)。
equal_range()：返回键为 k 的所有元素区间。时间复杂度为 \text{O}(\\log n)。
lower_bound() 和 upper_bound()：与 map 相同。时间复杂度为 \text{O}(\\log n)。

set

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

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

容器尺寸：能够添加元素

头文件：#include <set>

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

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

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

multiset

容器属性：关联容器，有序，允许元素重复

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

容器尺寸：能够添加元素

头文件：#include <set>

和 set 的区别在于，multiset 允许元素是重复的。底层同样是红黑树，插入、删除和查找的时间复杂度均为 \text{O}(\\log n)。

insert(elem)：插入元素。时间复杂度为 \text{O}(\\log n)。
erase(elem)：删除所有值为 elem 的元素。时间复杂度为 \text{O}(\\log n + k)，k 为被删除元素个数。
find(elem)：查找第一个值为 elem 的元素。时间复杂度为 \text{O}(\\log n)。
count(elem)：返回值为 elem 的元素个数。时间复杂度为 \text{O}(\\log n + k)。
equal_range(elem)：返回所有值为 elem 的元素区间。时间复杂度为 \text{O}(\\log n + k)。

stack

容器属性：容器适配器，LIFO（后进先出），只能从一端插入和删除，不允许遍历

内存空间：依赖底层容器（默认 deque）

容器尺寸：动态调整大小

头文件：#include <stack>

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

声明方式：std::stack<int> myStack;

stack 是一种 LIFO（Last In First Out，后进先出）的容器适配器，默认使用 deque 作为底层容器。stack 仅暴露栈顶操作，不支持遍历，也不提供迭代器。

push(val)：在栈顶添加元素。底层调用底层容器的 push_back()。时间复杂度为 \text{O}(1)。
emplace(val)：在栈顶就地构造元素。时间复杂度为 \text{O}(1)。
pop()：移除栈顶元素。底层调用底层容器的 pop_back()。时间复杂度为 \text{O}(1)。
top()：返回栈顶元素的引用。时间复杂度为 \text{O}(1)。
empty()：判断栈是否为空。时间复杂度为 \text{O}(1)。
size()：返回栈中元素数量。时间复杂度为 \text{O}(1)。
swap()：交换两个栈的内容。时间复杂度为 \text{O}(1)。

unordered_map

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

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

容器尺寸：能够添加元素

头文件：#include <unordered_map>

声明方式：std::unordered_map<int, string> mymap;

所有 unordered 的容器，都是以哈希表为底层。通常 map 增删元素的效率更高（维护有序性的开销相对稳定），unordered_map 访问元素的效率更高（平均情况下）。通过直接计算 key 的哈希值来访问元素，平均时间复杂度为 \text{O}(1)，最坏情况下（哈希冲突严重）为 \text{O}(n)。