四、STL 容器与数据结构（进阶）（一）-平芜编程栈

四、STL 容器与数据结构（）

一句话总览：STL 容器的选择本质上是在“连续内存、节点结构、有序性、哈希查找、插入删除效率、缓存友好性”之间做权衡；vector是默认首选，map/set适合有序和范围查询，unordered_map适合平均 O(1) 的精确查找，list/deque只在特定两端或任意位置插入删除场景下使用。

0. 知识点之间的联系

STL 容器 ├─ 序列式容器 │ ├─ array / vector：连续数组，随机访问快 │ ├─ deque：分段连续，双端操作快 │ └─ list / forward_list：链表，按已知位置插入删除快 │ ├─ 容器适配器 │ ├─ stack：后进先出 │ ├─ queue：先进先出 │ └─ priority_queue：堆，优先级最高者先出 │ ├─ 有序关联容器 │ ├─ set / map │ ├─ multiset / multimap │ └─ 底层通常是红黑树 │ ├─ 无序关联容器 │ ├─ unordered_set / unordered_map │ ├─ unordered_multiset / unordered_multimap │ └─ 底层通常是哈希表 │ └─ 横切知识点 ├─ iterator：统一访问方式 ├─ 算法：sort/find/copy/lower_bound ├─ 仿函数 / lambda：比较器、哈希函数 └─ mutable：const 对象逻辑可修改性

选择顺序可以简单记为：

默认用 vector 需要双端进出 → deque 需要有序遍历 / 范围查询 → map/set 需要按键平均 O(1) 查找 → unordered_map 已有迭代器且频繁任意位置插入删除 → list 需要 LIFO/FIFO/优先级 → stack/queue/priority_queue

1. C/C++ 中常用容器功能汇总

核心：C 语言主要靠原生数组、malloc/realloc动态数组、手动链表、环形缓冲区等实现容器；C++ STL 则提供自动内存管理、迭代器、泛型算法和统一接口。

C 语言没有真正意义上的标准容器库。数组大小固定，动态数组需要程序员手动管理内存；链表需要自己定义节点和指针；哈希表、平衡树也通常要手写或引入第三方库。C++ STL 将常见数据结构封装成模板类，并配合算法库实现排序、查找、复制、遍历等通用操作。

#include <array> #include <deque> #include <iostream> #include <list> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #include <vector> int main() { // 1. 固定大小数组 std::array<int, 3> arr = {1, 2, 3}; // 2. 动态数组 std::vector<int> vec; vec.reserve(100); vec.push_back(1); vec.push_back(2); // 3. 双端队列 std::deque<int> dq; dq.push_front(1); dq.push_back(2); // 4. 双向链表 std::list<int> lst = {1, 2, 3}; lst.push_front(0); // 5. 有序集合，去重且按 key 排序 std::set<int> s = {3, 1, 2}; // 6. 有序字典 std::map<std::string, int> mp; mp["alice"] = 90; mp["bob"] = 85; // 7. 哈希字典 std::unordered_map<std::string, int> ump; ump["model_a"] = 1; ump["model_b"] = 2; // 8. 栈 std::stack<int> st; st.push(1); // 9. 队列 std::queue<int> q; q.push(1); // 10. 优先队列，默认大根堆 std::priority_queue<int> pq; pq.push(3); pq.push(9); pq.push(5); std::cout << pq.top(); // 9 }

常见容器对比如下：

容器	逻辑结构	随机访问	头部插入	尾部插入	中间插入	元素顺序
`array`	固定数组	O(1)	不支持	不支持	不支持	插入顺序
`vector`	动态数组	O(1)	O(n)	均摊 O(1)	O(n)	插入顺序
`deque`	分段数组	O(1)	O(1)	O(1)	O(n)	插入顺序
`list`	双向链表	O(n)	O(1)	O(1)	已知位置 O(1)	插入顺序
`set/map`	红黑树	不支持	O(log n)	O(log n)	O(log n)	key 有序
`unordered_*`	哈希表	不支持	平均 O(1)	平均 O(1)	平均 O(1)	无序
`stack`	适配器	不支持	只访问栈顶	O(1)	不支持	LIFO
`queue`	适配器	不支持	O(1)	O(1)	不支持	FIFO

STL 容器通常通过迭代器统一访问：

std::vector<int> v = {3, 1, 2}; for (auto it = v.begin(); it != v.end(); ++it) { std::cout << *it << ' '; } for (const auto& x : v) { std::cout << x << ' '; }

使用容器时不能只背接口，还要理解底层结构。连续内存容器缓存友好，适合遍历和随机访问；节点容器插入删除稳定，但缓存局部性差；有序容器支持范围查询但单次查找为 O(log n)；哈希容器平均查找快但最坏情况会退化，并且不保证顺序。实际工程中，绝大多数业务容器首选vector，因为它最简单、最快、最容易被编译器优化。

2. 介绍一下 vector 的优缺点

核心：vector是动态数组，底层是一块连续内存。它随机访问快、尾部追加快、遍历缓存友好，是最常用的 STL 容器；缺点是头部和中间插入删除慢，扩容时可能发生大量元素移动并使迭代器失效。

vector内部维护三个核心概念：

起始位置 size 结束位置 capacity 容量结束位置 ↓ ↓ ↓ [1][2][3][4][5][ ][ ][ ][ ][ ] └──── 已使用 size=5 ────┘ └──────────── capacity=10 ────────┘

size：当前元素个数。
capacity：当前已分配空间最多能放多少元素。
当size == capacity再push_back时，会重新分配更大空间，把旧元素移动或拷贝过去，再释放旧空间。

#include <iostream> #include <vector> int main() { std::vector<int> v; std::cout << v.size() << ' ' << v.capacity() << '\n'; v.reserve(1000); // 提前分配容量，避免多次扩容 for (int i = 0; i < 1000; ++i) { v.emplace_back(i); } std::cout << v[500] << '\n'; // O(1) std::cout << v.at(500) << '\n'; // 带越界检查 v.pop_back(); // 删除尾部 O(1) v.insert(v.begin(), 100); // 头部插入 O(n) v.erase(v.begin()); // 头部删除 O(n) }

优点

第一，随机访问 O(1)。因为内存连续，元素地址可以通过公式计算：

第 i 个元素地址 = 起始地址 + i × sizeof(T)

第二，尾部插入效率高。容量足够时push_back/emplace_back是 O(1)；容量不足时虽然要扩容，但多次插入的均摊成本仍是 O(1)。

第三，缓存友好。连续内存使 CPU cache line 能一次加载多个相邻元素，顺序遍历通常明显快于链表。

第四，与 C 风格数组兼容好。可以通过data()获取连续首地址，适合网络、图形、算法库等接口。

第五，内存自动管理，不需要手写malloc/free，异常安全和 RAII 更可靠。

缺点

第一，中间和头部插入删除慢。在位置i插入需要把后面的元素整体后移：

插入前：[A][B][C][D] 在 B 前插入 X： [A][ ][B][C][D] ↑ 后面的元素全部后移 结果： [A][X][B][C][D]

第二，扩容成本高。扩容时可能拷贝或移动所有旧元素，扩容因子由实现决定，常见为 2 倍或 1.5 倍。

第三，迭代器失效问题需要重视。扩容后，旧内存被释放，所有迭代器、引用、指针通常都会失效；即使不扩容，插入位置之后的迭代器也可能失效。

std::vector<int> v = {1, 2, 3}; auto it = v.begin() + 1; v.push_back(4); // 若发生扩容，it 可能已经失效，不能继续使用

第四，容量可能大于实际元素数，造成一定空间浪费，可用shrink_to_fit()请求归还空间，但是否真的归还由实现决定。

第五，vector<bool>是特化版本，按位存储，不完全满足普通容器语义，对单个“元素”取引用时要特别小心。

工程建议是：如果元素数量大致已知，优先reserve；优先尾部增删；不要在循环中频繁头部插入；需要频繁中间删除时，考虑先标记后批量删除，或换用更合适的数据结构。

3. 介绍一下 list 的优缺点

核心：std::list是双向链表，节点在堆上独立分配。它最大的优点是在已知迭代器位置时，插入和删除都是 O(1)，且不会让其他元素的迭代器和引用失效；最大缺点是不支持随机访问、节点内存开销大、缓存局部性差。

list的逻辑结构如下：

head ↔ [prev|A|next] ↔ [prev|B|next] ↔ [prev|C|next] ↔ tail

每个节点除了保存元素，还要保存前驱和后继指针。

#include <iostream> #include <list> int main() { std::list<int> lst = {1, 2, 3, 4}; auto it = lst.begin(); std::advance(it, 2); // 移动到第三个元素，线性时间 lst.insert(it, 99); // 已知 it，插入 O(1) lst.erase(it); // 删除 O(1) lst.push_front(0); lst.push_back(5); for (int x : lst) { std::cout << x << ' '; } }

list还提供了一些链表特有操作：

#include <list> int main() { std::list<int> a = {1, 3, 5}; std::list<int> b = {2, 4, 6}; a.merge(b); // 合并两个有序链表 a.sort(); // 链表排序 a.unique(); // 删除连续重复元素 a.splice(a.end(), std::list<int>{7, 8}); // 拼接另一个链表 }

优点

第一，已知位置插入删除 O(1)。不需要像vector那样移动大量元素，只需要修改相邻节点指针：

删除 B： [A] ↔ [B] ↔ [C] 修改 A.next 和 C.prev： [A] ↔──────── [C]

第二，迭代器和引用稳定性好。插入任何元素不会使已有迭代器失效；删除某个节点，也只会使指向该节点的迭代器失效，其他节点不受影响。

第三，头尾插入删除都稳定 O(1)，不会像vector那样扩容搬移。

第四，支持splice，可以把一个链表的一段直接摘下来挂到另一个链表，不必逐个复制元素。

缺点

第一，不支持随机访问。lst[i]不存在，访问第i个元素必须从头或从尾沿指针走，平均 O(n)。

第二，额外内存开销大。每个节点都要分配一次内存，并保存前驱、后继指针。存储大量小对象时，内存可能远大于vector。

第三，缓存不友好。节点地址不连续，遍历时容易发生 cache miss，因此即使list在理论上插入删除是 O(1)，实际性能也可能因为内存分配和缓存问题输给vector。

第四，查找仍然是 O(n)，因为它没有像map那样维护按键排序的索引。

第五，std::list是双向链表，额外保存两个指针；如果只需要单向遍历，可使用更省空间的std::forward_list，但它功能更受限。

很多初学者会误以为“频繁插入删除就一定该用 list”，这是不准确的。如果插入位置本身需要通过查找或遍历得到，那么总成本仍是 O(n)，而且vector的连续内存和批量移动可能更快。list更适合已经持有目标位置迭代器、需要稳定引用、需要链表拼接的场景，例如任务调度、LRU 链表部分、事件订阅节点管理等。

4. 介绍一下 deque 的优缺点

核心：deque是双端队列，支持在头部和尾部高效插入删除，也支持 O(1) 随机访问。它可以理解为“分段连续数组”，兼顾了vector的部分随机访问能力和双端操作能力，但迭代器和内存结构更复杂。

deque并不是一整块连续内存，而通常由一个“映射表”管理多个固定大小的数据块：

map/中控数组 ┌──────┬──────┬──────┐ │ ptr0 │ ptr1 │ ptr2 │ └──┬───┴──┬───┴──┬───┘ ↓ ↓ ↓ [ ][A][B] [C][D][E] [F][G][ ] 头部可扩展 ↑ ↑ 尾部可扩展

因此它既能push_front，也能push_back。

#include <deque> #include <iostream> int main() { std::deque<int> dq; dq.push_back(2); dq.push_back(3); dq.push_front(1); dq.push_front(0); std::cout << dq.front() << '\n'; // 0 std::cout << dq.back() << '\n'; // 3 std::cout << dq[2] << '\n'; // O(1) 随机访问 dq.pop_front(); dq.pop_back(); }

优点

第一，头尾插入删除都是 O(1)。vector在头部插入需要移动全部元素，而deque只需要在头部数据块不足时申请新块。

第二，支持随机访问。虽然内部不是单块连续内存，但operator[]仍是常数时间，因为它可以先根据下标定位数据块，再定位块内偏移。

第三，不会像vector那样因扩容而整体搬移所有元素。它通过增加数据块扩展空间。

第四，适合实现队列、滑动窗口、工作窃取队列、BFS 队列等双端操作频繁的结构。

#include <deque> #include <vector> std::vector<int> max_sliding_window(const std::vector<int>& nums, int k) { std::deque<int> q; // 保存下标，对应值单调递减 std::vector<int> ans; for (int i = 0; i < static_cast<int>(nums.size()); ++i) { while (!q.empty() && nums[q.back()] <= nums[i]) { q.pop_back(); } q.push_back(i); if (q.front() <= i - k) q.pop_front(); if (i >= k - 1) ans.push_back(nums[q.front()]); } return ans; }

缺点

第一，内部结构比vector复杂。随机访问需要两次定位，迭代器也要保存当前位置、数据块边界和中控表信息，因此遍历和下标访问通常略慢于vector。

第二，中间插入删除仍然是 O(n)，因为要移动元素，不要把它误解成任意位置都高效。

第三，内存不是单一连续块，不能像vector.data()那样直接得到一个完整连续数组。

第四，没有reserve/capacity这类容量接口，因为它的扩容模型与vector不同。

第五，双端插入可能使迭代器失效；虽然元素引用通常比vector更稳定，但使用时仍应查阅标准规则，不要长期保存 begin/end 迭代器后继续修改容器。

简单来说：只在尾部操作优先vector；头尾都要操作选deque；需要 FIFO 队列时，std::queue默认底层容器就是deque。如果没有明确的双端需求，不要因为deque“功能更全”就默认使用它，vector的简单性和缓存性能通常更优。

5. 介绍一下 map & set 的优缺点

核心：map和set是 C++ 有序关联容器，底层通常是红黑树，元素始终按照比较规则排序。set只存 key，map存 key-value；它们支持 O(log n) 的查找、插入、删除和范围查询，缺点是节点开销大、缓存局部性不如连续容器。

#include <iostream> #include <map> #include <set> #include <string> int main() { std::set<int> s; s.insert(30); s.insert(10); s.insert(20); for (int x : s) { std::cout << x << ' '; // 10 20 30，有序 } std::map<std::string, int> scores; scores["Alice"] = 95; scores["Bob"] = 88; scores["Cindy"] = 91; for (const auto& [name, score] : scores) { std::cout << name << ": " << score << '\n'; } auto it = scores.lower_bound("B"); if (it != scores.end()) { std::cout << it->first << '\n'; // Bob } }

四类有序关联容器区别如下：

容器	是否存 value	key 是否可重复	用途
`set<T>`	否，只存 key	不可重复	去重、有序集合
`map<K,V>`	是	key 不可重复	有序字典
`multiset<T>`	否	可重复	有序计数集合
`multimap<K,V>`	是	可重复	一个 key 对应多个值

优点

第一，元素始终有序。遍历时按 key 升序或按自定义比较器顺序输出，不需要每次排序。

第二，查找、插入、删除复杂度稳定为 O(log n)。相比哈希表平均 O(1) 但最坏可能退化，红黑树的最坏时间复杂度更可预测。

第三，支持范围查询和相邻查询。lower_bound返回第一个不小于某 key 的位置，upper_bound返回第一个大于某 key 的位置：

std::map<int, std::string> users = { {10, "A"}, {20, "B"}, {30, "C"}, {40, "D"} }; auto left = users.lower_bound(15); auto right = users.upper_bound(30); for (auto it = left; it != right; ++it) { // 输出 key 在 [15,30] 的元素：20、30 }

第四，迭代器稳定性较好。插入不会使已有迭代器失效，删除只影响被删除元素的迭代器。

第五，自定义类型只要能定义严格弱序比较规则即可作为 key。

缺点

第一，单次查找通常比哈希表慢。O(log n) 虽然优秀，但大数据量下不如unordered_map的平均 O(1)。

第二，节点式结构内存开销大。每个节点通常包含颜色、父指针、左指针、右指针和平衡信息，存储小对象时额外空间明显。

第三，缓存局部性差。节点分散在堆上，树遍历可能产生较多 cache miss。

第四，插入删除需要旋转、染色等平衡操作，实现成本高于普通数组。

第五，要求 key 可比较。如果比较规则定义错误，例如不满足严格弱序，可能产生未定义行为。

使用建议是：需要“有序遍历、范围查询、稳定最坏复杂度”时选map/set；只做等值查找且不关心顺序时，优先考虑unordered_map/unordered_set；如果 key 本身是连续小整数，甚至直接用vector索引可能更快。

6. 介绍一下 mutable 关键字的作用

核心：mutable用来声明“即使对象处于 const 状态，该成员也可以被修改”。它主要用于不影响对象逻辑状态的缓存、延迟计算、互斥锁、统计信息等；lambda 表达式中的mutable则表示可以修改按值捕获的副本。

普通const成员函数中，不能修改成员变量：

class Counter { private: int value = 0; public: void add() const { // ++value; // 错误：const 成员函数不能修改普通成员 } };

但有些成员的修改并不改变对象“看起来的状态”。例如一个只读查询函数内部需要加锁，或者第一次查询时缓存结果，之后直接返回缓存。此时锁和缓存就适合声明为mutable。

#include <iostream> #include <mutex> #include <optional> class Data { private: int raw = 42; // const 接口中也需要加锁 mutable std::mutex mtx; // 缓存不影响对象的逻辑值 mutable std::optional<int> cache; public: int get_value() const { std::lock_guard<std::mutex> lock(mtx); if (!cache.has_value()) { cache = raw * 2; // 逻辑上仍是只读查询 } return *cache; } };

使用场景一：线程安全

const成员函数通常表示只读操作，但多线程下“读”也需要锁。mtx.lock()会改变互斥量内部状态，因此必须把锁声明为mutable：

mutable std::mutex mtx;

使用场景二：缓存和延迟计算

#include <cmath> #include <optional> class Circle { private: double radius; mutable std::optional<double> area_cache; public: explicit Circle(double r) : radius(r) {} double area() const { if (!area_cache) { area_cache = std::acos(-1.0) * radius * radius; } return *area_cache; } };

调用者多次调用area()，从外部看结果不变，因此它仍然符合“逻辑常量性”；但内部第一次计算后会缓存结果。

使用场景三：调试统计

class Query { private: mutable int query_count = 0; public: int result() const { ++query_count; // 统计只读查询被调用次数 return 100; } };

lambda 中的 mutable

lambda 默认把operator()声明为 const，因此不能修改按值捕获的变量。加上mutable后可以修改捕获副本：

#include <iostream> int main() { int x = 10; auto f = [x]() mutable { ++x; std::cout << x << '\n'; }; f(); // 11 f(); // 12 std::cout << x << '\n'; // 外部 x 仍然是 10 }

这里修改的是 lambda 对象内部的捕获副本，不是外部变量本身。若按引用捕获，是否加mutable的规则不同，因为引用本身重新绑定与修改所指对象是两回事。

注意事项

mutable不是用来绕过const检查的万能手段。如果一个成员的修改会影响用户可观察结果，例如对象的真实业务值，就不应该为了编译通过而随意加mutable。滥用它会破坏 const 正确性，让只读接口偷偷改变状态，使代码更难推理，也可能引入线程安全问题。正确判断标准是：该成员变化后，对象在逻辑上是否仍可视为未改变。锁、缓存、统计计数通常符合；核心数据字段通常不符合。

7. map 的底层原理是什么？

核心：C++ 标准只规定std::map的复杂度和接口，主流标准库通常使用红黑树实现。红黑树是一种近似平衡的二叉搜索树，通过节点颜色和旋转保证树高为 O(log n)，因此查找、插入、删除都能保持 O(log n)。

std::map中的元素按 key 有序存储，每个元素是std::pair<const Key, T>。之所以 key 带const，是因为如果允许直接修改 key，就可能破坏树的有序结构。想修改 key，通常应先删除旧节点，再插入新节点。

二叉搜索树的基本规则是：左子树 key 小于当前节点，右子树 key 大于当前节点。中序遍历即可得到有序序列：

30 / \ 10 50 \ / 20 40 中序遍历：10 → 20 → 30 → 40 → 50

普通二叉搜索树在最坏情况下可能退化成链表：

10 \ 20 \ 30 \ 40

此时查找退化为 O(n)。红黑树通过以下规则维持近似平衡：

节点是红色或黑色。
根节点是黑色。
空叶子节点视为黑色。
红色节点的两个子节点必须是黑色，即不能有连续红色节点。
从任一节点到其所有叶子节点的路径，黑色节点数量相同。

这些规则保证最长路径不会超过最短路径的两倍左右，因此树高为 O(log n)。

#include <iostream> #include <map> int main() { std::map<int, const char*> m; m[3] = "C"; m[1] = "A"; m[2] = "B"; for (const auto& [key, value] : m) { std::cout << key << ':' << value << ' '; } // 输出 1:A 2:B 3:C }

查找过程类似二叉搜索：

find(40) 30 / \ 10 50 \ 40 40 > 30 → 去右子树 40 < 50 → 去左子树 找到 40

插入时，先按二叉搜索树规则找到位置，再插入新节点。新节点通常为红色，因为这样不会增加路径上的黑色节点数量。但插入后可能违反红黑规则，需要通过：

重新染色；
左旋；
右旋；

恢复平衡。删除也类似，先删除节点，再通过旋转和染色修复平衡。

map的迭代器本质上会沿红黑树进行中序遍历，所以输出始终有序：

auto it = mp.lower_bound(20); ++it; // 得到 key 顺序上的下一个元素

它的几个设计结果非常重要：

查找、插入、删除：O(log n)。
有序遍历：O(n)。
lower_bound/upper_bound：O(log n)，可做范围查询。
插入和删除不会导致其他元素整体移动。
节点内存不连续，缓存性能不如vector。
key 必须能按比较器形成严格弱序。

面试中回答此题时，建议说“主流实现通常是红黑树”，而不是绝对说“标准规定必须是红黑树”。标准约束的是复杂度和行为，红黑树是最常见实现方案。与unordered_map的哈希表相比，map牺牲平均查找速度，换来了有序性、稳定最坏复杂度和范围查询能力。

8. map 和 unordered_map 了解吗？

核心：map通常基于红黑树，key 有序，查找、插入、删除为 O(log n)；unordered_map通常基于哈希表，key 无序，平均 O(1) 查找，最坏 O(n)。选择依据是是否需要顺序、范围查询、稳定最坏复杂度以及 key 是否方便定义哈希。

#include <iostream> #include <map> #include <unordered_map> int main() { std::map<int, const char*> ordered; ordered[3] = "C"; ordered[1] = "A"; ordered[2] = "B"; std::cout << "map 顺序：\n"; for (const auto& [k, v] : ordered) { std::cout << k << ' ' << v << '\n'; } // 1 2 3，按 key 有序 std::unordered_map<int, const char> hashed; hashed[3] = "C"; hashed[1] = "A"; hashed[2] = "B"; std::cout << "unordered_map 顺序不保证：\n"; for (const auto& [k, v] : hashed) { std::cout << k << ' ' << v << '\n'; } }

两者对比：

对比项	`map`	`unordered_map`
常见底层	红黑树	哈希表
元素顺序	按 key 有序	不保证顺序
查找	O(log n)	平均 O(1)，最坏 O(n)
插入	O(log n)	平均 O(1)
删除	O(log n)	平均 O(1)
key 要求	可比较，严格弱序	可哈希，且能用`==`判断相等
范围查询	支持	不支持
内存	树节点指针和颜色开销	桶数组 + 节点开销
性能稳定性	稳定	受哈希冲突和 rehash 影响
适用场景	有序、范围、稳定复杂度	精确 key 快速查找

map的核心优势是有序。例如需要按分数排序、按时间范围查找、找第一个大于某个 key 的元素：

std::map<int, std::string> rank = { {60, "pass"}, {80, "good"}, {90, "excellent"} }; auto it = rank.lower_bound(80); // 可以继续向后遍历 80、90

unordered_map的核心优势是等值查找快：

std::unordered_map<std::string, int> word_count; for (const auto& word : words) { ++word_count[word]; // 平均 O(1) }

自定义类型作为 key 时，二者要求不同。map需要比较器：

struct Point { int x, y; }; struct PointCompare { bool operator()(const Point& a, const Point& b) const { if (a.x != b.x) return a.x < b.x; return a.y < b.y; } }; std::map<Point, int, PointCompare> point_map;

unordered_map需要哈希函数和相等判断：

#include <functional> struct Point { int x, y; bool operator==(const Point& other) const { return x == other.x && y == other.y; } }; struct PointHash { std::size_t operator()(const Point& p) const noexcept { std::size_t h1 = std::hash<int>{}(p.x); std::size_t h2 = std::hash<int>{}(p.y); return h1 ^ (h2 << 1); } }; std::unordered_map<Point, int, PointHash> point_hash;

选择建议：如果只做find/insert/erase且不需要顺序，数据量较大时通常优先unordered_map；如果需要有序输出、前缀或区间查询、性能必须有稳定上界，选map。在嵌入式或实时系统中，哈希表 rehash 带来的不确定延迟可能不可接受，此时map的 O(log n) 反而更可控。还要注意，不要依赖unordered_map的遍历顺序，即使某次实验看起来有规律，也不是标准保证。

9. hashmap 和 map 的区别，底层数据结构算法是什么？

核心：C++ 中通常说的 hashmap 对应std::unordered_map，底层一般是哈希表；map底层通常是红黑树。哈希表通过哈希函数把 key 映射到桶，平均 O(1)；红黑树通过有序树结构查找，稳定 O(log n)。

9.1 哈希表工作原理

哈希表的基本流程是：

key ↓ hash(key) 哈希值 ↓ 对桶数取模或二次映射 bucket index ↓ 在对应桶中查找 key

图示：

buckets ┌────────────┐ │ bucket 0 │ → (key=18,v) → (key=3,v) ├────────────┤ │ bucket 1 │ ├────────────┤ │ bucket 2 │ → (key=2,v) ├────────────┤ │ bucket 3 │ → (key=7,v) └────────────┘

不同 key 可能映射到同一个桶，这叫哈希冲突。常见冲突处理方法有：

链地址法：每个桶挂一个链表或节点序列，主流 C++ 标准库的unordered_map多采用这种思想。
开放寻址法：冲突后按线性探测、二次探测或双重哈希寻找下一个空位。
再哈希：使用第二个哈希函数确定步长。

C++ 标准没有强制规定具体哈希表实现，但主流实现通常使用桶加单向链表形式。

#include <iostream> #include <unordered_map> int main() { std::unordered_map<std::string, int> table; table["apple"] = 1; table["banana"] = 2; if (auto it = table.find("apple"); it != table.end()) { std::cout << it->second << '\n'; } std::cout << "bucket count: " << table.bucket_count() << '\n'; std::cout << "load factor: " << table.load_factor() << '\n'; }

负载因子为：

load_factor = 元素数量 / 桶数量

负载因子越高，冲突越多。当负载因子超过max_load_factor时，容器会进行rehash，申请更多桶并重新分布元素。rehash 后迭代器通常失效，但元素引用一般仍有效。

9.2 map 工作原理

map通常基于红黑树：

30(B) / \ 10(B) 50(B) \ / 20(R) 40(R)

查找时不断比较 key：

find(40): 40 与 30 比较 → 右子树 40 与 50 比较 → 左子树 找到 40

插入、删除后通过旋转和染色维持平衡，因此高度保持 O(log n)。

9.3 核心区别

维度	hashmap / unordered_map	map
底层结构	哈希表	红黑树，常见实现
查找复杂度	平均 O(1)，最坏 O(n)	O(log n)
插入复杂度	平均 O(1)，可能 rehash	O(log n)
删除复杂度	平均 O(1)	O(log n)
是否有序	无序	按 key 有序
范围查询	不适合	很适合
key 要求	哈希函数 + 相等判断	比较函数
最坏性能	哈希冲突严重时退化	稳定
内存特点	桶数组加节点，可能有空桶	每节点平衡树指针开销
遍历	顺序不稳定	中序遍历有序

9.4 使用建议

如果需求是“根据用户 ID、单词、模型名快速查值”，不关心顺序，用unordered_map：

std::unordered_map<uint64_t, User> user_cache;

如果需求是“按时间排序、按分数区间统计、找最接近某个 key 的元素”，用map：

std::map<long long, Event> time_series; auto it = time_series.lower_bound(start_time);

哈希表性能高度依赖哈希函数质量。如果 key 容易被构造出大量冲突，最坏情况可能从 O(1) 退化为 O(n)，这也是算法题或安全场景中可能被哈希冲突攻击的原因。红黑树虽然平均慢一些，但每次操作的复杂度上界更稳定。

一句话总结：hashmap 用哈希换平均 O(1)，但无序且最坏情况可能退化；map 用平衡树换有序和稳定 O(log n)，但节点开销和常数成本更高。

总体选择建议

需求	首选容器
大多数普通集合	`vector`
已知数据量，减少扩容	`vector + reserve`
头部尾部都频繁增删	`deque`
先进先出	`queue`
后进先出	`stack`
每次取最大值/最小值	`priority_queue`
已知迭代器位置频繁插入删除	`list`
key 有序、范围查询	`map/set`
只按 key 等值快速查找	`unordered_map/unordered_set`
key 可重复且有序	`multimap/multiset`
key 可重复且无序	`unordered_multimap/unordered_multiset`

最重要的记忆主线是：

vector：连续数组，随机访问强，中间增删弱 deque：分段数组，双端增删强，中间仍弱 list：链表，已知位置增删强，随机访问弱 map/set：红黑树，有序、稳定 O(log n) unordered_*：哈希表，平均 O(1)，无序，最坏可能退化 mutable：const 逻辑不变时，允许修改缓存、锁等辅助成员

四、STL 容器与数据结构（进阶）（一）