四、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比较器、哈希函数 └─ mutableconst 对象逻辑可修改性选择顺序可以简单记为默认用 vector 需要双端进出 → deque 需要有序遍历 / 范围查询 → map/set 需要按键平均 O(1) 查找 → unordered_map 已有迭代器且频繁任意位置插入删除 → list 需要 LIFO/FIFO/优先级 → stack/queue/priority_queue1. 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::arrayint, 3 arr {1, 2, 3}; // 2. 动态数组 std::vectorint vec; vec.reserve(100); vec.push_back(1); vec.push_back(2); // 3. 双端队列 std::dequeint dq; dq.push_front(1); dq.push_back(2); // 4. 双向链表 std::listint lst {1, 2, 3}; lst.push_front(0); // 5. 有序集合去重且按 key 排序 std::setint s {3, 1, 2}; // 6. 有序字典 std::mapstd::string, int mp; mp[alice] 90; mp[bob] 85; // 7. 哈希字典 std::unordered_mapstd::string, int ump; ump[model_a] 1; ump[model_b] 2; // 8. 栈 std::stackint st; st.push(1); // 9. 队列 std::queueint q; q.push(1); // 10. 优先队列默认大根堆 std::priority_queueint 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)不支持LIFOqueue适配器不支持O(1)O(1)不支持FIFOSTL 容器通常通过迭代器统一访问std::vectorint 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][ ][ ][ ][ ][ ] └──── 已使用 size5 ────┘ └──────────── capacity10 ────────┘size当前元素个数。capacity当前已分配空间最多能放多少元素。当size capacity再push_back时会重新分配更大空间把旧元素移动或拷贝过去再释放旧空间。#include iostream #include vector int main() { std::vectorint 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::vectorint v {1, 2, 3}; auto it v.begin() 1; v.push_back(4); // 若发生扩容it 可能已经失效不能继续使用第四容量可能大于实际元素数造成一定空间浪费可用shrink_to_fit()请求归还空间但是否真的归还由实现决定。第五vectorbool是特化版本按位存储不完全满足普通容器语义对单个“元素”取引用时要特别小心。工程建议是如果元素数量大致已知优先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::listint 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::listint a {1, 3, 5}; std::listint b {2, 4, 6}; a.merge(b); // 合并两个有序链表 a.sort(); // 链表排序 a.unique(); // 删除连续重复元素 a.splice(a.end(), std::listint{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::dequeint 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::vectorint max_sliding_window(const std::vectorint nums, int k) { std::dequeint q; // 保存下标对应值单调递减 std::vectorint ans; for (int i 0; i static_castint(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只存 keymap存 key-value它们支持 O(log n) 的查找、插入、删除和范围查询缺点是节点开销大、缓存局部性不如连续容器。#include iostream #include map #include set #include string int main() { std::setint s; s.insert(30); s.insert(10); s.insert(20); for (int x : s) { std::cout x ; // 10 20 30有序 } std::mapstd::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 } }四类有序关联容器区别如下容器是否存 valuekey 是否可重复用途setT否只存 key不可重复去重、有序集合mapK,V是key 不可重复有序字典multisetT否可重复有序计数集合multimapK,V是可重复一个 key 对应多个值优点第一元素始终有序。遍历时按 key 升序或按自定义比较器顺序输出不需要每次排序。第二查找、插入、删除复杂度稳定为 O(log n)。相比哈希表平均 O(1) 但最坏可能退化红黑树的最坏时间复杂度更可预测。第三支持范围查询和相邻查询。lower_bound返回第一个不小于某 key 的位置upper_bound返回第一个大于某 key 的位置std::mapint, 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::optionalint cache; public: int get_value() const { std::lock_guardstd::mutex lock(mtx); if (!cache.has_value()) { cache raw * 2; // 逻辑上仍是只读查询 } return *cache; } };使用场景一线程安全const成员函数通常表示只读操作但多线程下“读”也需要锁。mtx.lock()会改变互斥量内部状态因此必须把锁声明为mutablemutable std::mutex mtx;使用场景二缓存和延迟计算#include cmath #include optional class Circle { private: double radius; mutable std::optionaldouble 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 中的 mutablelambda 默认把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::pairconst 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::mapint, 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_boundO(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::mapint, 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_mapint, 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; } }两者对比对比项mapunordered_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::mapint, std::string rank { {60, pass}, {80, good}, {90, excellent} }; auto it rank.lower_bound(80); // 可以继续向后遍历 80、90unordered_map的核心优势是等值查找快std::unordered_mapstd::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::mapPoint, 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::hashint{}(p.x); std::size_t h2 std::hashint{}(p.y); return h1 ^ (h2 1); } }; std::unordered_mapPoint, 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 │ → (key18,v) → (key3,v) ├────────────┤ │ bucket 1 │ ├────────────┤ │ bucket 2 │ → (key2,v) ├────────────┤ │ bucket 3 │ → (key7,v) └────────────┘不同 key 可能映射到同一个桶这叫哈希冲突。常见冲突处理方法有链地址法每个桶挂一个链表或节点序列主流 C 标准库的unordered_map多采用这种思想。开放寻址法冲突后按线性探测、二次探测或双重哈希寻找下一个空位。再哈希使用第二个哈希函数确定步长。C 标准没有强制规定具体哈希表实现但主流实现通常使用桶加单向链表形式。#include iostream #include unordered_map int main() { std::unordered_mapstd::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)查找时不断比较 keyfind(40): 40 与 30 比较 → 右子树 40 与 50 比较 → 左子树 找到 40插入、删除后通过旋转和染色维持平衡因此高度保持 O(log n)。9.3 核心区别维度hashmap / unordered_mapmap底层结构哈希表红黑树常见实现查找复杂度平均 O(1)最坏 O(n)O(log n)插入复杂度平均 O(1)可能 rehashO(log n)删除复杂度平均 O(1)O(log n)是否有序无序按 key 有序范围查询不适合很适合key 要求哈希函数 相等判断比较函数最坏性能哈希冲突严重时退化稳定内存特点桶数组加节点可能有空桶每节点平衡树指针开销遍历顺序不稳定中序遍历有序9.4 使用建议如果需求是“根据用户 ID、单词、模型名快速查值”不关心顺序用unordered_mapstd::unordered_mapuint64_t, User user_cache;如果需求是“按时间排序、按分数区间统计、找最接近某个 key 的元素”用mapstd::maplong 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已知迭代器位置频繁插入删除listkey 有序、范围查询map/set只按 key 等值快速查找unordered_map/unordered_setkey 可重复且有序multimap/multisetkey 可重复且无序unordered_multimap/unordered_multiset最重要的记忆主线是vector连续数组随机访问强中间增删弱 deque分段数组双端增删强中间仍弱 list链表已知位置增删强随机访问弱 map/set红黑树有序、稳定 O(log n) unordered_*哈希表平均 O(1)无序最坏可能退化 mutableconst 逻辑不变时允许修改缓存、锁等辅助成员