返回：C++ 泛型编程目录 · 安全开发总目录

这一章整理三类顺序容器：vector、deque、list。它们接口看起来相似，但内存布局完全不同。安全复盘重点是容量、迭代器失效、边界访问和插入删除成本。

3.4 vector 特性解析

vector 是连续动态数组，支持随机访问，尾部追加效率高。

特性 说明
连续内存 适合和 C API、二进制缓冲区交互
动态扩容 容量不够时重新分配
随机访问 v[i] 快
中间插入删除 需要移动元素

3.5 vector 对象初始化

1
2
3
std::vector<int> a;
std::vector<int> b(5, 1);
std::vector<int> c = {1, 2, 3};

3.6 vector 内存布局

vector 通常维护三个关键信息：起始位置、当前结束位置、容量结束位置。扩容后旧指针和迭代器可能全部失效。

3.7 vector 大小函数

函数 作用
size() 当前元素个数
capacity() 当前已分配容量
empty() 是否为空
reserve() 提前预留容量
resize() 改变元素个数

3.8 vector 元素追加

1
2
3
4
std::vector<int> nums;
nums.reserve(10);
nums.push_back(1);
nums.emplace_back(2);

提前 reserve 可以减少扩容次数，也能降低迭代器失效频率。

3.9 vector 数据插入

中间插入会移动后续元素。

1
nums.insert(nums.begin() + 1, 100);

插入前要确认位置合法。

4.0 vector 元素删除

1
nums.erase(nums.begin());

删除后被删除位置及其后面的迭代器通常失效。

4.1 vector 修改数据

[] 不检查边界，at() 会检查边界并抛异常。

1
2
3
if (index < nums.size()) {
    nums[index] = 10;
}

4.2 vector 标准查询

1
2
3
4
auto it = std::find(nums.begin(), nums.end(), 10);
if (it != nums.end()) {
    std::cout << "found\n";
}

算法返回迭代器，必须和 end() 比较。

4.3 deque 对象初始化

deque 是双端队列，适合头尾插入删除。

1
2
3
std::deque<int> q = {1, 2, 3};
q.push_front(0);
q.push_back(4);

4.4 deque 内存布局

deque 不是一整块连续内存，而是分段管理。它支持随机访问，但不适合把内部地址长期传给 C API。

4.5 deque 动态增加

头尾插入比 vector 更自然，但中间插入仍然有成本。

4.6 deque 释放元素

pop_front / pop_back 不返回被删除值，删除前要自己保存。

4.7 deque 修改数据

和 vector 类似，优先检查下标范围。

4.8 list 对象构造

list 是双向链表，元素不连续。

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

4.9 list 内存布局

每个节点保存数据和前后指针。插入删除稳定，但不支持下标随机访问。

5.0 list 结构图解

可以把 list 画成：

1
[prev|data|next] <-> [prev|data|next] <-> [prev|data|next]

5.1 list 构造插入

1
2
values.push_back(4);
values.push_front(0);

5.2 list 元素删除

1
values.remove(2);

remove 会删除所有等于目标值的元素。

5.3 list 查找修改

1
2
3
4
auto it = std::find(values.begin(), values.end(), 3);
if (it != values.end()) {
    *it = 30;
}

容器选择表

容器 适合 注意
vector 随机访问、连续缓冲区、尾部追加 扩容导致迭代器失效
deque 头尾频繁插入删除 内存不完全连续
list 中间频繁插入删除 不能随机访问，缓存局部性差

本章最小复盘代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <algorithm>
#include <iostream>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3};
    nums.reserve(8);
    nums.push_back(4);

    auto it = std::find(nums.begin(), nums.end(), 2);
    if (it != nums.end()) {
        *it = 20;
    }

    for (int n : nums) {
        std::cout << n << " ";
    }
    return 0;
}

学习检查清单

检查项 状态
能说明 vector 连续内存和扩容机制 待复盘
能解释迭代器失效是什么 待复盘
能区分 vector、deque、list 的适用场景 待复盘
能使用 find 查询并检查 end() 待复盘
能安全删除容器元素 待复盘