顺序容器：从访问模式到安全修改

一条日志进入处理系统后，可能先放进接收缓冲区，再进入待处理队列；解析失败时要删除，处理成功后要留下撤销记录。看起来都是“保存一批数据”，操作方式却不同：有的只在末尾追加，有的从两端进出，有的要求中间元素的位置长期稳定，还有的长度从程序启动前就不会改变。

C++ 的顺序容器正是为这些差异准备的。选择容器时，先描述最频繁的访问和修改，再决定存储结构。本篇把 array、vector、deque、list、forward_list 放到同一套接口中比较，并重点处理结构修改后的迭代器安全问题。

后面的示例都以 C++17 为基准。复杂度是判断方向，不是替代测量的承诺；元素大小、缓存命中、分配次数和实际数据量都会改变最终表现。

先按操作模式选择容器

容器选择不是类型名称的联想题。业务上叫“任务列表”的数据，常常只需要顺序扫描和末尾追加，vector 仍可能是最合适的类型。真正有用的问题是：数据是否定长、是否需要下标、修改发生在什么位置、是否长期保存元素位置。

一张选择表

没有明显限制时，先用 vector。它的连续存储让处理器更容易成批读取相邻元素，尾部追加的摊还成本也低。只有需求明确指向两端操作、稳定节点或固定长度时，再换到其他容器。

复杂度要连同“找到位置”一起算

假设要在 list 的第 50,000 个位置插入元素。如果手里已经有指向该位置的迭代器，插入本身是常数时间；如果只有数字 50,000，程序仍要从头走过大量节点。vector 虽然要移动后续元素，但连续内存上的批量移动可能很快。

因此，“链表中间插入是常数时间”只描述已有位置之后的结构操作，不包括定位，也不包括节点分配和缓存成本。性能敏感时，应使用真实元素类型和真实数据规模测量。

把一个处理系统拆开看

• 最近收到的事件按批次扫描、偶尔按下标查看：vector<Event>。
• 待处理任务先进先出：后面使用 queue<Task> 表达流程，而不是开放整个底层容器。
• 最近一次操作先撤销：使用 stack<Action>。
• 一天 24 个小时的计数桶：array<int, 24>。
• 行编辑器要在已有行之间插入，并保留其他行的位置：可以考虑 list<Line>。
• 日志消息需要查找和替换标记：string。

同一个程序同时使用多种容器很正常。类型应该表达局部数据的操作约束，不必追求全项目统一成一种容器。

小节测试

用统一接口理解不同容器

顺序容器的实现差异很大，但它们尽量使用相同的名字表达相同操作。掌握这套共同语言后，阅读一个新容器时，先找 value_type、begin()、end()、empty() 和 size()，就能迅速建立基本认识。

常见成员类型

泛型代码不应猜测 size() 一定返回 unsigned long，也不应假设 iterator 就是裸指针。实现可以使用类类型迭代器，只要它提供该类别承诺的操作。

构造方式表达不同意图

以 std::vector<int> 为例，常见构造形式如下：

std::vector<int> empty;
std::vector<int> five_zeros(5);
std::vector<int> four_sevens(4, 7);
std::vector<int> values{4, 7, 9};
std::vector<int> copy(values.begin(), values.end());

圆括号数量构造和花括号元素列表不能混淆：

std::vector<int> a(3);  // 三个元素：0, 0, 0
std::vector<int> b{3};  // 一个元素：3

范围构造的两个迭代器必须描述同一个有效序列，并且终点能从起点按该迭代器的前进规则到达。把两个不同容器的迭代器拼成一对，不会形成合法范围。

观察、赋值与交换

多数容器提供这些共同操作：

if (events.empty()) {
    // 没有元素
}
 
auto count = events.size();
auto first = events.begin();
auto last = events.end();
events.clear();

forward_list 是重要例外：它不提供 size()。如果每次询问长度都要遍历整条单向链，就很容易把一个看似便宜的调用写进循环。需要频繁知道数量时，可以单独维护计数，或改选别的容器。

复制容器会复制元素值，副本和被复制对象随后可以独立修改。移动容器通常转移内部资源；被移动对象仍然可以析构、赋值或重新使用，但不要依赖它保留哪些元素。

swap 交换两个同类型容器的内容，通常比逐元素复制更直接：

std::vector<int> ready{1, 2};
std::vector<int> pending{8, 9, 10};
ready.swap(pending);

调用后，ready 保存 8, 9, 10，pending 保存 1, 2。

小节测试

半开范围连接遍历与处理

一对迭代器可以描述完整容器，也可以描述其中一段。C++ 使用半开范围 [first, last)：first 指向范围内第一个元素，last 指向最后一个元素之后的位置。

为什么终点不属于范围

半开范围让三个边界情况使用同一套规则：

• 空范围满足 first == last。
• 非空时可以安全解引用 first。
• 每次 ++first，最终恰好到达 last。

典型遍历骨架是：

while (first != last) {
    use(*first);
    ++first;
}

end() 不是最后一个元素。无论容器是否为空，都不能解引用 end()；也不能先对空容器的 end() 做减一，再期待得到有效元素。

同一个函数处理不同容器

下面的函数只要求迭代器能解引用、前进和比较，因此既能打印 vector 的子范围，也能打印整个 list。

#include <iostream>
#include <list>
#include <vector>
 
template <class Iterator>
void print_range(Iterator first, Iterator last) {
    if (first == last) {
        std::cout << "<empty>\n";
        return;
    }
 
    std::cout << *first;
    ++first;
    while (first != last) {
        std::cout << ' ' << *first;
        ++first;
    }
    std::cout << '\n';
}
 
int main() {
    const std::vector<int> latency{21, 35, 18, 42};
    const std::list<int> retries{1, 2, 1};
 
    print_range(latency.cbegin() + 1, latency.cend());
    print_range(retries.cbegin(), retries.cend());
}

输出：

35 18 42
1 2 1

cbegin() 和 cend() 明确返回只读迭代器。函数仍然可以复制和移动迭代器本身，但不能通过它修改元素。

迭代器能力分层

所以 list.begin() + 3 不能通过编译。若代码只需要“向前移动 n 步”，可以使用 std::advance(it, n)；对链表它逐节点前进，对随机访问迭代器则可以直接跳转。

不同容器的迭代器不能拿来比较。即使两个容器元素相同，a.begin() == b.begin() 也没有“位置相同”的语义。迭代器的位置只在它所属的序列中有意义。

小节测试

构造、插入与原地构造元素

除固定长度的 array 外，顺序容器通常能改变元素数量。接口名称相似，但支持的端点与位置取决于存储结构。

端点与指定位置

insert(pos, value) 把新元素放在 pos 之前，并返回新元素的迭代器。插入多个元素时，返回值指向第一个新元素。使用返回值很重要，因为修改可能让旧迭代器失效。

emplace 表达“用参数构造”

如果手里已有一个完整对象，push_back(object) 很自然。如果手里是构造参数，emplace_back(args...) 可以直接在目标位置调用元素构造函数。

#include <iostream>
#include <string>
#include <utility>
#include <vector>
 
struct Event {
    Event(std::string event_id, int event_priority)
        : id(std::move(event_id)), priority(event_priority) {}
 
    std::string id;
    int priority;
};
 
int main() {
    std::vector<Event> events;
    events.reserve(3);
 
    events.emplace_back("E-100", 2);
    events.push_back(Event{"E-300", 1});
 
    const auto inserted = events.emplace(
        events.begin() + 1,
        "E-200",
        3
    );
 
    std::cout << "inserted=" << inserted->id << '\n';
    for (const Event& event : events) {
        std::cout << event.id << ':' << event.priority << '\n';
    }
}

输出：

inserted=E-200
E-100:2
E-200:3
E-300:1

这里保存的是 emplace 返回的新迭代器，没有继续使用调用前的位置。reserve(3) 只减少这段示例的重新分配次数；中间插入仍会移动插入点之后的元素。

emplace 不是无条件的性能开关。若传入的本来就是 Event 对象，容器仍要复制或移动它；在 vector 中间原地构造，也无法消除后续元素为腾位置而发生的移动。

单向链表为什么操作 after

forward_list 的节点只知道下一个节点。删除当前节点时，需要修改前一个节点保存的链接，因此它提供“前驱位置”接口：

std::forward_list<int> jobs{20, 30};
auto before_first = jobs.before_begin();
jobs.insert_after(before_first, 10);  // 10, 20, 30

before_begin() 是首元素之前的特殊位置，不能解引用。它让“在开头之前插入”也能使用 insert_after 这套统一规则。

不要默认把同一容器中的一段范围直接插回自身。迭代器可能在操作过程中失效，某些重载还明确要求输入范围不来自正在修改的容器。需要复制片段时，先放到临时容器；链表节点整体转移则应查看链表专用接口。

小节测试

访问、删除与安全循环

访问接口常常返回引用，删除接口只改变容器。把这两件事分开理解，可以避免空容器访问和“以为 pop 会返回值”两类错误。

访问前先满足前置条件

list 不提供下标，因为第 n 个节点只能从端点逐步走到。若确实要移动若干步，迭代器和 std::advance 会把这项成本写得更明显。

来自输入或配置的下标应先检查，或直接使用 at()：

if (index < events.size()) {
    events[index].mark_ready();
}

front()、back() 和适配器的 top() 都不替你处理空序列。先调用 empty()，再访问。

pop 只删除，不返回元素

pop_back()、pop_front()、stack::pop() 和 queue::pop() 的返回类型都是 void。需要取值时分两步：

if (!tasks.empty()) {
    Task task = std::move(tasks.front());
    tasks.pop();
    run(task);
}

先读取再删除，让“取得元素”和“修改容器”各自拥有清楚的异常与生命周期边界。

erase 返回下一个有效位置

删除循环最容易写错。正确形式是在删除分支接住 erase 返回值，只在保留分支递增：

#include <iostream>
#include <string>
#include <vector>
 
struct Event {
    std::string id;
    bool valid;
};
 
int main() {
    std::vector<Event> events{
        {"E-10", true},
        {"E-11", false},
        {"E-12", false},
        {"E-13", true}
    };
 
    for (auto it = events.begin(); it != events.end();) {
        if (!it->valid) {
            it = events.erase(it);
        } else {
            ++it;
        }
    }
 
    for (const Event& event : events) {
        std::cout << event.id << '\n';
    }
}

输出：

E-10
E-13

若先调用 events.erase(it)，再执行 ++it，第二步使用的已经是失效迭代器。连续两个无效元素还可能导致跳过检查或直接触发未定义行为。

范围删除同样返回删除区间之后的位置：

auto next = events.erase(first_bad, last_bad);

clear() 相当于删除全部元素。对 vector 而言，它把 size() 变为 0，但通常不会把 capacity() 也变为 0。

小节测试

把迭代器失效当成接口规则

迭代器、元素引用和元素指针都依赖容器内部位置。结构修改后，底层元素可能搬家，也可能在原位置左右移动。此时旧句柄不只是“值可能不准”，而是不能再解引用、比较或递增。

常用失效规则

deque 的端点删除还有更细的边界规则。工程代码若要跨结构修改长期保存它的迭代器，往往比重新获取位置更难审查。一个稳妥约定是：deque 结构变化后重取迭代器，只在确实需要时依赖引用稳定性。

不要执行失效句柄来观察结果

下面的旧位置在插入后不能再用：

auto old = labels.begin() + 1;
labels.insert(labels.begin(), "receive");
// old 可能已经失效；不要解引用，也不要和 end() 比较。

程序偶尔打印出“看起来正确”的值，并不能证明操作安全。未定义行为可能在另一次构建、另一组数据或完全无关的修改后才显现。

用索引或返回值重新定位

若逻辑位置可以用下标表达，在修改前保存下标，修改后重新取得迭代器：

#include <iostream>
#include <string>
#include <vector>
 
int main() {
    std::vector<std::string> labels{"read", "parse", "store"};
 
    const auto old_position = labels.cbegin() + 1;
    auto index = static_cast<std::vector<std::string>::size_type>(
        old_position - labels.cbegin()
    );
 
    labels.insert(labels.begin(), "receive");
    ++index;  // 在开头插入一个元素，目标逻辑位置向后移动一格
 
    using Difference = std::vector<std::string>::difference_type;
    const auto restored = labels.cbegin() + static_cast<Difference>(index);
    std::cout << *restored << '\n';
}

输出：

parse

这段代码从不使用插入前的迭代器。若修改操作本身返回新位置，优先接住返回值，通常比手工调整下标更简单。

reserve 能解决什么，不能解决什么

已知最多追加 10,000 个元素时，先 reserve(10000) 可以减少扩容，并在这段只做尾部追加的流程中降低全部句柄失效的机会。但是：

• reserve 自己一旦触发重新分配，会使全部元素句柄失效。
• 即使容量足够，旧 end() 在 push_back 后也失效。
• 中间 insert 或 erase 仍会让受影响位置及其后的句柄失效。

如果需求真正要求中间增删时其他元素的位置长期稳定，节点容器比“到处提前 reserve”更能直接表达约束。

小节测试

分清 size、capacity、reserve 与 resize

vector 和 string 把“已有元素”和“为未来增长准备的存储”分开管理。混淆两者会写出最常见的容量错误：只调用 reserve，随后就用下标写入并不存在的元素。

两条边界

对一个 vector，可以把内部状态想成两条边界：

已构造元素: [0, size())
已分配空间: [0, capacity())

只有第一段是可以访问的元素。[size(), capacity()) 只是备用存储，其中还没有可通过容器接口访问的对象。

capacity() 和 reserve() 主要属于 vector 与 string 的连续动态存储模型。deque 自己管理分段存储，不公开同样的容量数值。

一个只验证标准承诺的实验

不同实现采用的增长倍率可以不同，因此不要把某次运行打印出的具体 capacity() 当成固定答案。下面只检查“容量至少足够”和“元素数量如何变化”。

#include <iostream>
#include <vector>
 
int main() {
    std::vector<int> values;
 
    values.reserve(5);
    std::cout << std::boolalpha;
    std::cout << "after reserve: size=" << values.size()
              << ", can_hold_5=" << (values.capacity() >= 5U) << '\n';
 
    values.resize(3, 7);
    std::cout << "after grow: size=" << values.size() << ", values=";
    for (int value : values) {
        std::cout << value << ' ';
    }
    std::cout << '\n';
 
    values.resize(1);
    std::cout << "after shrink: size=" << values.size()
              << ", first=" << values.at(0) << '\n';
}

输出：

after reserve: size=0, can_hold_5=true
after grow: size=3, values=7 7 7 
after shrink: size=1, first=7

values.reserve(5) 后仍为空，所以此时写 values[0] = 7 是越界访问。resize(3, 7) 才创建三个值为 7 的元素。

增长策略不是接口契约

实现通常按几何方式扩大容量，使连续 push_back 的平均成本保持较低，但标准没有承诺“每次翻倍”。代码只能依赖以下事实：

• capacity() >= size()。
• reserve(n) 成功后容量至少为 n。
• 容量不足的增长可能重新分配并使句柄失效。
• resize 改的是元素数量。

shrink_to_fit() 只是请求实现尝试收缩容量，不保证一定发生。它适合经过测量后的内存调整，不适合作为正确性条件。

小节测试

用 string 与容器适配器完成处理流水线

string 既遵循字符序列接口，又增加了文本操作。容器适配器则走向另一个方向：它们故意隐藏大部分容器能力，只保留某种流程需要的操作。

string 是带文本语义的序列

常用文本修改可以直接按位置表达：

find 返回的是下标类型，不是迭代器。检查失败要与 std::string::npos 比较：

const auto pos = message.find("error");
if (pos != std::string::npos) {
    message.replace(pos, 5, "warning");
}

字符串也有 size()、capacity() 和 reserve()。结构修改可能让先前取得的字符指针、引用和迭代器失效；修改后应重新获取。c_str() 和 data() 得到的指针尤其不能跨任意字符串修改长期保存。

适配器用受限接口表达流程

适配器不提供普通迭代器，也不允许在中间随意插入。这个限制能阻止调用方破坏队列或栈的顺序语义。pop() 仍然只删除；应先用 front() 或 top() 读取。

一个可运行的任务流水线

下面的程序用 string 清理任务文本，用 queue 保证接收顺序，用 stack 保存最近完成的任务。

#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
 
std::string normalize(std::string task) {
    const auto temporary = task.find("[tmp] ");
    if (temporary != std::string::npos) {
        task.erase(temporary, 6);
    }
 
    const auto first_text = task.find_first_not_of(' ');
    if (first_text == std::string::npos) {
        return {};
    }
    task.erase(0, first_text);
 
    const auto urgent = task.find("P1:");
    if (urgent != std::string::npos) {
        task.replace(urgent, 3, "urgent");
    }
    return task;
}
 
int main() {
    std::queue<std::string> pending;
    std::stack<std::string> completed;
 
    pending.push("  [tmp] parse logs");
    pending.push("P1: restart worker");
 
    while (!pending.empty()) {
        std::string task = normalize(pending.front());
        pending.pop();
 
        if (!task.empty()) {
            std::cout << "run: " << task << '\n';
            completed.push(std::move(task));
        }
    }
 
    if (!completed.empty()) {
        std::cout << "undo: " << completed.top() << '\n';
    }
}

输出：

run: parse logs
run: urgent restart worker
undo: urgent restart worker

queue 让先接收的任务先运行，stack 让最后完成的任务先撤销。若改成“紧急任务优先”，可以为任务定义比较规则并使用 priority_queue，而不是每次手工扫描普通序列。

实践时逐项检查

1. 先写出最频繁的访问和修改位置，再选容器。
2. 用 [begin, end) 描述遍历边界，不解引用尾后位置。
3. 结构修改后明确哪些迭代器、引用和指针仍然有效。
4. 删除循环接住 erase 返回值。
5. 分开 size 与 capacity，不把备用存储当元素。
6. 需要先进先出、后进先出或优先级语义时，用适配器收窄接口。

这套检查能覆盖顺序容器中最常见的设计错误。处理逻辑需要排序、查找、计数或变换时，再把有效范围交给通用算法，而不用重写容器内部操作。

小节测试