C++ SLT常用容器

容器大类

• 顺序容器：vector / deque / list / array
  • 按“位置/顺序”存数据
• 关联容器（有序）：map / set / multimap / multiset
  • 按“key/值的排序规则”存，底层树结构，O(logN)
• 无序容器（哈希）：unordered_map / unordered_set
  • 平均 O(1)，不排序
• 容器适配器：stack / queue / priority_queue
  • “接口受限”的封装（不支持遍历）

共同接口（大多数都有）

• size() / empty() / clear()
• begin() / end() 用于遍历
• insert / erase（不同容器细节不同）

1) std::vector<T>（动态数组）

头文件：#include <vector>

特点

• 连续内存（cache 友好，遍历/拷贝快）
• 支持 随机访问：v[i]、v.at(i)
• 尾部插入快：push_back 均摊 O(1)
• 中间插入/删除慢：O(N)（需要移动元素）
• 自动扩容；扩容时迭代器/引用/data() 可能失效

初始化

std::vector<int> v;                 // 空
std::vector<int> v2(5);             // 5个0
std::vector<double> v3(6, 0.0);     // 6个0.0
std::vector<int> v4 = {1,2,3};      // 列表初始化

常用操作

• 访问（读/写）

v[i];            // 不做越界检查（越界=未定义行为）
v.at(i);         // 带边界检查，越界抛 std::out_of_range
v.front();       // 第一个元素（要求非空）
v.back();        // 最后一个元素（要求非空）
v.data();        // 指向底层连续内存的指针（传 C 接口常用）

• 插入 / 删除

v.push_back(x);                              // 末尾追加
v.pop_back();                                // 删除末尾

v.insert(v.begin() + pos, x);                // 中间插入（O(N)）
v.erase(v.begin() + pos);                    // 删除单个位置（O(N)）
v.erase(v.begin() + l, v.begin() + r);       // 删除区间 [l, r)
v.clear();                                   // 清空所有元素（容量不变）

• 赋值 / 重置

v.assign(6, 0.0);                            // 直接重置为 6 个 0.0
v.resize(10);                                // 改长度（扩展补默认值 T()）
v.resize(10, 3.14);                          // 扩展用 3.14 填充

• 容量管理

v.size();                                    // 当前元素个数
v.capacity();                                // 当前容量（不小于 size）
v.reserve(100);                              // 预留容量（避免多次扩容）
v.shrink_to_fit();                           // 请求收缩容量（非强制）
v.empty();                                   // 是否为空

• 遍历（C++11）

for (const auto& x : v) { /* 只读遍历 */ }
for (auto& x : v) { /* 可修改遍历 */ }

for (auto it = v.begin(); it != v.end(); ++it) {
    // *it 访问
}

典型用例：从数组构造 vector / 追加数组内容

double a[6] = {0,0,0,0,0,0};
std::vector<double> v(a, a+6); // 构造

// 追加插入数组到vector末尾
v.insert(v.end(), a, a+6);

常见坑：下标赋值前必须有空间

std::vector<double> v;
v[0] = 1.0; // × 越界（未定义行为）

v.resize(6);
v[0] = 1.0; // √

迭代器/指针失效规则（重点）

• push_back 可能触发扩容 ⇒ 所有迭代器、引用、data() 指针都可能失效
• erase/insert 在 vector 中通常会使插入点之后的迭代器失效

2) std::array<T, N>（固定长度数组）

头文件：#include <array>

特点

• 长度在编译期固定（N 是模板参数）
• 连续内存（与 C 数组布局一致，cache 友好）
• 无动态分配（通常在栈上或作为对象成员）
• 支持 随机访问：a[i]、a.at(i)
• 可与 STL 算法配合使用（有 begin/end）
• 不能改变长度（没有 push_back / resize）

初始化（C++11 需要双花括号）

std::array<int, 5> a1 = {{1, 2, 3, 4, 5}};
std::array<double, 6> a2 = {{0, 0, 0, 0, 0, 0}};
std::array<int, 3> a3 = {{}};              // 全部初始化为 0

常用操作

• 访问（读 / 写）

a[i];            // 不做越界检查（越界=未定义行为）
a.at(i);         // 带边界检查，越界抛 std::out_of_range
a.front();       // 第一个元素
a.back();        // 最后一个元素
a.data();        // 指向底层连续内存的指针（T*）

• 容量相关

a.size();        // 返回 N
a.empty();       // C++11 中永远是 false（N > 0 时）

• 填充 / 赋值

a.fill(0);       // 所有元素赋为同一个值

#include <algorithm>
std::fill(a.begin(), a.end(), 1.0);

• 遍历

for (const auto& x : a) { /* 只读 */ }
for (auto& x : a) { /* 可修改 */ }

for (auto it = a.begin(); it != a.end(); ++it) {
    // *it
}

• 交换

std::array<int, 3> x = {{1,2,3}};
std::array<int, 3> y = {{4,5,6}};
x.swap(y);               // O(N)

• 与 C 数组 / vector 的互操作

//C 数组 → std::array
double c[6] = {1,2,3,4,5,6};
std::array<double, 6> a;
std::copy(c, c + 6, a.begin());

//std::array → std::vector
#include <vector>
std::vector<double> v(a.begin(), a.end());

//作为“数组指针”使用
void foo(const double* p, int n);
foo(a.data(), static_cast<int>(a.size()));

用途建议

• 长度固定（比如 6 个 double）更推荐 array<double,6> 而不是 vector<double>
  • 更快、更省内存、语义明确

3) std::pair<A,B>（二元组/ 键值对）

头文件：#include <utility>

特点

• 用来存储 两个相关的值：first 和 second
• 两个类型可以不同：std::pair<A,B>
• std::map 的元素类型就是 std::pair<const K, V>
• 常用于：
  • 返回两个结果（函数返回值）
  • 存键值对（map/set 插入返回值）
  • 把两个字段临时打包传递/存储

成员

pair.first   // 第一个元素
pair.second  // 第二个元素

创建 / 初始化（C++11）

1）直接构造

std::pair<int, double> p(1, 3.14);

2）用 std::make_pair（自动推导类型）

auto p2 = std::make_pair(2, 2.71);

3）列表初始化（C++11）

std::pair<int, std::string> p3 = {1, "one"};

// 注意：make_pair("one") 里字符串字面量类型是 const char*，如果你想要 std::string，可以显式写：
std::pair<int, std::string> p = std::make_pair(1, std::string("one"));

访问 / 修改

int a = p.first;
double b = p.second;

p.first = 10;
p.second = 0.5;

常见操作

• 函数返回两个值

#include <utility>

std::pair<bool, int> parse() {
    // 成功与结果一起返回
    return std::make_pair(true, 42);
}

int main() {
    std::pair<bool, int> r = parse();
    if (r.first) {
        int value = r.second;
    }
}

• 与 std::map 配合：insert 的返回值

map.insert(...) 返回 std::pair<iterator, bool>：

#include <map>
#include <utility>

std::map<int, int> m;
std::pair<std::map<int,int>::iterator, bool> ret =
    m.insert(std::make_pair(1, 100));

if (ret.second) {
    // 插入成功
    // ret.first 指向新插入的元素
} else {
    // 插入失败（key 已存在）
    // ret.first 指向已有元素
}

• 与 std::set 配合：insert 的返回值

set.insert(x) 返回 pair<iterator, bool>：

#include <set>
#include <utility>

std::set<int> s;
auto ret = s.insert(3);

if (!ret.second) {
    // 3 已存在
}

• 比较（pair 支持比较运算）

pair 默认是 字典序比较：

• 先比较 first
• first 相等再比较 second

std::pair<int,int> a = {1, 5};
std::pair<int,int> b = {2, 0};

bool x = (a < b); // true，因为 1 < 2

• 交换

std::pair<int,int> a = {1, 2};
std::pair<int,int> b = {3, 4};
a.swap(b); // 或 std::swap(a,b)

常见坑

1. pair 不是容器：只能存 2 个值，没有 size()/begin()/end()
2. 类型推导小心字符串字面量：make_pair(1, "one") 的第二个是 const char*
3. map 元素是 pair<const K, V>：it->first 是 const，不能改 key

4) std::map<K,V>（有序键值表）

头文件：#include <map>

特点

• 存储 键值对：(key, value)
• key 唯一（同一个 key 只能出现一次）
• 按 key 自动排序（默认升序，比较器默认 std::less<K>）
• 底层一般是 红黑树（平衡二叉搜索树）
• 常见操作复杂度：查找/插入/删除 O(log N)
• 遍历时会按 key 有序输出

初始化（C++11）

std::map<int, int> m1; // 空

std::map<int, std::string> m2 = {
    {1, "one"},
    {2, "two"}
};

// value 是 vector 的例子
std::map<int, std::vector<double>> m3;
m3[1] = std::vector<double>(6, 0.0);

常用操作

• 查询 / 判断是否存在（不会插入）

std::map<int,int> m;

// find：找到返回迭代器，否则返回 end()
std::map<int,int>::iterator it = m.find(10);
if (it != m.end()) {
    int key = it->first;
    int val = it->second;
}

// count：map 中只可能是 0 或 1
if (m.count(10) != 0) { /* 存在 */ }

• 访问 / 修改 value（存在则改，不存在则插入）

m[10] = 5;          // 若 key=10 不存在，会插入 {10, 0} 再赋值为 5
int x = m[10];      // 若 key=10 不存在，会插入 {10, 0} 并返回 0

// 重要坑：operator[] 会“无意插入”。
如果你希望 key 不存在就报错/不插入，用 find 或 at（但 at 是 C++11 有的，会抛异常）：
// C++11: at 不会插入，但 key 不存在会抛 std::out_of_range
int v = m.at(10);

• 插入（不会覆盖已有 key）

// insert 返回 pair<iterator, bool>
std::pair<std::map<int,int>::iterator, bool> r = m.insert(std::make_pair(1, 100));
if (r.second) {
    // 插入成功
} else {
    // key 已存在，未插入，r.first 指向已有元素
}

// C++11
m.insert(std::pair<int,int>(2, 200));
m.insert(std::make_pair(3, 300));

如果要“存在就改，不存在就插”，最简单：m[key] = value;
如果要“只插不覆盖”，用 insert

• 删除

m.erase(10);             // 按 key 删除（返回删除个数：0 或 1）
m.erase(it);             // 按迭代器删除
m.erase(m.begin(), m.end()); // 删除一个范围（清空）

• 清空

m.clear();

• 遍历（C++11）

for (std::map<int,int>::const_iterator it = m.begin(); it != m.end(); ++it) {
    int k = it->first;
    int v = it->second;
}

// C++11 range-for
for (const auto& kv : m) {
    int k = kv.first;
    int v = kv.second;
}

• 范围查询（有序 map 的优势）

//map 有序，所以可以做“找第一个 >= key”的查询等：
std::map<int,int>::iterator it1 = m.lower_bound(10); // 第一个 key >= 10
std::map<int,int>::iterator it2 = m.upper_bound(10); // 第一个 key > 10

// 等于 key 的范围（map 要么 0 个要么 1 个）
std::pair<std::map<int,int>::iterator, std::map<int,int>::iterator> rg = m.equal_range(10);

//典型用法：遍历区间 [L, R) 的 key
for (auto it = m.lower_bound(L); it != m.lower_bound(R); ++it) {
    // it->first in [L, R)
}

常见坑

• m[key] 会插入默认值：只查存在性不要用它
• insert不会覆盖：key 已存在时插入失败
• key 是 const：it->first 不能改（编译期限制）
• 遍历时按 key 排序，不是插入顺序
• find 是 O(logN)，不是 O(1)（因为树结构）

5) std::set<T>（有序集合，元素唯一）

头文件：#include <set>

特点

• 存储 元素（value），每个元素 唯一（不允许重复）
• 元素会按比较规则 自动排序（默认升序，比较器默认 std::less<T>）
• 底层一般是 红黑树（平衡二叉搜索树）
• 查找/插入/删除复杂度：O(log N)
• 适合：去重 + 有序输出、快速判断元素是否存在

初始化（C++11）

std::set<int> s1;                 // 空
std::set<int> s2 = {3, 1, 2, 2};   // 去重后为 {1,2,3}

指定排序规则（降序）：

#include <functional>
std::set<int, std::greater<int> > s3 = {1,2,3}; // {3,2,1}

常用操作

• 查询 / 判断是否存在

std::set<int> s = {1,2,3};

// find：找到返回迭代器，否则返回 end()
std::set<int>::iterator it = s.find(2);
if (it != s.end()) {
    // 找到了 *it == 2
}

// count：set 中只可能是 0 或 1
if (s.count(2) != 0) {
    // 存在
}

• 插入（重复会失败）

std::pair<std::set<int>::iterator, bool> r = s.insert(5);
if (r.second) {
    // 插入成功
} else {
    // 元素已存在，未插入，r.first 指向已有元素
}

// 也可以批量插入（C++11 initializer_list）：
s.insert({7, 8, 9});

• 删除

// 按值删除：
s.erase(2);   // 返回删除个数：0 或 1

// 按迭代器删除：
std::set<int>::iterator it = s.find(3);
if (it != s.end()) s.erase(it);

// 按范围删除：
s.erase(s.begin(), s.end()); // 清空（也可以用 clear）

• 清空 / 大小

s.clear();
s.size();
s.empty();

• 遍历（有序）

for (const auto& x : s) {
    // x 按序输出
}

for (std::set<int>::const_iterator it = s.begin(); it != s.end(); ++it) {
    int x = *it;
}

• 范围查询（有序 set 的优势）

// 第一个 >= key
std::set<int>::iterator it1 = s.lower_bound(5);

// 第一个 > key
std::set<int>::iterator it2 = s.upper_bound(5);

// 等于 key 的范围（set 要么 0 个要么 1 个）
std::pair<std::set<int>::iterator, std::set<int>::iterator> rg = s.equal_range(5);

// 典型用法：遍历区间 [L, R)
for (auto it = s.lower_bound(L); it != s.lower_bound(R); ++it) {
    // *it in [L, R)
}

典型用途

• 去重 + 保持有序
• 需要做范围查询（lower_bound/upper_bound）
• 频繁判断“某元素是否出现过”

常见坑

• set 里元素不能重复：插入重复元素会失败（不会报错，只是 insert().second == false）
• 元素是“只读”的：不能通过迭代器修改元素值，因为改值可能破坏排序结构，想“修改元素”通常做法：erase(old) 再 insert(new)
• find/count 是 O(logN)，不是 O(1)（树结构）
• 遍历顺序是 按排序规则，不是插入顺序

6) std::unordered_map<K, V>（哈希键值表，平均 O(1)）

头文件：#include <unordered_map>
（常用：#include <utility> 用 std::make_pair）

特点

• 存储 键值对 (key, value)，key 唯一
• 不排序（遍历顺序不可预测，会随 rehash 改变）
• 底层是 哈希表
• 平均查找/插入/删除 O(1)，最坏可能 O(N)（哈希冲突极端情况）
• 适合：只想快速查找，不关心顺序

初始化（C++11）

std::unordered_map<int, std::string> um1; // 空

std::unordered_map<int, std::string> um2 = {
    {1, "one"},
    {2, "two"}
};

常用操作

• 查询 / 判断是否存在（不会插入）

std::unordered_map<int,int> um;

auto it = um.find(10);        // 找到返回迭代器，否则 end()
if (it != um.end()) {
    int v = it->second;
}

if (um.count(10) != 0) {      // 0 或 1
    // 存在
}

• 访问 / 修改（存在则改，不存在则插入默认值）

um[10] = 5;        // 不存在则插入 {10, 0} 再赋值为 5
int x = um[99];    // 不存在则插入 {99, 0} 并返回 0

// 如果你不想插入，用 find，或用 at（C++11 有，key 不存在抛异常）：
int v = um.at(10); // key 不存在会抛 std::out_of_range

• 插入（不会覆盖已有 key）

auto ret = um.insert(std::make_pair(1, 100));
// ret: pair<iterator, bool>
if (ret.second) {
    // 插入成功
} else {
    // key 已存在，未插入
}

• 删除

um.erase(10);   // 按 key 删除，返回删除个数（0 或 1）

auto it = um.find(5);
if (it != um.end()) um.erase(it); // 按迭代器删除

• 清空 / 大小

um.clear();
um.size();
um.empty();

• 遍历（无序）

for (const auto& kv : um) {
    // kv.first, kv.second
}

• rehash / 负载因子（性能相关，进阶但很常用）

um.reserve(1000);        // 预留（减少 rehash 次数）
um.rehash(2048);         // 强制桶数量（bucket count）至少到指定值
float lf = um.load_factor();      // 当前负载因子
um.max_load_factor(0.7f);         // 设定最大负载因子（默认通常 1.0）
// reserve 很实用：当你预估元素很多时，提前 reserve 能显著减少 rehash。

常见坑

1. 遍历顺序不稳定：不要依赖输出顺序
2. operator[] 会 插入默认值：只想查存在用 find/count
3. rehash 会使迭代器失效（以及 bucket 相关状态变化）
4. key 类型需要 std::hash<K> 支持；自定义类型要提供 hash 和相等判断（见下方）

自定义 key（hash + equal）

例如你用 struct Key { int a,b; }; 做 key：

#include <unordered_map>

struct Key {
    int a, b;
};

struct KeyHash {
    std::size_t operator()(const Key& k) const {
        // 简单组合（示例）
        return std::hash<int>()(k.a) ^ (std::hash<int>()(k.b) << 1);
    }
};

struct KeyEq {
    bool operator()(const Key& x, const Key& y) const {
        return x.a == y.a && x.b == y.b;
    }
};

std::unordered_map<Key, int, KeyHash, KeyEq> um;

与 map 的选择

• 要排序/范围查询（lower_bound 等）：用 map
• 只要快速查找：用 unordered_map

7) std::unordered_set<T>（哈希集合，平均 O(1)）

头文件：#include <unordered_set>

特点

• 存储 元素（value），每个元素 唯一
• 不排序，遍历顺序不可预测
• 平均查找/插入/删除 O(1)

初始化（C++11）

std::unordered_set<int> us1;
std::unordered_set<int> us2 = {3, 1, 2, 2}; // 去重后包含 {1,2,3}

常用操作

• 查询/存在性

auto it = us2.find(2);
if (it != us2.end()) {}

if (us2.count(2) != 0) {} // 0 或 1

• 插入（重复失败）

auto ret = us2.insert(5); // pair<iterator,bool>
if (!ret.second) {
    // 5 已存在
}

• 删除/清空

us2.erase(2); // 0或1
us2.clear();

• 遍历（无序）

for (const auto& x : us2) {}

• 性能相关

us2.reserve(1000);
us2.max_load_factor(0.7f);

常见坑（重点）

1. 无序：不要期待升序/插入顺序
2. rehash 可能导致迭代器失效
3. 自定义类型同样需要 hash + equal（和 unordered_map 类似）

unordered_* vs map/set 如何选择（快速选型）

用 unordered_map / unordered_set：

• 只关心“是否存在/快速查找”
• 不需要排序、不需要范围查询
• 追求平均性能 O(1)

用 map / set：

• 需要按 key 有序遍历
• 需要范围查询：lower_bound/upper_bound
• 希望复杂度稳定 O(logN)（不会退化到 O(N)）

8) std::deque<T>（双端队列）

头文件：#include <deque>

特点

• 双端操作快：在队首/队尾插入、删除都是 O(1)（均摊）
• 支持 随机访问：d[i] / d.at(i)（O(1)）
• 不是连续内存（通常是分段连续），因此：
  • data() 在 C++11 的 deque 不保证存在/不可用作连续数组指针
  • 遍历也很快，但 cache 友好程度一般不如 vector
• 常见用途：
  • 需要频繁 push_front 的场景
  • queue/stack 的默认底层容器
  • 滑动窗口、双端操作的队列逻辑

初始化（C++11）

std::deque<int> d1;                // 空
std::deque<int> d2(5);             // 5 个 0
std::deque<double> d3(6, 0.0);     // 6 个 0.0
std::deque<int> d4 = {1,2,3};      // 列表初始化

常用操作

• 访问（读 / 写）

d[i];          // 不检查越界（越界=未定义行为）
d.at(i);       // 越界抛 std::out_of_range
d.front();     // 队首元素（要求非空）
d.back();      // 队尾元素（要求非空）

• 双端插入 / 删除（deque 的核心优势）

d.push_back(x);     // 尾部追加
d.push_front(x);    // 头部追加

d.pop_back();       // 删除尾部
d.pop_front();      // 删除头部

• 中间插入 / 删除（一般为 O(N)）

d.insert(d.begin() + pos, x);
d.erase(d.begin() + pos);

d.erase(d.begin() + l, d.begin() + r); // 删除区间 [l, r)

• 赋值 / 重置 / 调整大小

d.clear();               // 清空
d.assign(6, 0.0);        // 重置为 6 个 0.0
d.resize(10);            // 改长度（扩展补默认值 T()）
d.resize(10, 3.14);      // 扩展用 3.14 填充

• 大小 / 判空

d.size();
d.empty();

• 遍历（C++11）

for (const auto& x : d) { /* 只读 */ }
for (auto& x : d) { /* 可修改 */ }

for (auto it = d.begin(); it != d.end(); ++it) {
    // *it
}

例子：滑动窗口（双端队列典型场景）

维护一个“单调队列”求窗口最大值（核心思想示例）：

#include <deque>
#include <vector>

// 这里只展示 deque 的 push_front/push_back/pop_front/pop_back 的使用思路

与 vector 的选择建议

选 deque：

• 经常在 头部 插入/删除（push_front/pop_front）
• 需要随机访问但不要求连续内存

选 vector：

• 主要在 尾部 操作
• 需要 data() 连续内存（传 C 接口/高性能拷贝）
• 更强的 cache 友好性

常见坑

1. front()/back() 在空 deque 上调用是 未定义行为：先 empty()
2. deque 通常 不是连续内存：不要把它当数组指针用（C++11 下不要依赖 data()）
3. 中间 insert/erase 仍可能是 O(N)（需要移动元素）
4. 迭代器失效规则比 list/map 更“敏感”：插入/删除可能导致部分迭代器失效（保守做法：插入/删除后不要复用旧迭代器）

9) std::list<T>（双向链表）

头文件：#include <list>

特点

• 底层是 双向链表（每个节点存元素 + 前后指针）
• 任意位置插入/删除很快：给定迭代器时 O(1)
• 不支持随机访问：没有 operator[]，不能 it + n
• 遍历访问是 O(N)，cache 友好性较差（节点分散）
• 迭代器在插入时通常稳定（删除只会使被删节点的迭代器失效）
• 适合：频繁在中间插入/删除、需要迭代器长期有效的场景

初始化（C++11）

std::list<int> l1;             // 空
std::list<int> l2(5);          // 5 个 0
std::list<double> l3(6, 0.0);  // 6 个 0.0
std::list<int> l4 = {1,2,3};   // 列表初始化

常用操作

• 访问

l.front();     // 首元素（要求非空）
l.back();      // 尾元素（要求非空）

std::list 没有 []、没有 at()。

• 插入 / 删除（list 的核心优势）

头尾插入删除

l.push_front(x);
l.push_back(x);

l.pop_front();
l.pop_back();

任意位置插入删除（给定迭代器）

auto it = l.begin();
++it;                       // 指向第二个元素
l.insert(it, 99);           // 在 it 前插入 99（O(1)）
l.erase(it);                // 删除 it 指向元素（O(1)），返回下一个迭代器

删除区间

l.erase(first, last);       // 删除 [first, last)

按值删除（非常常用）

l.remove(3);                // 删除所有值等于 3 的元素（O(N)）

条件删除（C++11，lambda）：

l.remove_if([](int x){ return x % 2 == 0; }); // 删除所有偶数

• 清空 / 大小

l.clear();
l.size();
l.empty();

• 遍历（C++11）

for (const auto& x : l) { /* 只读 */ }
for (auto& x : l) { /* 可修改 */ }

for (auto it = l.begin(); it != l.end(); ++it) {
    // *it
}

• list 专有/常用高级操作（很多人忽略，但很强）

splice：把另一个 list 的节点“摘过来”（几乎 O(1)）

std::list<int> a = {1,2,3};
std::list<int> b = {10,20,30};

auto pos = a.begin();
++pos; // 指向2

// 把 b 的所有元素移动到 a 的 pos 前面（不拷贝元素，移动节点）
a.splice(pos, b);
// 此后 b 变空，a 变为 {1,10,20,30,2,3}

unique：去掉相邻重复（只处理相邻！）

std::list<int> l = {1,1,2,2,2,3};
l.unique(); // 结果 {1,2,3}

如果你要“全局去重”，通常先 sort() 再 unique()。

sort：list 自带排序（因为不能随机访问，所以不能用 std::sort）

l.sort(); // 默认升序

自定义排序：

l.sort([](int a, int b){ return a > b; }); // 降序

merge：合并两个已排序 list（经典 O(N)）

std::list<int> a = {1,3,5};
std::list<int> b = {2,4,6};
a.merge(b); // a={1,2,3,4,5,6}, b 变空

reverse：反转

l.reverse();

例子：需要频繁中间插入/删除的场景

#include <list>

std::list<int> l = {1,2,3,4};

// 找到元素 3 的位置后删除（迭代器删除是 O(1)）
for (auto it = l.begin(); it != l.end(); ++it) {
    if (*it == 3) {
        l.erase(it);
        break;
    }
}

常见坑

1. 不能随机访问：l[i]、it + n 都不行
2. std::sort 不能用于 list（需要随机访问迭代器），要用 l.sort()
3. front/back 空 list 调用是未定义行为：先 empty()
4. unique() 只去掉 相邻重复，要全局去重通常要先排序

什么时候选 list

适合：

• 频繁在中间插入/删除（并且你持有迭代器位置）
• 需要 splice/merge 这种“移动节点不拷贝”的能力
• 需要插入/删除后迭代器尽量稳定

不适合：

• 需要大量随机访问、下标访问 → 用 vector/deque
• 追求遍历性能（cache） → vector 通常更快

10) 容器适配器：stack / queue / priority_queue

std::stack<T>（栈 LIFO，后进先出）

头文件：#include <stack>
可选：如果你指定底层容器，可能还需要 #include <deque> 或 #include <vector> 或 #include <list>

特点

• 后进先出（LIFO）：最后入栈的最先出栈
• 是一个容器适配器（adapter）：内部用别的容器实现
  • 默认底层容器：std::deque<T>
• 不支持遍历（没有 begin()/end()）
• 常用场景：括号匹配、表达式求值、DFS、撤销/回退、函数调用栈模型

创建 / 初始化（C++11）

std::stack<int> st;                      // 默认底层 deque<int>

// 指定底层容器（可选）：例如用 vector 做底层
std::stack<int, std::vector<int> > st2;
//底层容器必须支持：push_back / pop_back / back / empty / size

常用操作

• 1）入栈 / 出栈

st.push(x);      // 入栈（压栈）
st.pop();        // 出栈（弹栈）⚠️不返回被删元素
// pop()不会返回元素；要先 top()取值再 pop()。

• 访问栈顶

st.top();        // 访问栈顶元素（最后入栈的）

前提：栈非空，否则未定义行为。通常先判断：

if (!st.empty()) {
    int x = st.top();
}

• 大小 / 判空

st.size();
st.empty();

• 清空（stack 没有 clear）

std::stack 没有 clear() 成员函数，清空方式：

方式 A：循环 pop

while (!st.empty()) st.pop();

方式 B：与空栈 swap（常用且快）

std::stack<int> empty;
st.swap(empty);

• 交换

std::stack<int> a, b;
a.swap(b);

例子：典型用法模板（取出并处理）

#include <stack>

std::stack<int> st;
st.push(1);
st.push(2);
st.push(3);

while (!st.empty()) {
    int x = st.top();
    st.pop();
    // 处理 x（输出顺序：3,2,1）
}

例子：括号匹配（经典）

#include <stack>
#include <string>

bool isValid(const std::string& s) {
    std::stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '[' || c == '{') st.push(c);
        else {
            if (st.empty()) return false;
            char t = st.top(); st.pop();
            if ((c == ')' && t != '(') ||
                (c == ']' && t != '[') ||
                (c == '}' && t != '{')) return false;
        }
    }
    return st.empty();
}

常见坑

1. pop() 不返回值：要先 top() 再 pop()
2. top() 在空栈上调用是 未定义行为：先 empty()
3. std::stack 不能遍历：要遍历就用底层容器（如 vector/deque）自己管理
4. std::stack 没有 clear()：用循环 pop 或 swap 清空

什么时候选 stack

适合：

• LIFO 逻辑（回退/撤销、DFS、解析器、括号匹配）

不适合：

• 需要遍历或随机访问
• 需要 FIFO → 用 queue
• 需要按优先级 → 用 priority_queue

std::queue<T>（队列 FIFO，先进先出）

头文件：#include <queue>
可选：如果要指定底层容器，可能还需要 #include <deque> 或 #include <list>

特点

• 先进先出（FIFO）：先入队的先出队
• 是一个容器适配器（adapter）：内部用别的容器实现（默认 std::deque<T>）
• 不支持遍历（没有 begin()/end()），只能通过接口操作队首/队尾
• 常用场景：BFS、任务队列、生产者-消费者缓冲（单线程逻辑）

创建 / 初始化（C++11）

std::queue<int> q;                 // 默认底层容器 deque<int>

// 指定底层容器（可选）：例如用 list 作为底层
std::queue<int, std::list<int> > q2;

//底层容器必须支持：push_back / pop_front / front / back / empty / size

常用操作

q.push(x);      // 入队（放到队尾）
q.pop();        // 出队（删除队首元素）⚠️不返回被删元素
// pop()不会返回元素；要先 front() 取值再 pop()

q.front();      // 访问队首元素（最先入队的）
q.back();       // 访问队尾元素（最后入队的）

if (!q.empty()) {
    int x = q.front();
}

q.size();       // 元素个数
q.empty();      // 是否为空

while (!q.empty()) q.pop();

std::queue<int> empty;
q.swap(empty);

std::queue<int> q1, q2;
q1.swap(q2);

例子：典型用法模板（取出并处理）

#include <queue>

std::queue<int> q;
q.push(1);
q.push(2);
q.push(3);

while (!q.empty()) {
    int x = q.front();
    q.pop();
    // 处理 x
}

例子：BFS（广度优先搜索）核心写法

#include <queue>

std::queue<int> q;
q.push(start);

while (!q.empty()) {
    int u = q.front();
    q.pop();

    // for (v in neighbors[u]) if (!vis[v]) { vis[v]=true; q.push(v); }
}

常见坑

1. pop() 不返回值：要先 front() 再 pop()
2. front()/back() 在空队列上调用是 未定义行为：先 empty()
3. std::queue 不能遍历：如果你需要遍历/随机访问，考虑直接用 deque/vector
4. std::queue 没有 clear()：用循环 pop 或 swap 清空

什么时候选 queue

适合：

• FIFO 任务处理
• BFS
• 单线程或用锁保护的生产者-消费者队列（简单版）

不适合：

• 需要按序遍历、随机访问
• 需要按优先级出队（用 priority_queue）

std::priority_queue<T>（优先队列/堆）

头文件：#include <queue>
注意：常用还会用到：#include <vector>、#include <functional>

特点

• 每次 top() 拿到的是“优先级最高”的元素
• 默认是 大顶堆（最大值优先出）
• 是一个容器适配器：底层默认 std::vector<T>
• 不支持遍历（没有 begin()/end()），只能通过 top/push/pop
• 常用场景：TopK、调度器、Dijkstra/A*、合并 K 个有序序列、事件模拟

创建 / 初始化（C++11）

1）默认：大顶堆（最大元素在 top）

#include <queue>

std::priority_queue<int> pq;

2）小顶堆（最小元素在 top，最常用配置）

#include <queue>
#include <vector>
#include <functional>

std::priority_queue<int, std::vector<int>, std::greater<int> > minpq;
// 说明：模板参数含义
priority_queue<T, Container, Compare>

Container 默认 vector<T>
Compare 默认 std::less<T>（因此是大顶堆）

常用操作

• 插入 / 弹出

pq.push(x);      // 插入
pq.pop();        // 弹出堆顶（⚠️不返回元素）
// pop()不返回值：要先 top()再 pop()。

• 访问堆顶

pq.top();        // 查看堆顶元素（优先级最高）

前提：队列非空，否则未定义行为：

if (!pq.empty()) {
    int x = pq.top();
}

• 大小 / 判空

pq.size();
pq.empty();

• 清空（priority_queue 没有 clear）

方式 A：循环 pop

while (!pq.empty()) pq.pop();

方式 B：swap 空队列（常用且快）

std::priority_queue<int> empty;
pq.swap(empty);

例子：大顶堆基本用法

#include <queue>
#include <iostream>

std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(5);

while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
}
// 输出：5 3 1

例子：小顶堆（最小优先）

#include <queue>
#include <vector>
#include <functional>
#include <iostream>

std::priority_queue<int, std::vector<int>, std::greater<int> > pq;
pq.push(3);
pq.push(1);
pq.push(5);

while (!pq.empty()) {
    std::cout << pq.top() << " ";
    pq.pop();
}
// 输出：1 3 5

例子：Top K 最大值（用小顶堆更省）

思路：保持堆大小为 K，小顶堆里存“当前最大的 K 个”，堆顶是这 K 个里最小的。

#include <queue>
#include <vector>
#include <functional>

std::vector<int> nums = {5, 2, 9, 1, 7, 3};
int K = 3;

std::priority_queue<int, std::vector<int>, std::greater<int> > heap;

for (size_t i = 0; i < nums.size(); ++i) {
    heap.push(nums[i]);
    if ((int)heap.size() > K) heap.pop();
}
// heap 里就是最大的 3 个数，heap.top() 是这 3 个里最小的

自定义比较器（存结构体/按某字段排）

假设要按 priority 大的优先：

#include <queue>
#include <vector>

struct Task {
    int id;
    int priority;
};

// Compare：返回 true 表示 “a 的优先级比 b 低”（放到后面）
// 这样 top() 就是 priority 最大的
struct Cmp {
    bool operator()(const Task& a, const Task& b) const {
        return a.priority < b.priority; // priority 大的更靠前
    }
};

std::priority_queue<Task, std::vector<Task>, Cmp> pq;

使用：

pq.push(Task{1, 10});
pq.push(Task{2, 5});
Task t = pq.top(); // id=1

常见坑

1. pop() 不返回值：要先 top() 再 pop()
2. 空队列调用 top() 是 未定义行为：先 empty()
3. priority_queue 不能遍历：如果你想“查看所有元素”，只能不断 pop（会破坏结构），或自己额外复制一份再 pop
4. 比较器方向容易写反：
   • 默认是大顶堆
   • 小顶堆要用 std::greater<T>
5. 修改堆顶元素：不能直接改 top() 对应的底层值（会破坏堆），正确做法是 pop 再 push 新值

什么时候选 priority_queue

适合：

• 总是要拿最大/最小
• TopK
• 最短路（Dijkstra：通常用小顶堆）
• 任务调度（按优先级处理）

不适合：

• 需要按插入顺序 FIFO → 用 queue
• 需要随机访问/遍历 → 用 vector/deque 自己管理

常用算法头文件（配合容器经常用）

• #include <algorithm>：sort/find/copy/min/max/...
• #include <numeric>：accumulate
• #include <iterator>：std::begin/std::end（C++11）
• #include <functional>：比较器 std::greater<> 等

复杂度速查表