顺序容器：vector、deque、list、array
探索 STL 中的顺序容器──vector、deque、list、forward_list 和 array。学习它们的性能权衡、内存布局和迭代器失效规则。
什么是顺序容器？
顺序容器以严格的线性顺序存储元素。STL 提供了五种顺序容器，每种都针对不同的访问和修改模式进行了优化：
- std::vector ── 动态数组，连续内存
- std::deque ── 双端队列，两端快速插入
- std::list ── 双向链表
- std::forward_list ── 单向链表
- std::array ── 固定大小数组，栈上分配
选择正确的容器是你在 C++ 中做出的最具影响力的性能决策之一。关键因素是访问模式、插入/删除模式和缓存局部性。
std::vector ── 默认之选
std::vector 是最常用的容器。它将元素存储在单个连续的内存块中，具有出色的缓存性能和 O(1) 随机访问。使用 push_back 追加元素的摊还复杂度为 O(1)，因为 vector 在满时会将容量翻倍。
#include <iostream>
#include <vector>
int main() {
std::vector<int> nums; // empty vector
nums.reserve(100); // pre-allocate for 100 elements (no reallocation)
for (int i = 0; i < 10; ++i) {
nums.push_back(i * i); // amortized O(1)
}
// Size vs capacity
std::cout << "Size: " << nums.size() << '\n'; // 10
std::cout << "Capacity: " << nums.capacity() << '\n'; // >= 100
// Random access — O(1)
std::cout << "Element 3: " << nums[3] << '\n'; // 9
std::cout << "Element 3: " << nums.at(3) << '\n'; // 9 (bounds-checked)
// Erase-remove idiom (pre-C++20)
nums.erase(std::remove_if(nums.begin(), nums.end(),
[](int x) { return x > 50; }),
nums.end());
// C++20: std::erase_if (cleaner)
std::erase_if(nums, [](int x) { return x > 30; });
// Range-based for loop
for (int n : nums) {
std::cout << n << ' ';
}
std::cout << '\n';
}deque、list 和 forward_list
std::deque 在头部和尾部都提供 O(1) 的插入和删除，但使用分段内存布局（固定大小块的数组）而非单个连续分配。std::list 是双向链表，给定迭代器即可在任意位置进行 O(1) 插入/删除，但缓存局部性较差。std::forward_list 是单向链表，每个节点占用更少的内存，但只支持正向遍历。
#include <deque>
#include <list>
#include <forward_list>
#include <iostream>
int main() {
// deque — O(1) push_front and push_back
std::deque<int> dq;
dq.push_front(1); // O(1) — vector cannot do this efficiently
dq.push_back(2); // O(1)
dq.push_front(0); // O(1)
// dq: {0, 1, 2}
// list — O(1) insert/erase at any position with iterator
std::list<std::string> names = {"Alice", "Charlie", "Eve"};
auto it = std::next(names.begin()); // points to "Charlie"
names.insert(it, "Bob"); // O(1) insert before "Charlie"
names.erase(it); // O(1) erase "Charlie"
// names: {"Alice", "Bob", "Eve"}
// list has splice — O(1) move of entire sublists
std::list<std::string> more = {"Frank", "Grace"};
names.splice(names.end(), more); // moves all of 'more' into 'names'
// names: {"Alice", "Bob", "Eve", "Frank", "Grace"}
// more is now empty
// forward_list — singly linked, no size(), push_front only
std::forward_list<int> fl = {3, 1, 4, 1, 5};
fl.push_front(0);
fl.sort(); // member sort — O(n log n), stable
fl.unique(); // remove consecutive duplicates
// fl: {0, 1, 3, 4, 5}
for (int v : fl) std::cout << v << ' ';
std::cout << '\n';
}std::array ── 固定大小，零开销
std::array 将 C 风格数组包装在一个合适的类中，提供 .size()、.at()、迭代器以及与所有 STL 算法的兼容性──与原始 T[N] 相比零开销。
#include <array>
#include <algorithm>
#include <iostream>
int main() {
std::array<int, 5> arr = {5, 2, 8, 1, 9};
std::sort(arr.begin(), arr.end()); // works with STL algorithms
std::cout << "Size: " << arr.size() << '\n'; // constexpr — known at compile time
std::cout << "Front: " << arr.front() << '\n'; // 1
std::cout << "Back: " << arr.back() << '\n'; // 9
// Bounds-checked access
try {
arr.at(10); // throws std::out_of_range
} catch (const std::out_of_range& e) {
std::cout << "Out of range: " << e.what() << '\n';
}
// Compile-time size via std::tuple_size
constexpr std::size_t n = std::tuple_size_v<decltype(arr)>; // 5
static_assert(n == 5);
}选择正确的顺序容器
使用以下决策指南：
使用 std::vector（默认选择）当你需要随机访问、缓存友好的迭代或在尾部进行 push/pop 操作时。绝大多数代码都应该使用 vector。
使用 std::deque 当你需要在头尾两端频繁插入/删除时（例如滑动窗口、BFS 队列）。
使用 std::list 当你需要在给定迭代器的位置进行 O(1) 插入/删除，或者需要使用 splice() 在链表之间移动子序列而不复制时。
使用 std::forward_list 当每个节点的内存很重要且只需正向遍历时。
使用 std::array 当大小在编译时已知且永远不会改变时。
性能提示： 由于 CPU 缓存效应，在现代硬件上 std::vector 在中间插入方面通常优于 std::list，甚至对于出人意料的大量元素（数千个元素）也是如此。在选择链表之前一定要先进行性能测量。
每种容器对于迭代器、指针和引用何时失效有不同的规则：
vector ── 触发重新分配的插入会使所有迭代器失效。不触发重新分配的插入会使插入点及之后的迭代器失效。删除操作会使删除点及之后的迭代器失效。
deque ── 在头部或尾部的插入会使所有迭代器失效，但不会使指向现有元素的引用/指针失效。在中间的插入会使一切失效。头部/尾部的删除只会使被删除元素的迭代器失效。
list / forward_list ── 插入和删除永远不会使指向其他元素的迭代器、引用或指针失效。只有被删除元素的迭代器会失效。
array ── 迭代器永远不会失效（数组不能改变大小）。
一个常见的 bug 是在基于范围的 for 循环内修改 vector。如果 push_back 触发重新分配，循环中隐含的迭代器就会变成悬空指针。
如果你知道（或可以估算）一个 vector 将容纳多少元素，请在填充之前调用 reserve()。这会预分配内存并避免昂贵的重新分配：
- reserve(n) 改变容量但不改变大小──不会添加任何元素。
- resize(n) 改变大小──它实际上会默认构造元素。
- shrink_to_fit() 是一个非约束性请求，用于将容量缩减到与大小匹配。
对于构建 vector 的热循环，单次 reserve() 调用可以大幅减少分配开销。使用大数据集进行测量以观察差异。
std::vector是默认选择──连续内存意味着缓存友好的迭代和 O(1) 随机访问- 当大致大小已知时，使用
reserve()预分配 vector 内存 std::deque在头尾两端都提供 O(1) push/pop，但不是连续的std::list使用迭代器提供 O(1) 插入/删除，且永远不会使其他迭代器失效std::array是 C 数组的零开销包装器，完全兼容 STL- 迭代器失效规则因容器而异──了解这些规则以避免悬空迭代器 bug
测验 — 检验你的知识
(15 经验值)1. 哪种顺序容器提供 O(1) 摊还的 `push_back` 和连续内存布局？
2. 当 `push_back` 触发重新分配时，所有 vector 迭代器会怎样？
3. vector 上 `reserve(n)` 和 `resize(n)` 有什么区别？