面试宝典(六):STL 容器源码与虚函数多态

STL 的整体架构：容器、算法、迭代器、分配器
vector：连续内存与迭代器失效
list/ deque：链表与双端队列
map / set：红黑树实现
unordered_map / unordered_set：哈希表实现
迭代器与 std::allocator
容器性能对比与选型
虚函数表（vtable）与多态原理
虚析构函数：为什么基类析构必须是 virtual
纯虚函数、抽象类与接口
多继承、菱形继承与虚继承
RTTI：dynamic_cast 与 typeid
虚函数开销与替代方案（CRTP）
面试真题与速记

1. STL 的整体架构

STL（Standard Template Library）由四大部分组成：

容器（Containers）
：vector/list/deque/map/set/unordered_map 等。
算法（Algorithms）
：sort/find/copy/for_each 等，与容器解耦。
迭代器（Iterators）
：连接容器与算法的"泛型指针"，定义 5 类（输入/输出/前向/双向/随机访问/连续 C++20）。
分配器（Allocators）
：负责内存分配（默认 std::allocator）。

设计哲学：算法只认迭代器，不认容器，因此 sort(v.begin(), v.end()) 对任意随机访问容器通用——这是泛型编程的精华。面试能讲清"迭代器是胶水层"很重要。

2. `vector`：连续内存与迭代器失效

vector 是动态数组，元素在连续内存中，支持下标随机访问 O(1)。

底层结构：三个指针（或指针+大小+容量）——start、finish（已用末尾）、end_of_storage（容量末尾）。

扩容（reallocate）：size == capacity 时 push_back 触发扩容，通常翻倍容量，分配新内存、拷贝/移动旧元素、释放旧内存。因此 push_back 均摊 O(1)，但单次可能 O(n)。

std::vector<int> v;v.reserve(1000);   // 预分配，避免多次扩容for (int i = 0; i < 1000; ++i) v.push_back(i); // 不再扩容

迭代器失效（高频考点）：

插入
：引起扩容时，所有迭代器/引用/指针全部失效；未扩容时，插入点之后的迭代器失效。
删除
：被删元素及之后的迭代器失效。
erase 返回下一个有效迭代器
，所以正确删除循环是：

for (auto it = v.begin(); it != v.end(); ) {    if (*it % 2 == 0) it = v.erase(it); // erase 返回新位置    else ++it;}

erase 不缩减容量：erase 只移动元素，容量不变；要真正释放用 shrink_to_fit()（C++11，非强制）或 vector<T>(v).swap(v) 惯用法。

面试加分：vector<bool> 是特化，用位压缩，其 operator[] 返回代理对象而非 bool&（所以不能用 auto& 绑定），且不支持 data() 返回 bool*。这是个著名坑。

3. `list` / `deque`：链表与双端队列

list（双向链表）：

节点分散在堆上，每个节点含前/后指针 + 数据。
插入/删除任意位置 O(1)（已知位置），但随机访问 O(n)。
插入永远不会使其他迭代器失效
（只有被删节点失效）——这与 vector 相反，是选型的依据。
额外内存开销（两个指针/节点），缓存局部性差。

deque（双端队列）：

分段连续（中央 map 指向多个固定大小缓冲区数组），支持两端 O(1) 插入删除，且支持随机访问 O(1)。
下标访问略慢于 vector（先定位段）。
std::stack
/std::queue 默认底层容器就是 deque。

对比选型：需要随机访问+尾部追加→vector；频繁中间插入删除→list；双端操作→deque。

4. `map` / `set`：红黑树实现

std::map/std::set/std::multimap/std::multiset 底层是红黑树（Red-Black Tree）——一种自平衡二叉搜索树。

性质：

元素有序（按 key 比较，std::less 默认），中序遍历即有序序列。
插入/删除/查找均为 O(log n)。
节点含颜色位、父/左/右指针，内存开销大、缓存差。

std::map<std::string, int> m;m["a"] = 1; m["b"] = 2;for (auto& [k, v] : m) std::cout << k << ":" << v; // 按 key 有序输出

map vs unordered_map：

需要有序遍历 / 范围查询（lower_bound/upper_bound）→ map。
只查不排序、要更快平均 O(1) → unordered_map。

面试考点：红黑树的平衡维持（旋转 + 变色）保证最长路径不超过最短路径两倍；为什么不用 AVL？红黑树插入删除旋转更少，更适合作业系统/STL 场景。能说出这点是加分。

5. `unordered_map` / `unordered_set`：哈希表实现

底层是开链法（separate chaining）哈希表：数组桶（bucket）+ 每个桶挂链表（C++11 后元素多时转红黑树，类似 Java HashMap 8+）。

关键参数：

负载因子（load factor）
= 元素数 / 桶数，默认 1.0，超过触发 rehash（扩容并重散列，所有迭代器失效）。
哈希函数
：内置类型有默认 std::hash；自定义类型需特化 std::hash 或传自定义哈希。
相等比较
：key 相等用 operator== 或自定义。

struct Point { int x, y; };struct PointHash {    size_toperator()(const Point& p)const{        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);    }};std::unordered_map<Point, int, PointHash> m;

性能：平均 O(1) 查找/插入/删除，最坏 O(n)（全部哈希冲突进同一桶）。reserve/max_load_factor 可调优。

面试坑：

把 unordered_map 当缓存但 key 是 std::string，注意哈希计算开销。
修改 key 会使哈希失效（绝不能改 map 元素的 key，只能删了重插）。
遍历时 rehash 导致迭代器失效。

6. 迭代器与 `std::allocator`

迭代器分类（决定算法复杂度）：

输入/输出：单遍。
前向：单方向多遍（forward_list/unordered_*）。
双向：可前进后退（list/map）。
随机访问：可 +=n、<（比较）（vector/deque/array）。
连续（C++20）：内存连续（vector/array）。

算法根据迭代器类别选择最优实现（如 sort 需要随机访问，对 list 用 list::sort 而不是 std::sort）。

std::allocator：STL 默认分配器，封装 ::operator new/delete，基本是 new/delete 的薄包装。C++11 起支持 construct/destroy 分离（但 construct 在 C++20 被弃用，用 std::construct_at）。

高级话题：std::allocator_traits、状态无关 vs 状态相关分配器、std::pmr（C++17 多态内存资源，让容器用内存池）。面试提到 pmr 可加分。

7. 容器性能对比与选型

容器	随机访问	头部插入	中间插入	查找	有序	底层
`vector`	O(1)	O(n)	O(n)	O(n)	否	动态数组
`deque`	O(1)	O(1)	O(n)	O(n)	否	分段数组
`list`	O(n)	O(1)	O(1)*	O(n)	否	双向链表
`map`	—	—	O(log n)	O(log n)	是	红黑树
`unordered_map`	—	—	O(1)~	O(1)~	否	哈希表

* 已知迭代器位置。

选型口诀：默认 vector；要字典序/范围查用 map；要极快查且不排序用 unordered_map；频繁两端操作用 deque；频繁任意位置删插且不需随机访问用 list。

8. 虚函数表（vtable）与多态原理

多态（polymorphism）：基类指针/引用调用虚函数时，运行时根据实际对象类型调用对应函数——动态绑定（late binding）。

实现机制：

含虚函数的类，编译器为其生成一张虚函数表（vtable）（每个类一份，存虚函数地址）。
每个对象头部有一个隐含的 vptr（虚表指针），指向所属类的 vtable。
调用虚函数时，通过 vptr -> vtable[slot] 找到实际函数。

#include<iostream>struct Animal { virtualvoidsound(){ std::cout << "?\n"; } virtual ~Animal() = default; };struct Dog : Animal { voidsound()override{ std::cout << "woof\n"; } };intmain(){    Animal* a = new Dog();    a->sound();        // 输出 woof（动态绑定，查 Dog 的 vtable）    delete a;}

开销：

空间：每个对象多一个 vptr（通常 8 字节），每类一份 vtable。
时间：一次指针间接寻址（vptr → vtable → func），无法内联（失去优化机会，且破坏分支预测友好性）。

面试要点：每次虚调用多两次内存读取，且阻止内联——在热点循环里，虚函数可能成为性能瓶颈，这时考虑 CRTP/模板静态多态（见上一篇）或 final 关键字（final 类/函数可被编译器去虚拟化优化）。

9. 虚析构函数：为什么基类析构必须是 virtual

经典面试题：基类析构不写 virtual 会怎样？

struct Base { ~Base() { std::cout << "Base dtor\n"; } };       // 非虚struct Derived : Base { ~Derived() { std::cout << "Derived dtor\n"; } };Base* p = new Derived();delete p;   // 只调用 Base 析构！Derived 部分未释放 -> 资源泄漏 + UB 风险

原因：delete p 时若析构非虚，编译器按静态类型 Base 调用析构，不会下降到 Derived。若基类析构是 virtual，则通过 vtable 调到 Derived 析构，而析构会自动调用父类析构（析构链从派生到基类），完整释放。

结论：任何作为多态基类的类，析构函数必须是 virtual（或 =default 的虚析构）。反之，若类不用于多态（不会被父类指针删除），不必加虚析构——避免无谓的 vptr 开销。C++11 =default 可显式定义。

struct Base { virtual ~Base() = default; };  // 推荐

10. 纯虚函数、抽象类与接口

struct Shape {                               // 抽象类（不能实例化）    virtualdoublearea() const = 0;         // 纯虚函数    virtual ~Shape() = default;};struct Circle : Shape {    doublearea() constoverride { return 3.14 * r * r; }};

纯虚函数= 0
：派生类必须实现，否则派生类也是抽象类。
抽象类
：含纯虚函数，不能实例化，作接口/契约。
C++ 没有 interface 关键字，用"纯虚函数类"表达接口（Java/C# 的 interface 等价物）。

override 关键字（C++11）：显式标记重写，编译器帮你检查签名是否真匹配基类虚函数——防止"本想重写却写错签名变成重载/新函数"的隐蔽 bug。强烈建议所有重写都加 override。

final：final 类禁止被继承；final 虚函数禁止被进一步重写（助编译器去虚化优化）。

11. 多继承、菱形继承与虚继承

多继承：一个类继承多个基类。能力聚合有用，但带来歧义与复杂性。

菱形继承（diamond）：

      A     / \    B   C     \ /      D

若 A 有数据成员，D 会包含两份 A 的子对象（B、C 各一份），导致数据冗余与二义性（d.A::x 歧义）。

**虚继承（virtual inheritance）**解决：让 B、C 虚继承 A，D 中只保留一份 A 子对象。

struct A { int x; };struct B : virtual A {};struct C : virtual A {};struct D : B, C {};   // D 只有一份 x

代价：虚继承让对象布局复杂（含虚基类指针/偏移），访问虚基类成员需间接寻址，且构造函数初始化顺序改变（虚基类由最派生类直接初始化）。面试要能画出内存布局并指出"虚继承增加间接开销但消除冗余"。生产里尽量用组合而非菱形继承。

12. RTTI：`dynamic_cast` 与 `typeid`

RTTI（Run-Time Type Information）：运行时获取类型信息，依赖 vtable（含 typeinfo 指针）。

dynamic_cast<Derived*>(base_ptr)
：安全向下转型。若指针转型失败返回 nullptr；引用转型失败抛 std::bad_cast。底层走 vtable 的类型信息比对，有开销。
typeid(expr)
：返回 std::type_info，含类型名（typeid(T).name()，名字经编译器修饰，需用 c++filt 解）。

if (auto* d = dynamic_cast<Derived*>(p)) {    d->derived_only();  // 安全转型成功才调用}

面试权衡：dynamic_cast 频繁使用往往是设计味道（可用访问者模式/双分派替代）。能关 RTTI（-fno-rtti）以减小体积（如嵌入式、某些游戏引擎），但就失去 dynamic_cast/typeid。static_cast 不查运行期类型，转型错误是 UB，更快但危险。

13. 虚函数开销与替代方案（CRTP / 概念）

虚函数的真实成本：

每个对象 +vptr（8B）；每个类 +vtable。
每次调用：vptr → vtable → func，两次间接 + 可能缓存未命中。
阻止内联与很多优化（无法去虚拟化就慢）。

替代方案：

CRTP 静态多态
（见上一篇）：编译期确定调用目标，零运行开销。
final
：标记后编译器可去虚拟化，直接内联。
std::variant + std::visit
：用"访问者 + 编译期分派"代替继承多态，值语义、无堆分配、缓存友好（C++17 std::variant 是 modern 替代继承的利器）。
函数指针表 / std::function
：特定场景替代。

#include<variant>#include<iostream>struct Circle { doublearea()const{ return 3.14; } };struct Square { doublearea()const{ return 4.0; } };using Shape = std::variant<Circle, Square>;doublearea(const Shape& s){    return std::visit([](const auto& x){ return x.area(); }, s); // 编译期分派}

14. 面试真题与速记

速记清单：

STL 四件套：容器/算法/迭代器/分配器；迭代器是胶水层。
vector
连续内存、翻倍扩容、迭代器在扩容/erase 后失效。
list
插入不失效其他迭代器；deque 双端 O(1)。
map
=红黑树 O(log n) 有序；unordered_map=哈希 O(1) 无序；负载因子触发 rehash。
默认 vector；有序用 map；极速查用 unordered_map。
虚函数靠 vtable + vptr 动态绑定；开销在间接寻址与无法内联。
多态基类析构必须 virtual；重写加 override。
菱形继承用虚继承消冗余；RTTI 靠 dynamic_cast/typeid，有开销。
高频虚函数考虑 CRTP / final / std::variant 替代。

高频真题：

vector
扩容机制？迭代器何时失效？（翻倍；扩容全失效、erase 后失效）
map
和 unordered_map 怎么选？（有序/范围查 vs 极速查）
unordered_map
rehash 时迭代器失效吗？（全部失效）
为什么基类析构要 virtual？（避免只析构基类导致派生资源泄漏）
虚函数实现原理与开销？（vtable+vptr 间接寻址，阻止内联）
什么是 RTTI？dynamic_cast 失败返回什么？（运行期类型信息；指针返回 nullptr，引用抛 bad_cast）
菱形继承怎么解决？（虚继承）
如何避免虚函数性能损耗？（CRTP、final、variant+visit）
list::sort
和 std::sort 区别？（list 双向迭代器不能随机访问，须用成员 sort）
红黑树 vs AVL？（红黑树旋转少，更适合 STL）

小结

STL 与多态是 C++ 工程师的"内功"：容器选型看复杂度与内存布局，迭代器失效是高频 bug 源，哈希表负载因子与红黑树平衡是性能根基；虚函数与 vtable 支撑面向对象多态，但代价是间接寻址与失去内联，高级工程师懂得在"优雅的多态"与"极致的性能"之间，用 CRTP、final、std::variant 等手段做权衡。

15. 补充：`std::sort` 与比较器的陷阱

std::sort 要求比较器满足严格弱序（strict weak ordering）：comp(a,a) 必须为 false；若 comp(a,b) 且 comp(b,c) 则 comp(a,c)；以及不可比较性的传递性。违反会未定义行为（典型表现：排序时崩溃或死循环）。

// 错误：用 <= 而非 <，comp(a,a) 为真，违反严格弱序std::sort(v.begin(), v.end(), [](int a, int b){ return a <= b; }); // UB!// 正确std::sort(v.begin(), v.end(), [](int a, int b){ return a < b; });

面试点：比较器应标记 const、最好 noexcept、返回稳定结果（不要依赖会变的外部状态）。对 std::map 的 key 比较器同理——必须用严格弱序，否则查找/插入行为错乱。能说出"严格弱序"是排序与有序容器的底层契约，是高级工程师的素养。

16. 补充：`emplace` 与 `push` 的区别

emplace_back 在容器尾部原地构造元素（把参数完美转发给元素构造函数），避免先构造临时对象再移动/拷贝。push_back 需要先有元素（拷贝/移动）。

struct Person { std::string name; int age; Person(std::string n, int a):name(std::move(n)),age(a){} };std::vector<Person> v;v.push_back(Person("Tom", 20));     // 构造临时 + 移动v.emplace_back("Tom", 20);          // 原地构造，零多余拷贝

注意：emplace 能避免拷贝，但有时会产生隐式转换的"惊喜"（如 emplace 一个 int 到 vector<bool> 会触发 bool 转换）。面试能指出"emplace 省一次移动但语义要清楚"是细致之处。

17. 补充：对象内存布局与虚表偏移

含虚函数的对象，其内存布局（典型 64 位）：[vptr][基类子对象...][派生成员...]。多重继承下可能有多个 vptr（每个含虚函数的基类一个）。虚继承会引入虚基类表指针/偏移。

#include<iostream>struct A { virtualvoidf(){} int a; };struct B { virtualvoidg(){} int b; };struct C : A, B { int c; };intmain(){    C c;    std::cout << sizeof(c) << "\n"; // vptr_A + a + vptr_B + b + c，含对齐填充    A* pa = &c;  // pa 指向 C 起始（= &c）    B* pb = &c;  // pb 指向 B 子对象（= (char*)&c + 偏移），这里发生指针调整}

面试点：把派生类指针转基类指针时，若基类不在最前，编译器会悄悄调整指针地址（pointer adjustment），这就是为什么"多重继承下 dynamic_cast/static_cast 能正确定位"。能画出这个布局图，面试基本封神。

18. 真题演练（STL 与多态进阶）

Q1：vector 的 data() 什么时候可用？vector<bool> 有 data() 吗？ A：连续内存容器的 data() 返回指向底层数组的指针（随机访问容器都有）。但 vector<bool> 是位压缩特化，没有data() 返回 bool*（它根本不是字节数组），这也是为什么需要真布尔数组时应改用 vector<char> 或 std::bitset/boost::dynamic_bitset。

Q2：为什么 std::sort 不能用于 std::list？ A：std::sort 要求随机访问迭代器（需 it + n）；list 是双向迭代器，只能 ++/--。list 提供成员函数 sort()（用归并排序，O(n log n)），只重链指针不搬数据，比复制出 vector 再排更高效。

Q3：unordered_map 的 key 是自定义结构体，需要什么？ A：需提供 (1) 哈希函数（特化 std::hash 或传自定义 hash 对象）；(2) 相等比较（operator== 或自定义）。两者必须一致：相等的 key 必须哈希相同，否则查找失败。面试能说出"哈希与相等必须兼容"是正确性关键。

Q4：dynamic_cast 对没有虚函数的类能用吗？ A：不能。dynamic_cast 依赖 vtable 里的 RTTI 信息，要求源类型至少有虚函数（多态类型）；对非多态类型用 dynamic_cast 编译报错。若不需要运行期检查，可用 static_cast（但错误转型是 UB）。

Q5：final 关键字除了禁止继承还能做什么？ A：修饰虚函数可禁止进一步重写，给编译器"去虚拟化（devirtualization）"优化的机会——编译器知道不会再被覆盖，可能直接内联调用，消除 vtable 间接寻址。在性能敏感路径（如游戏引擎每帧调用百万次的虚函数）上收益明显。

Q6：迭代器失效的"通用规律"怎么记？ A：口诀——连续容器（vector/string）插入/删除使"之后"的迭代器失效，扩容时全部失效；节点式容器（list/map/set）插入不失效任何迭代器，删除只失效被删节点；unordered_* 在 rehash 时全部迭代器失效（但指针/引用仍有效，因元素不搬）。能套用这个框架基本不会错。

19. 深度专题：容器选型实战与 `reserve`/`shrink_to_fit`

很多性能问题源于"容器用错"或"没预留容量"：

vector::reserve(n)
：提前分配至少 n 容量，避免多次扩容拷贝。已知元素数量时必用（如读文件、批量构造）。一次扩容是 O(n) 拷贝，频繁 push_back 到百万级可能搬运几十 MB 数据。
shrink_to_fit()
（C++11）：请求释放多余容量（非强制，编译器可忽略）。但注意它会触发"分配新缓冲 + 移动 + 释放旧缓冲"，所以不要在循环里反复调用。
std::vector vs std::deque 内存
：vector 一处连续，缓存友好但扩容搬移；deque 分段，扩容不搬旧数据、中段插入不挪动全部，但随机访问多一次间接。
std::unordered_map 优化
：reserve(expected) + 设合理 max_load_factor 减少 rehash；自定义高效哈希（避免把所有字段异或，容易碰撞）。

std::vector<int> v;v.reserve(1'000'000);          // 一次分配，避免约 20 次翻倍扩容for (int i = 0; i < 1'000'000; ++i) v.push_back(i);// v.shrink_to_fit();         // 若确定不再增长才调用

面试点：能结合"扩容代价、缓存局部性、迭代器失效"三维度讲容器选型，而非背结论，是实战经验。

20. 真题再加码（STL 与多态终极）

Q1：std::map 的 operator[] 和 at() / find() 区别？ A：operator[] 若 key 不存在会插入默认值（可能意外增容、对 const map 不可用）；at() 不存在抛 out_of_range；find() 返回 end() 迭代器（最安全、无副作用）。读多写少且不想误插，请用 find 或 at。面试能指出"operator[] 的隐式插入"是常见陷阱。

Q2：为什么 std::vector 的 size() 是 O(1)？ A：vector 内部同时保存"已用大小"和"容量"两个值，size() 直接返回已用计数，O(1)。对比单链表需遍历才知长度（所以 std::list::size() 在 C++11 前可能是 O(n)，C++11 起要求 O(1) 但实现上维护计数）。

Q3：虚函数能声明为 inline 吗？ A：可以声明 inline virtual，但"虚调用"通过 vtable 间接寻址、无法内联（除非编译器能静态确定对象类型做去虚拟化）。inline 在虚函数上主要作为"可在头文件定义、建议内联"的提示，运行时多态场景下内联通常不生效。面试能区分"语法允许但运行期多半不内联"是精准回答。

Q4：std::enable_shared_from_this 的 vtable 关联？ A：enable_shared_from_this<T> 内部有一个 weak_ptr<T> 成员，由首个 shared_ptr 构造时填充。它不需要虚函数，而是通过 shared_ptr 的构造函数检测到基类 enable_shared_from_this 后，把弱引用挂上。面试能讲清"不是靠虚函数，而是靠 shared_ptr 构造时的类型探测"体现对实现的深层理解。

Q5：成员函数指针和普通函数指针能互转吗？ A：不能。成员函数指针包含"相对于对象起始的偏移/虚表索引"信息（尤其多继承/虚函数下），大小可能大于普通指针（甚至有 16/24 字节实现）。普通函数指针不能调成员函数（缺 this）。要用 std::function + lambda/std::bind 桥接。面试能说出"成员函数指针本质含 this 偏移"是细节功力。

Q6：C++ 对象模型里，空基类优化（EBO）有什么用？ A：空基类（无数据成员、无虚函数）在派生类中通常不占空间（编译器优化掉那 1 字节对齐），所以 struct Empty{}; struct D : Empty { int x; }; 的 sizeof(D) 可能就是 sizeof(int)。STL 大量用 EBO（如 std::less 作比较器基类）避免为"无状态策略类"付出内存代价。面试能举例 EBO 体现对对象模型的掌握。

21. 高频速答 20 题（STL 与多态闪电战）

STL 四件套？
容器、算法、迭代器、分配器。
vector 底层？
连续动态数组，三指针（start/finish/end_of_storage）。
vector 扩容策略？
通常翻倍，O(n) 搬迁，均摊 O(1) push_back。
vector 迭代器何时失效？
扩容全部失效；erase 后及之后失效。
list 插入影响其他迭代器吗？
不影响（只有被删节点失效）。
map 底层？
红黑树，有序，O(log n)。
unordered_map 底层？
开链哈希表，平均 O(1)。
rehash 时迭代器？
全部失效（指针/引用仍有效）。
map vs unordered_map 选型？
需要有序/范围查用 map；极速查用 unordered_map。
emplace vs push？
emplace 原地构造，省一次移动。
sort 比较器要求？
严格弱序，comp(a,a) 必须为 false。
vector<bool> 坑？
位压缩特化，无 data()，返回代理引用。
虚函数实现？
vtable + vptr 动态绑定，间接寻址、阻止内联。
基类析构为何 virtual？
防只析构基类导致派生资源泄漏。
重写加 override 好处？
编译期校验签名，防误写成重载。
纯虚函数与抽象类？=0
强制派生实现，含者不可实例化。
菱形继承怎么解？
虚继承消除冗余子对象。
dynamic_cast 失败？
指针返回 nullptr，引用抛 bad_cast。
final 作用？
禁止继承/重写，助编译器去虚拟化。
EBO 是什么？
空基类不占空间，STL 策略类常用。

22. 临场速记清单（STL 与多态篇面试前过一遍）

STL 四件套：容器/算法/迭代器/分配器；迭代器是连接二者的胶水层。
vector
连续内存、翻倍扩容、迭代器在扩容/erase 后失效；reserve 防抖动。
list
插入不失效其他迭代器；deque 双端 O(1) 但随机访问多一次间接。
map
=红黑树 O(log n) 有序；unordered_map=哈希 O(1) 无序；负载因子触发 rehash。
默认 vector；需有序/范围查用 map；极速查且不排序用 unordered_map。
比较器必须严格弱序；vector<bool> 是位压缩特化、无 data()、返回代理引用。
虚函数靠 vtable + vptr 动态绑定，开销在间接寻址与无法内联。
多态基类析构必须 virtual；重写一律加 override；接口用纯虚函数类表达。
菱形继承用虚继承消冗余；RTTI 靠 dynamic_cast/typeid，有运行期开销。
高频虚函数考虑 CRTP / final / std::variant+visit 替代，换性能。
emplace
原地构造省一次移动；operator[] 会隐式插入、find/at 更安全。
迭代器失效口诀：连续容器删后失效、节点容器只删节点、unordered rehash 全失效。

目录