顺序容器

直觉：为什么不能只用一种容器？

你已经学了用 vector 装数据——它简单好用，往末尾塞数据又快又稳。但如果你的程序需要在开头频繁插入、在中间随机删除、或者数据量巨大——vector 就开始喘气了。

想象工厂里有六种物料箱：长条槽（vector）按顺序排放零件、取第 N 个直接走过去就行——但想在中间插一个？后面所有零件都得往后挪。分段托盘（deque）两端都能快速取放。链条挂架（list）每个零件独立挂着——插哪都只是挂个钩子，不用搬别的零件。单向流水钩（forward_list）每个零件只知道下一个在哪——轻便但只能往一个方向走。固定格子盘（array）出厂就焊死格子数——零额外开销。标签带（string）专门处理字符——除了当容器，还能搜索、切割、比较。

没有选型意识会怎样？ 你可能把 vector 当万能容器用——在所有场景都用它——结果程序运行得越久越慢，内存碎片化，一个简单操作要搬动成千上万个元素。这一章教你六种容器的内部构造——从此「这个场景该用什么」你心里有数。

六种容器，六种底层结构

在 C++ 里，顺序容器（sequential container） 就是按你插入的顺序存放元素的盒子——第一个塞进去的元素就在第一个位置。但不同的「盒子」内部结构完全不同——这决定了哪些操作快、哪些操作慢。

上面这张图把六种容器的内部结构并排展示——注意它们的核心差异：

• vector：一块连续内存，像一排紧挨着的停车位。访问第 N 个车位——直接算地址、O(1)。想在中间插一个车位——后面的车全部要挪（O(n)）。尾部加车——有预留车位就直接停，否则重新划一片更大的地。
• deque：分段存储——由多个固定大小的数据块拼成，中间由一个指针数组串起来。两端都能快速插（O(1)），访问也需要通过指针中转（仍是 O(1)，比 vector 多一次间接跳转）。
• list：每个元素独立存储——每个「节点」里除了数据还有两个指针——指向前一个节点和后一个节点。插入删除只改四个指针——O(1)，不搬动任何其他元素。代价是不能随机访问——要找第 N 个必须从头走（O(n)）。
• forward_list：list 的瘦身版——每个节点只存一个 next 指针。更省内存，但只能向前走——没有 --iter，没有 push_back。
• array：固定大小——大小写死在模板参数里。零额外开销——不分配堆内存，没有 capacity 管理。代价是大小不能改——不能 push_back，不能 insert。
• string：专为字符设计——和 vector<char> 一样是连续存储，但多了专属武器：substr 切子串、find 搜索、compare 比较、+ 拼接。许多实现使用短字符串优化（SSO），但这不是标准要求，不能依赖具体内联容量。

所有容器都听你的同一套指令

不管你选了哪种容器，C++ 给你一套 迭代器（iterator） 让你用同样的方式遍历、读、写——begin() 永远指第一个元素，end() 永远指最后一个元素之后的位置，*iter 解引用得到元素自己。

#include <iostream>
#include <vector>
#include <list>
 
// 同一个模板对 vector / list 通用——只要容器支持迭代器
template <typename Container>
void print_all(const Container &c) {
    // auto 让编译器推导迭代器类型——vector/list 都能用
    for (auto it = c.cbegin(); it != c.cend(); ++it)
        std::cout << *it << ' ';
    std::cout << '\n';
}
 
int main() {
    std::vector<int> v = {1, 2, 3};
    std::list<int>   lst = {4, 5, 6};
 
    print_all(v);   // 1 2 3
    print_all(lst); // 4 5 6
}

上面的 print_all 函数——对 vector 和 list 用同一套代码遍历。除了 cbegin()/cend()（只读），还有 begin()/end()（可读写）、crbegin()/crend()（反向只读）。

除了迭代器，所有容器还有一套共同的增删改操作：

std::vector<int> a = {1, 2, 3};
std::vector<int> b = {4, 5, 6};
 
a.swap(b);        // 同类型容器交换内容；vector 与 list 不能互换
 
a.assign(5, 42);  // 替换内容为 5 个 42 → [42,42,42,42,42]
a.clear();        // 清空所有元素——size 变 0

下面这张表帮你速查——哪些操作在哪个容器上支持、效率如何：

最重要的两个记忆点：

1. push_back——vector/deque/list/string 都有——vector/string 尾部最快（均摊 O(1)），deque O(1)，list O(1)。forward_list 和 array 没有。
2. insert——在已知位置插入时，list/forward_list 修改链接为 O(1)；若还要从头查找位置，总成本仍是 O(n)。vector/deque/string 可能搬移元素，array 不支持改变大小。

官方 Chapter 9 的完整容器操作契约

原书不是只列出六个容器，而是要求把“选择容器、构造与赋值、增删元素、失效规则、容量管理、string 专用接口、适配器”连成一套决策。容器的渐进复杂度必须和元素移动成本、缓存局部性、查找位置的成本一起判断。

构造、赋值与 forward_list 的特殊接口

容器可由大小、值、迭代器范围或初始化列表构造。范围构造允许不同但可转换的元素类型，也允许在不同容器类型之间复制元素；普通拷贝构造则要求容器和元素类型一致。assign 会替换全部元素，swap 交换同类型容器的内容。array 的大小是类型的一部分，所以 array<int, 4> 与 array<int, 8> 是不同类型。

forward_list 没有高效的“前一个节点”可用，因此提供 before_begin()、insert_after() 和 erase_after()。若只记住其他容器的 insert(pos)，就无法正确表达单链表操作：

std::forward_list<int> values = {2, 3};
auto before = values.before_begin();
values.insert_after(before, 1); // {1, 2, 3}
values.erase_after(before);     // 删除 1，恢复 {2, 3}

迭代器失效：修改后还能用什么

迭代器失效（iterator invalidation） 必须按容器和操作判断：

• list 与 forward_list 插入不使已有迭代器失效，删除只使指向被删元素的迭代器、指针和引用失效。
• vector 与 string 重分配会使全部迭代器、指针和引用失效；未重分配的插入会使插入点及其后的失效，删除会使删除点及其后的失效。
• deque 在中间插入会使全部迭代器、指针和引用失效；两端插入也会使迭代器失效，但既有元素的引用和指针保持有效。删除规则更细，修改后最稳妥的做法是重新取得位置。
• 不要缓存 end() 后再修改容器。循环中插入或删除时，应使用操作返回的新迭代器，并按该容器规则决定哪些旧位置还能使用。

string 专用操作与数值转换

string 操作（string operations） 包括按位置构造、substr、append、replace、多组 find 和 compare。搜索失败返回 string::npos，它是无符号的 size_type 最大值，不能先转成有符号整数再与 -1 混用：

std::string text = "name=alice;score=92";
auto split = text.find(';');
if (split != std::string::npos) {
    auto namePart = text.substr(0, split);
    text.replace(split + 1, 6, "points");
}
 
int value = std::stoi("92");
std::string rendered = std::to_string(value + 8); // "100"

stoi、stol、stof、stod 等转换函数可通过位置参数报告解析到哪里，并会在格式无效或超出范围时抛异常。它们比手写字符运算清晰，但处理外部输入时必须捕获并区分失败原因。

vector 的隐藏能力：capacity 和 reserve

你已经知道 v.size() 返回元素个数。但 vector 还有一个不常被注意的「幕后容量」——capacity 和 size 不是一回事。

用 Stepper 一步步看 vector 在 push_back 的过程中 capacity 如何变化。图里的 0、1、2、4 是一种常见实现的示意轨迹，不是标准规定的增长倍率；程序只能依赖“容量足够且连续追加具有均摊常数复杂度”。

先预测：执行 reserve(8) 后，size()、capacity() 和可安全下标访问的元素数分别是多少？再连续追加 9 个元素，哪些旧迭代器必然在某一刻失效？先写答案，再逐步看图验证。

实用技巧——如果你事先知道大概要装多少个元素：

std::vector<int> scores;
scores.reserve(10000);  // 预分配 10000 个槽位
for (int i = 0; i < 10000; ++i)
    scores.push_back(compute_score(i));  // 这 10000 次都不扩容
scores.shrink_to_fit();  // 回收多余内存（请求，不保证立即释放）

reserve(n) 前一定要确认 n 大于当前 capacity() 才有意义。reserve 只影响 capacity——不影响 size——不能用来添加元素。

三个适配器——让 deque 变成栈、队列、堆

你已经有了底层容器（deque、vector、list）——但有时候你不想暴露这么多操作。比如需要一个「只能从一端进出」的栈——你不用自己写一个类，C++ 提供了 容器适配器（container adaptor）——包装底层容器，只露出你需要的那几个接口。

三种适配器用受限接口表达不同访问纪律；stack 与 queue 默认包装 deque，priority_queue 默认包装 vector：

#include <stack>
#include <queue>
 
// stack：后进先出——最后放进去的最先拿出来
std::stack<int> stk;
stk.push(1);  stk.push(2);  stk.push(3);
while (!stk.empty()) {          // 输出 3 2 1
    std::cout << stk.top();     // 只能看栈顶
    stk.pop();
}
 
// queue：先进先出——最先放进去的最先拿出来
std::queue<int> q;
q.push(1);  q.push(2);  q.push(3);
while (!q.empty()) {            // 输出 1 2 3
    std::cout << q.front();     // 看队首（最早入队）
    q.pop();                    // 从队首移除
}
 
// priority_queue：按优先级——大的（默认）先出来
std::priority_queue<int> pq;
pq.push(3);  pq.push(1);  pq.push(5);  pq.push(2);
while (!pq.empty()) {           // 输出 5 3 2 1
    std::cout << pq.top();      // 总是当前最大的
    pq.pop();
}

关键规则——适配器不提供自己的存储；你可以采用默认底层容器，也可以显式指定满足所需操作的容器：

// 默认底层容器：
std::stack<int> s1;                 // 底层用 deque<int>
std::queue<int> q1;                 // 底层用 deque<int>
std::priority_queue<int> pq1;       // 底层用 vector<int>
 
// 显式指定底层容器：
std::stack<int, std::vector<int>> s2;         // 用 vector 作底层
std::queue<int, std::list<int>> q2;           // 用 list 作底层
// std::queue<int, std::vector<int>> q3;      // 错误！vector 没有 pop_front

queue 不能用 vector 作底层——因为 vector 没有 pop_front()（从前面删除是 O(n) 的，queue 要求 O(1)）。priority_queue 不能用 list 作底层——因为堆操作需要随机访问。

实战：选对容器——四个场景对比

场景一：成绩管理系统——频繁在末尾添加、偶尔排序

#include <vector>
#include <algorithm>
#include <iostream>
 
int main() {
    std::vector<int> scores;
 
    // 读入阶段：只做 push_back —— vector 均摊 O(1)
    int s;
    while (std::cin >> s)
        scores.push_back(s);
 
    // 排序阶段：需要随机访问 —— vector 支持，list 不支持
    std::sort(scores.begin(), scores.end());
 
    // 输出统计
    if (!scores.empty())
        std::cout << "中位数: " << scores[scores.size() / 2] << '\n';
}

选 vector 而不是 list 的关键原因——std::sort 要求 RandomAccess 迭代器——list 的迭代器只能 ++/--，不能 it + n。

场景二：LRU 缓存——频繁在任意位置增删

对于这个场景，list 是自然选择——splice 操作直接把一个节点从任意位置「移植」到另一个位置，不拷贝数据，不释放内存：

#include <list>
#include <string>
#include <iostream>
#include <algorithm>
 
int main() {
    std::list<std::string> cache;
 
    // 初始化缓存
    cache.push_back("home");
    cache.push_back("settings");
    cache.push_back("profile");
 
    // 访问 "settings" —— 把它移到最前面
    auto it = std::find(cache.begin(), cache.end(), "settings");
    if (it != cache.end())
        cache.splice(cache.begin(), cache, it);
    // splice 是 O(1)：把节点从 it 位置取下，接到 begin() 前
 
    for (auto &s : cache)
        std::cout << s << ' ';  // settings home profile
}

splice 是 list 的独门武器——它只修改几个指针，O(1)——比任何「拷贝+删除+插入」的方案快得多。vector 不可能做到这一点——vector 的 erase + insert 需要搬动所有元素，O(n)。

但这个示例用 std::find 查找页面，查找本身仍是 O(n)。真正要求访问、移动、淘汰都为 O(1) 的 LRU，通常把 list 与 unordered_map<Key, list::iterator> 组合：哈希表定位节点，splice 只负责移动节点。

场景三：文本编辑器——频繁在中间插入删除字符

list<char> 在中间插入字符 O(1)——不搬动其他字符。但同时也丧失了随机访问——跳到第 100 个字符需要走 100 步。这就是经典的「时间-空间-功能」三角权衡：

#include <list>
#include <string>
#include <iostream>
 
int main() {
    std::list<char> text = {'H', 'e', 'l', 'o'};  // "Helo" — 少了第二个 'l'
 
    // 中间插入 'l'：找到 'o' 的位置，在它前面插入
    auto pos = std::find(text.begin(), text.end(), 'o');
    text.insert(pos, 'l');  // O(1) — 只改指针，不改其他字符
 
    for (char c : text)
        std::cout << c;  // Hello
}

string 的 insert 需要移动插入点后的字符，单次为 O(n)。list<char> 说明了“位置已知时改链接”的复杂度，但它不是成熟文本编辑器的通用答案：逐字符节点有显著内存和缓存代价，随机跳转也慢。真实编辑器通常使用 gap buffer、piece table 或 rope，并按光标局部性、撤销模型和大文件需求选型。

场景四：令牌桶限流器——两端操作

deque 是标准顺序容器中的合适默认选择——vector 没有 pop_front，list 虽支持两端操作但承担逐节点分配成本。若只需 FIFO 接口，可直接使用默认基于 deque 的 queue；固定容量高性能场景还可能采用环形缓冲区。因此这里是基于需求的选择，不是唯一可能实现。

#include <deque>
#include <iostream>
 
int main() {
    std::deque<int> tokens;
 
    // 定时补充：从后端放令牌
    for (int i = 0; i < 5; i++)
        tokens.push_back(i);
 
    // 请求消耗：从前端取令牌
    while (!tokens.empty()) {
        int token = tokens.front();  // peek 而不 pop
        std::cout << "使用令牌 " << token << '\n';
        tokens.pop_front();          // O(1)
    }
}

选型速查

容易踩的坑

小结

• 六种顺序容器按底层结构分三类：连续存储（vector/string/array）随机访问 O(1) 但中间插入 O(n)；链式存储（list/forward_list）任意位置插入 O(1) 但不支持随机访问；分段存储（deque）兼顾两端插入 O(1) 和随机访问 O(1)
• 所有容器共享一套迭代器接口——begin()/end()、*iter、++iter——同一套代码可遍历不同容器；vector 的 push_back 扩容会令所有迭代器失效，list 的 erase 只让被删元素的迭代器失效
• vector 的 capacity ≥ size——reserve(n) 预分配内存避免反复扩容、shrink_to_fit() 只是回收请求；实现采用几何增长以提供均摊 O(1) 追加，但标准不规定具体倍率
• 容器适配器（stack/queue/priority_queue）包装底层容器、只暴露受限接口——默认都用 deque（priority_queue 用 vector）；可根据需要指定底层容器（queue 不能用 vector——没有 pop_front）
• 选容器先分析最频繁的操作——频繁中间插入选 list、频繁两端操作选 deque、需要排序选 vector、编译期大小确定选 array、处理文本选 string

#include <vector>
#include <iostream>
int main() {
    std::vector<int> v = {3, -1, 2, -3, 5, -2};
    for (auto it = v.begin(); it != v.end(); ++it)
        if (*it < 0)
            v.erase(it);
    for (int x : v) std::cout << x << ' ';
}

#include <vector>
#include <algorithm>
#include <iostream>
int main() {
    std::vector<int> v = {3, -1, 2, -3, 5, -2};
    // remove_if 把非负数往前挪，返回「新末尾」
    auto new_end = std::remove_if(v.begin(), v.end(),
                                   [](int x) { return x < 0; });
    v.erase(new_end, v.end());  // 真正删除末尾的"垃圾"
    for (int x : v) std::cout << x << ' ';  // 3 2 5
}

#include <iostream>
#include <string>
#include <stack>
#include <queue>
 
bool is_palindrome(const std::string &s) {
    std::stack<char> stk;
    std::queue<char> q;
 
    // 压入：stack 最后入的在顶、queue 最前入的在队首
    for (char c : s) {
        stk.push(c);
        q.push(c);
    }
 
    while (!stk.empty()) {
        if (stk.top() != q.front()) return false;
        stk.pop();   // stack 从顶移除（逆序）
        q.pop();     // queue 从队首移除（正序）
    }
    return true;
}
 
int main() {
    std::string input;
    std::cout << "输入字符串: ";
    std::cin >> input;
    std::cout << (is_palindrome(input) ? "是回文" : "不是回文") << '\n';
    return 0;
}

名词解释