C++ 容器速查手册

STL 容器与原生数组的 API 速查表，按“查得到、抄得来”组织，覆盖构造、访问、容量、修改、查找。原理(内存布局、扩容机制、迭代器失效的根因、选型权衡)见 C++ STL 容器,内存分配细节见 C++ STL Allocator。本文只列怎么用。

容器总览

容器	头文件	底层	迭代器类别	随机访问
T[N] 原生数组	-	连续	指针(随机)	✓
array	<array>	固定数组	随机访问	✓
vector	<vector>	动态数组	随机访问	✓
deque	<deque>	分段连续	随机访问	✓
list	<list>	双向链表	双向	✗
forward_list	<forward_list>	单向链表	前向	✗
set / multiset	<set>	红黑树	双向	✗
map / multimap	<map>	红黑树	双向	✗
unordered_set/map	<unordered_*>	哈希表	前向	✗
stack	<stack>	适配器	—	—
queue	<queue>	适配器	—	—
priority_queue	<queue>	堆	—	—

array/vector/deque/string/原生数组是连续内存，cache 友好；链表与节点容器不连续。适配器不暴露迭代器。

全容器通用接口

除适配器外，标准容器共享这套接口：

C c;                          // 默认构造
C c2(c);                      // 拷贝构造
C c3(std::move(c2));          // 移动构造
C c4(other.begin(), other.end());  // 范围构造
C c5{1, 2, 3};                // 初始化列表
c = c4;                       // 拷贝赋值
c = std::move(c4);            // 移动赋值
c = {1, 2, 3};                // 列表赋值
c.empty();
c.size();                     // forward_list 没有
c.max_size();
c.clear();
c.swap(other);
std::swap(c, other);
c.begin();  c.end();
c.cbegin(); c.cend();         // const 版本
c.rbegin(); c.rend();         // 反向，连续/链表/有序有

forward_list 特立独行：没有 size()（为省一个指针），用 insert_after 系列代替 insert。

原生数组（C 风格）

std::array 的老底：自身不动态分配（存放位置随变量而定）、零开销，但类型系统弱、易退化、边界不查。能用 std::array 就别用原生数组；以下补它仍常见时的用法。

声明与初始化

int a[4];                     // 局部，内容未定义
int b[4]{};                   // 全 0
int c[4]{1, 2, 3, 4};         // 显式
int d[4]{1, 2};               // {1,2,0,0}，余者 0
int e[] = {1, 2, 3};          // 大小推导为 3
char s[] = "hi";              // 含 '\0'，长度 3

大小必须是编译期常量；int a[4]; 不加 {} 则局部内容未定义。C99 变长数组（VLA）不是标准 C++。

访问与大小

#include <iterator>

a[0];                         // 不检查边界，越界 UB
a[2] = 9;
sizeof(a);                    // 总字节数
sizeof(a) / sizeof(a[0]);     // 元素个数
std::size(a);                 // C++17，返回 4
std::ssize(a);                // C++20，有符号
std::begin(a); std::end(a);   // 指针，适配泛型算法

sizeof/std::size 仅在数组未退化时正确；传入函数后退化成指针，三者全部失灵。

退化：头号陷阱

数组名在多数语境退化为首元素指针，长度信息丢失：

int a[4]{1, 2, 3, 4};
int* p = a;                   // 退化
auto x = a;                   // 推导为 int*，仍退化
auto& r = a;                  // int(&)[4]，不退化

void f(int arr[]);            // 等价于 void f(int*)
void f(int arr[4]);           // 长度被忽略
f(a);                         // 退化，丢失 4

遍历

for (size_t i = 0; i < std::size(a); ++i)
  a[i];
for (int x : a) { /* 只读 */ }
for (int& x : a) { x *= 2; }  // 可写

多维数组

行优先、连续存储；除第一维外大小必须固定。

int m[2][3]{{1, 2, 3}, {4, 5, 6}};
m[0][1];                      // 2
int (*row)[3] = m;            // 指向 3 个 int 的数组
void g(int arr[][3], int n);  // 第二维不可省

int m[][] 非法。

安全传参

退化让“数组参数”形同虚设。三种姿势，长度保障从弱到强：

#include <span>

void f0(int* a, size_t n);        // C 风格，长度靠手传
void f1(int (&a)[4]);             // 引用数组，长度入类型
void f2(std::span<const int> a);  // C++20 首选

int a[4]{1, 2, 3, 4};
f0(a, 4);
f1(a);
f2(a);                        // 数组直接推导长度
std::span<int> s{a, 4};       // 显式构造视图

std::span 是“连续内存 + 长度”的零拷贝视图，可接受原生数组、std::array、std::vector、std::string。

自由函数：统一访问接口

容器有成员函数（c.begin()），原生数组没有。<iterator> 的自由函数对二者一视同仁，是泛型代码的基础；范围 for 正是靠它展开。

begin / end 家族

#include <iterator>

int a[4]{1, 2, 3, 4};
std::vector<int> v{1, 2, 3};

std::begin(a);                // int*（首元素）
std::end(a);                  // int*（尾后）
std::begin(v);                // vector<int>::iterator
std::cbegin(a);               // const int*，C++14
std::cend(a);
std::rbegin(a);               // 反向，C++14
std::rend(a);
std::crbegin(a);              // const 反向，C++14
std::crend(a);

对容器等价于成员函数；对数组返回首/尾后指针。写泛型代码统一用自由函数。

size / ssize / empty / data

std::size(a);                 // 4，C++17，无符号 size_t
std::size(v);                 // v.size()
std::ssize(a);                // C++20，有符号 ptrdiff_t
std::empty(a);                // C++17
std::empty(v);
std::data(a);                 // int*，C++17
std::data(v);                 // v.data()

std::ssize 专治无符号下溢：

for (size_t i = 0; i < v.size() - 1; ++i) { }
// v 为空时 size()-1 回绕成 SIZE_MAX，死循环

for (ptrdiff_t i = 0; i < std::ssize(v) - 1; ++i) { }
// 有符号，安全

next / prev / advance / distance

迭代器算术，代价随迭代器类别变化：

std::advance(it, n);          // 原地推进 n 步
auto it2 = std::next(it);     // 返回下一个，不改 it
auto it3 = std::next(it, 3);
auto it4 = std::prev(it);     // 需双向迭代器
auto d = std::distance(b, e); // [b,e) 距离

随机访问 O(1)，其余按步数 O(n)。

泛型示例

template <class R>
void print(const R& r) {
  for (auto it = std::begin(r); it != std::end(r); ++it)
    std::cout << *it << ' ';
}

int a[4]{1, 2, 3, 4};
std::vector<int> v{5, 6, 7};
std::list<int> l{8, 9};
print(a);                     // 数组也行
print(v);
print(l);

范围 for（for (auto x : r)）即用 std::begin/std::end 展开，故对数组同样有效。

序列容器

std::array：固定大小数组

自身不动态分配，存放位置随变量而定：局部在栈、static/全局在静态区、new 出来的在堆。零开销，大小是类型的一部分。

#include <array>

std::array<int, 4> a{1, 2, 3, 4};
std::array b{1.0, 2.0};       // CTAD -> array<double,2>

a[0];                         // 不检查边界
a.at(2);                      // 越界抛 out_of_range
a.front();
a.back();
a.data();                     // int*
a.size();                     // constexpr
a.empty();
a.fill(0);                    // 全部置 0
std::get<0>(a);               // 编译期取
a.swap(b);
// 按字典序比较 == != < <= > >=

没有 push_back/insert/erase/resize——大小编译期固定。

std::vector：默认选择

连续内存，尾端均摊 O(1)。

#include <vector>

std::vector<int> v;
std::vector<int> v1(n);       // n 个 0
std::vector<int> v2(n, 7);    // n 个 7
std::vector<int> v3{1, 2, 3};
std::vector<int> v4(v3.begin(), v3.end());

// 元素访问
v[0]; v.at(2); v.front(); v.back();
v.data();

// 容量
v.size();
v.capacity();
v.reserve(1000);              // 预留，避免扩容
v.shrink_to_fit();            // 请求释放多余容量
v.resize(10);
v.resize(10, -1);             // 新位置填 -1

// 修改
v.push_back(9);
v.emplace_back(9);            // 原地构造，无拷贝
v.pop_back();
v.insert(v.begin(), 0);
v.insert(v.begin(), 3, 0);    // 插 3 个 0
v.insert(v.begin(), v3.begin(), v3.end());
v.emplace(v.begin(), 0);
v.erase(v.begin());
v.erase(v.begin(), v.begin() + 2);
v.assign({1, 2});
v.assign(n, 7);
v.swap(v2);
v.clear();

C++23 范围插入：append_range / assign_range / insert_range(pos, rng)。
C++20 统一删除：std::erase(v, 7) 删所有等于 7；std::erase_if(v, pred)。

std::vector<bool>：特化版本

std::vector<bool> 是标准库的显式特化，非普通 vector：为省空间把每个 bool 压成 1 bit 紧凑存储，代价是行为与 vector<T> 不一致。

std::vector<bool> b{true, false, true};

b[0];                         // proxy，非 bool
bool x = b[0];                // OK，隐式转换取值
auto y = b[0];                // 陷阱：y 是 proxy，非 bool
auto& r = b[0];               // 编译错：proxy 是右值
bool* p = &b[0];              // 编译错：无法取地址
b.flip();                     // 全部取反

关键差异与陷阱：

• operator[]/at()/front()/back() 返回代理对象 reference，非 bool&：不可取地址、不可绑到 bool&。
• 无连续 bool 数组，不满足 ContiguousContainer，不能传给 C 风格 bool* 接口。
• 数据竞争：同一字节内不同位非独立，多线程并发写相邻元素即 race（下标不同也算）。
• flip() 翻转全部位；static swap(r1, r2) 交换两个位引用。

需要“真”布尔数组时改用：

std::vector<char> v(n, 1);    // 要 bool* / 连续内存
std::array<bool, N> a;        // 固定大小，真数组
std::bitset<N> bits;          // 固定大小，位运算友好
boost::dynamic_bitset<> db;   // 动态大小位集

经验：除非明确要省内存，否则别用 vector<bool>；要位操作选 bitset，要当数组用 vector<char>。

std::deque：双端队列

两端 O(1) 插删，随机访问 O(1) 但慢于 vector。

#include <deque>

std::deque<int> dq{1, 2, 3};

dq[0]; dq.at(1); dq.front(); dq.back();

dq.push_back(4);
dq.push_front(0);
dq.emplace_back(4);
dq.emplace_front(0);
dq.pop_back();
dq.pop_front();
dq.insert(dq.begin(), 9);
dq.erase(dq.begin());
dq.resize(5);
dq.assign({7, 8});

中间插删 O(n)。

std::list / forward_list：链表

list 双向，forward_list 单向（更省内存）。

#include <list>
#include <forward_list>

std::list<int> l{1, 2, 3};
std::forward_list<int> fl{1, 2, 3};

l.front(); l.back();
fl.front();                   // forward_list 无 back()

l.push_back(4);
l.push_front(0);
fl.push_front(0);             // forward_list 无 push_back
l.pop_back(); l.pop_front();
fl.pop_front();

l.insert(it, 9);              // O(1)，已知 it
l.insert(it, 3, 9);
l.insert(it, l2.begin(), l2.end());
l.emplace(it, 9);
l.erase(it);
l.erase(first, last);

链表特有 O(1) 整表操作（forward_list 对应有 _after 版本）：

l.splice(it, l2);             // 整表接到 it 前
l.splice(it, l2, it2);        // 接单个
l.splice(it, l2, first, last);
l.remove(9);                  // 删所有等于 9
l.remove_if(pred);
l.unique();                   // 去相邻重复
l.merge(l2);                  // 合并有序链表
l.sort();                     // 归并排序
l.reverse();

forward_list 用 insert_after/emplace_after/erase_after/splice_after，配合 before_begin() 取得"首前"位置。

关联容器

有序，红黑树，查找/插删 O(log n)。

set / multiset

#include <set>

std::set<int> s{3, 1, 2};     // 自动有序 {1,2,3}
std::multiset<int> ms{1, 1, 2};

// 无 operator[]，无 at()
s.find(2);                    // 返回迭代器
s.contains(2);                // C++20
s.count(2);                   // 0/1；multiset 可 >1
s.lower_bound(2);             // 首个 >= 2
s.upper_bound(2);             // 首个 > 2
s.equal_range(2);             // [lower, upper)

s.insert(4);
s.emplace(4);
s.erase(2);                   // 按 key 删
s.erase(it);
s.extract(2);                 // C++17 节点句柄
s.merge(s2);                  // 接合另一集合

multiset::erase(key) 删除全部匹配；只删一个用 erase(it)。自定义序：std::set<int, std::greater<>>。

map / multimap

#include <map>

std::map<std::string, int> m{{"a", 1}, {"b", 2}};
std::multimap<std::string, int> mm;

m["a"] = 1;                   // 不存在则插 {a,0} 再赋值
m.at("a");                    // 越界抛 out_of_range
m.find("a");
m.contains("a");              // C++20
m.count("a");
m.lower_bound("a");
m.upper_bound("a");
m.equal_range("a");

m.insert({"c", 3});
m.emplace("c", 3);
m.insert_or_assign("c", 3);   // C++17，类似 []
m.try_emplace("c", 3);        // C++17，不覆盖已有 value
m.erase("a");
m.extract("a");

// 遍历（C++17 结构化绑定）
for (auto& [k, v] : m) { /* ... */ }

multimap 一对多，无 operator[] 与 at()；按 key 取区间用 equal_range。

无序关联容器

哈希表，平均 O(1)，最坏 O(n)（冲突/rehash）。

#include <unordered_set>
#include <unordered_map>

std::unordered_set<int> us{1, 2, 3};
std::unordered_map<std::string, int> um;
um["a"] = 1;

us.find(2); us.contains(2); us.count(2);
us.insert(4); us.emplace(4);
us.erase(2);
us.bucket_count();
us.load_factor();             // size / bucket_count
us.max_load_factor();         // 默认 1.0
us.rehash(100);               // 设桶数
us.reserve(100);              // 预留，自动 rehash

接口与有序容器基本一致，但没有 lower_bound/upper_bound。unordered_map 同样有 []/at/try_emplace/insert_or_assign。

自定义 key 必须提供哈希与相等判断：

struct Point { int x, y; };

struct PHash {
  size_t operator()(const Point& p) const noexcept {
    return size_t(p.x) * 31 + p.y;
  }
};

struct PEq {
  bool operator()(const Point& a,
                  const Point& b) const noexcept {
    return a.x == b.x && a.y == b.y;
  }
};

std::unordered_map<Point, int, PHash, PEq> grid;

容器适配器

包装底层容器（默认 deque），只暴露受限接口，不可遍历。

stack：LIFO

#include <stack>

std::stack<int> st;
std::stack<int, std::vector<int>> sv;  // 指定底层

st.push(1);
st.emplace(1);
st.pop();                     // 无返回值
st.top();
st.empty();
st.size();

queue：FIFO

#include <queue>

std::queue<int> q;

q.push(1);                    // 入队尾
q.emplace(1);
q.pop();                      // 出队头
q.front();                    // 队头
q.back();                     // 队尾
q.empty();
q.size();

priority_queue：堆

默认大根堆，top() 是最大元素。

#include <queue>

std::priority_queue<int> pq;              // 大根堆
std::priority_queue<int, std::vector<int>,
                    std::greater<>> min_pq;  // 小根堆

pq.push(3);
pq.emplace(3);
pq.pop();                     // 移除堆顶
pq.top();                     // 堆顶
pq.empty();
pq.size();

无 front/back，无遍历。自定义类型需提供 operator<（或传入比较器）。

迭代器失效速查

对容器的修改可能让已有迭代器/引用/指针失效，再用即 UB。

容器	插入	删除
vector / string	扩容则全部失效；否则插入点之后失效	删除点及之后失效（含 end）
deque	两端插：仅 end 失效；中间插：全部失效	两端删：被删与 end 失效；中间删：全部失效
list / forward_list	不失效其他	仅被删元素失效
set / map 等	不失效	仅被删元素失效
unordered_*	rehash 则全部失效；否则不失效	仅被删元素失效（rehash 期间除外）

边遍历边删的正确写法：

// vector：erase 返回下一个有效迭代器
for (auto it = v.begin(); it != v.end();)
  if (*it % 2 == 0) it = v.erase(it);
  else ++it;

// C++20：统一一行搞定，适用所有容器
std::erase_if(v, [](int x) { return x % 2 == 0; });

复杂度速查

操作	vector	deque	list	set/map	unordered_*
随机访问 []	O(1)	O(1)	—	—	—
头部插入	O(n)	O(1)	O(1)	—	—
尾部插入	均摊 O(1)	O(1)	O(1)	—	—
中间插入	O(n)	O(n)	O(1)*	O(log n)	均摊 O(1)
按 key 查找	O(n)	O(n)	O(n)	O(log n)	均摊 O(1)
排序	O(n log n)	—	O(n log n)	已序	—

* list 中间插入 O(1) 仅指"已知位置插入"，找位置仍 O(n)。

选型决策

要随机访问 / 连续内存？
├─ 大小编译期已知       -> array
├─ 默认                 -> vector
└─ 两端都要进出         -> deque

要按键查找？
├─ 需要有序 / 范围查询  -> map / set
└─ 只要平均最快         -> unordered_map / unordered_set

要在已知位置频繁增删，
且不能失效其他迭代器？  -> list / forward_list

要栈/队列/优先队列？    -> stack / queue / priority_queue

经验法则：默认 vector；按 key 查表默认 unordered_map；大小固定用 array；除非真需要"增删不失效其他迭代器"，否则避免 list。批量操作优先 assign/insert(range)/append_range 而非循环 push_back，一次 reserve 避免多次扩容。