数据结构 01：从存储布局到结构选择

同样一批数据，为什么数组按下标取值很快，链表插入之前却常常需要先找位置？为什么堆能快速取出最大值，却不能像有序数组一样做二分查找？这篇沿着“数据放在哪里 → 一次操作改变什么 → 哪个约束始终成立”的顺序，把结构和操作连起来。

专题目录 · 下一篇：链表与指针操作 · STL 数据处理

1. 先提出操作，再选择结构

设想正在处理机器人记录：传感器样本要顺序保存，等待处理的任务要排队，紧急任务要优先执行，设备名称要映射到状态，设备之间又有连接关系。这些数据都能保存到 vector，但查询与修改的代价会不同。

这里的 n 表示元素数，V、E 表示顶点数与边数。复杂度描述规模增长时的操作量，不是一次操作的耗时。O(1) 也要执行哈希、访问内存或分配节点；实际速度应在真实数据上测量。

2. 连续存储：数组怎样换来随机访问

假设每个整数占 4 字节，数组首地址为 1000，第 i 个元素的地址就是 1000 + 4 × i。只计算偏移，不需要从头走过前面的元素。

下标       0       1       2
地址     1000    1004    1008
数据     [10]    [20]    [30]

std::array<int, 3> 把这 3 个元素放在对象内部，元素连续。它不保证对象一定在栈上：局部对象、静态对象、另一个对象的成员或动态创建的对象，可以有不同的存储期。标准草案：array

std::array<int, 3> samples{10, 20, 30};
samples[1] = 15;           // 已知下标有效时使用；[] 不检查边界
int value = samples.at(2); // 下标越界时抛出 std::out_of_range

vector 的 size 和 capacity 各表示什么

size 是已经存在的元素数，capacity 是当前分配的空间能容纳多少元素。reserve(8) 只是预留空间，不能让空数组立刻合法地访问 v[0]；resize(8) 才会把元素数改为 8。

先看在 [10,20,30] 的下标 1 插入 15：必须给新元素腾出一格。图用整数赋值展示移动关系；真正的泛型 vector 还要处理对象的构造、移动和析构。

点击下一步，观察被搬移的后缀。这里始终维持的约束是：插入位置之前的元素保持顺序，已经搬好的后缀不会被尚未移动的数据覆盖。结束后得到 [10,15,20,30]。

std::vector<int> values{10, 20, 30};
values.reserve(8);
values.insert(values.begin() + 1, 15);
// 结果：10, 15, 20, 30；size 为 4，capacity 至少为 8

容量不足和中间搬移是两件事。 即使提前 reserve，中间插入仍要移动后缀；如果还发生重新分配，则全部元素要进入新的存储区域。重新分配后，旧指针、引用和迭代器全部失效；未重新分配的插入也会使插入点及其后的迭代器、指针和引用失效，包含旧的 end()。标准草案：vector 修改规则

尾插多数时候只增加一个元素，少数时候搬迁整个数组，所以一系列尾插平均分摊为 O(1)，但单次可能 O(n)。标准不规定每次容量必须恰好翻倍。尾删为 O(1)，通常保留容量；shrink_to_fit() 是非强制的缩容请求。

即使先 reserve(100)，在已有 50 个元素的最前面插入仍需移动后缀。预留容量减少重新分配，不能消除元素移动。

3. 节点存储：链表的 O(1) 有什么前提

head → [10 | next] → [20 | next] → [30 | null]
                插入 15：先连 15→20，再连 10→15

节点不要求连续。已有前驱节点时，单链表插入只改变少量链接；但要从头寻找“第 100 个节点”，仍要顺着链接走。双链表还保存前驱链接，能向两个方向移动。

std::list<int> values{10, 20, 30};
auto position = std::next(values.begin()); // 查找位置有成本
auto inserted = values.insert(position, 15); // 已知位置，插入为 O(1)
values.erase(inserted);                      // 只使被删除节点失效

std::forward_list 是单链表，对应 insert_after、erase_after；std::list 是双链表。二者都没有下标访问。链表中的稳定节点身份适合某些移接操作，但“经常增删就用链表”仍不够：如果每次都要先搜索，搜索可能占主要成本。

list::splice 可以转移节点而不复制元素，但不同重载复杂度不同：转移整张表或单个节点是常数时间；跨容器转移一个范围通常还需统计范围长度，标准规定线性复杂度；同一容器内合法的范围移接为常数时间。来源与目标的分配器还必须相等。标准草案：list 操作

具体插入、删除、反转的逐步指针图见数据结构 02：链表。图中直接标出了修改前后的链接关系。

4. 栈、队列、deque：限制入口让意图明确

同样加入 10,20,30，不同规则决定下一个处理谁：

栈：   入 10 → 入 20 → 入 30 → 取出 30       后进先出
队列： 入 10 → 入 20 → 入 30 → 取出 10       先进先出
deque：既可从左侧进出，也可从右侧进出

stack 与 queue 是容器适配器，默认使用 deque；它们强调允许哪些操作，不暴露用于任意遍历的迭代器。top() / front() 观察元素，pop() 删除元素但不返回值；调用前要先检查非空。

std::queue<int> jobs;
jobs.push(10);
jobs.push(20);
if (!jobs.empty()) {
    int job = jobs.front();
    jobs.pop();
    // 处理 job；下一个轮到 20
}

deque 支持 O(1) 随机访问和两端单元素增删，但不保证元素处于同一连续内存区。因此不能把它当作 vector::data() 那样的连续数组传给 C 接口。中间插入仍是线性操作。标准草案：deque 修改

用操作理解场景： 括号匹配需要最近一个未配对左括号，所以用栈；BFS 必须先处理早发现的节点，所以用队列。结构选择来自访问规则。

5. 搜索树、堆与哈希表解决三个不同的问题

有序树：查询值和区间

二叉搜索树要求左子树键小于当前键、右子树键大于当前键。未经平衡的树可能退化成链，所以不能一概声称树查找是 O(log n)。标准库 map、set 提供相应的对数复杂度保证，常见实现是平衡搜索树，标准未指定必须使用红黑树。

map 保存键值对；set 只保存键；multimap、multiset 允许等价键重复。键是否等价由比较器判断：!comp(a,b) && !comp(b,a)，不一定由 operator== 决定。

std::map<int, std::string> devices{
    {30, "imu"}, {10, "camera"}, {20, "lidar"}
};
// lower_bound 找第一个键 >= 15 的位置，随后按键向前遍历
for (auto it = devices.lower_bound(15);
     it != devices.end() && it->first < 30; ++it) {
    // 只访问键 20；区间 [15,30)
}

定位起点 O(log n)，输出 k 项再花 O(k)。不要把整个范围查询只记成 O(log n)。标准草案：有序关联容器

堆：只维持最值所需的秩序

最小堆要求父节点不大于孩子，不要求左右子树互相有序。用数组保存完全二叉树时，节点 i 的孩子下标是 2*i+1 与 2*i+2；只有 i>0 时才有父节点 (i-1)/2。

例如最小堆数组 [2,5,3,9,7] 并没有完全排序，但根已经是最小值。加入 1 时先放末尾，再与父节点交换，直到父子约束恢复；弹出根时用末尾补位，再向下调整。

std::priority_queue<int, std::vector<int>, std::greater<int>> ready;
for (int priority : {5, 2, 9}) ready.push(priority);
while (!ready.empty()) {
    int next = ready.top(); // 依次为 2、5、9
    ready.pop();
}

priority_queue 默认是最大堆；上面用 greater<int> 得到最小堆。查看顶端 O(1)，调整堆所需比较次数 O(log n)。默认底层 vector 插入偶尔还会重新分配，因此 push 的总成本有摊还因素。维护大小为 k 的最小堆，可以在扫描 n 项时保留最大的 k 项，典型代价 O(n log k)。标准草案：priority_queue

哈希表：完整键定位，不维护大小关系

哈希把键映射到桶，桶冲突后仍必须比较真正的键。平均查找为 O(1)，最坏可能 O(n)；若键是长字符串，计算哈希和比较字符串本身也有成本。

std::unordered_map<std::string, int> counts;
counts.reserve(100);
++counts["imu"]; // 这里确实希望不存在的计数先插入 0
auto found = counts.find("camera"); // 单纯查询不会插入

不能依赖哈希表的遍历顺序。rehash 会使迭代器失效，但不会使仍存活元素的指针和引用失效；删除元素才会使指向该元素的引用失效。reserve 也可能触发 rehash。标准草案：无序关联容器

自定义键的相等判断与哈希必须一致：相等的两个键必须产生相同哈希值；哈希值相同则不代表键相等。C++17 写法示例：

struct Point {
    int x, y;
    bool operator==(const Point& other) const noexcept {
        return x == other.x && y == other.y;
    }
};
struct PointHash {
    std::size_t operator()(const Point& p) const noexcept {
        return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 1);
    }
};
// 简单演示，不代表适合所有数据分布的高质量哈希组合
std::unordered_map<Point, std::string, PointHash> labels;

6. Trie：把“公共前缀”变成公共路径

root
 ├─ c ─ a ─ t*       cat
 │       └─ r*       car
 └─ d ─ o ─ g*       dog
* 标记一个完整单词结束

插入 cat 后再插入 car，只需在 ca 后新建 r 节点。查询 ca 时路径存在，但终点未被标为单词，因此 starts_with("ca") 为真，contains("ca") 为假。

固定 26 字母孩子数组让每一步索引为 O(1)，长度为 L 的插入和查询为 O(L)。代价是每个节点都预留 26 个孩子位置。字符集大且分支稀疏时，可改用映射存孩子，复杂度和空间也会随之变化。

static void validate_word(std::string_view word) {
    for (char c : word) {
        if (c < 'a' || c > 'z') {
            throw std::invalid_argument("expected lowercase a-z");
        }
    }
}
// 必须先验证整串，再执行 child[c - 'a']。
// 否则大写、标点及 UTF-8 字节会造成错误索引。

完整 Trie 实现和边界用例 使用 unique_ptr 表达子节点所有权，接受空字符串作为可插入的单词，非法字符抛出异常。这个教学版本针对小规模单词，不把 Unicode 分词、超长输入的资源限制或产品级搜索功能混在一起。

7. 图与 BFS：让队列对应“距离一层层增长”

图的顶点表示对象，边表示关系。先画一个有向无权图：A 指向 B、C；B 指向 D；C 指向 D、E。代码用 0..4 对应 A..E。

using Graph = std::vector<std::vector<int>>;
Graph graph{{1, 2}, {3}, {3, 4}, {}, {}};
//           A       B      C     D   E

从 A 出发的过程如下。队列左侧是下一次要出队的元素；发现节点时就标记，而不是等到出队时才标记。

BFS 的关键约束是：队列按距离非递减的顺序处理顶点。若每条边代价相同，第一次发现一个点时就得到最短步数。若边有不同权重，这个结论不再成立，需要根据权重条件选择 Dijkstra 等算法。

std::vector<int> bfs_distance(const Graph& graph, int start) {
    // 完整源码先检查 start、图规模以及全部边端点是否合法。
    validate_graph(graph, start);
    std::vector<int> distance(graph.size(), -1);
    std::queue<int> pending;
    distance[start] = 0;
    pending.push(start);
    while (!pending.empty()) {
        int u = pending.front();
        pending.pop();
        for (int v : graph[u]) {
            if (distance[v] == -1) {
                distance[v] = distance[u] + 1;
                pending.push(v);
            }
        }
    }
    return distance;
}

完整源码将空图和非法起点视为无效调用并抛出异常；即使某个坏的边端点位于不可达分量，也会先验证出来，避免因输入形状不同而漏检。未访问顶点的距离保持 -1。

这里是未额外建立索引的普通邻接表。无向边通常存两次，不改变渐进复杂度。BFS/DFS 遍历邻接表的代价为 O(V+E)；DFS 用递归或显式栈，可用于连通分量、环检测等，但普通 DFS 不保证无权最短路。

8. 并查集：只关心哪些点属于同一集合

假设依次连接 (0,1)、(2,3)、(1,2)：

开始：   {0} {1} {2} {3} {4}
连0—1： {0,1}   {2} {3} {4}
连2—3： {0,1}   {2,3}   {4}
连1—2： {0,1,2,3}       {4}

并查集保存“父节点”，沿父节点最终找到代表元。集合代表元是谁不重要，同一集合中的元素是否找到同一个根才重要。合并时把小集合的根挂到大集合的根上；查询时把沿途节点尽量指向根，称为路径压缩。

DisjointSet groups(5); // 完整定义见 structures.cpp
groups.unite(0, 1);
groups.unite(2, 3);
groups.unite(1, 2);
bool same = groups.connected(0, 3); // true
bool changed = groups.unite(0, 3);  // false：本来就已连通

初始化为 O(n)。按大小合并与路径压缩一起使用时，后续操作的摊还复杂度为 O(α(n))；α 是增长极慢的反阿克曼函数，不能据此宣称每一次调用严格为 O(1)。它适合增量连通性与 Kruskal；不保存具体连通路径，也不能直接支持任意删除边。

示例构造函数先拒绝负数规模，再分配数组；零规模允许构造，但没有合法元素下标。find、unite、connected 接受的编号范围是 [0,n)，完整代码检查这个前提，不把负数隐式转成超大无符号下标。

9. 复杂度要写清楚是哪一个操作

表中的 unordered_* 单元素删除指持有一个元素迭代器的情形；允许重复键的 erase(key) 还要计入删掉多少项。有序容器按迭代器删除与按键删除也不是同一复杂度，详细要求见标准草案对应表。

10. 把图变成可运行的实验

下载 structures.cpp，其中包括安全的 Trie、BFS、并查集，以及数组、堆和自定义哈希键示例。仓库中的统一实验命令见专题学习路线。所有示例使用 C++17。

接下来到 STL 数据流水线：将这里的结构选择，落实成查找、过滤、计数、排序和去重代码。