STL 容器内幕：vector 的三个指针与 string 的 SSO

① 钩子：24 字节装下一百万个 int

sizeof(std::vector<int>)只有24 字节，却能装下一百万个int——因为它自己只存三个指针。

std::string的短字符串"免费"、不碰堆分配；vector扩容按 2 倍翻。这些"魔法"，在汇编和实测数据里全都能看见。

这一集我们拆开两个最常用的容器：vector（三个指针 + 连续存储）和string（SSO 短字符串优化），看它们的布局、扩容、和"为什么快"。

② 源码 vs 实测/汇编对照

__attribute__((noinline))intv_get(conststd::vector<int>&v,size_t i){returnv[i];}intmain(){std::string s_short="hi";std::string s_long="this is a much longer string that surely exceeds the short string buffer";...std::vector<int>v;for(inti=0;i<100;++i)v.push_back(i);// 打印每次容量变化}

实测输出（g++ 15.2.0，x86-64）：

sizeof(string)=32 sizeof(vector<int>)=24 short: obj=0x...fd20 data=0x...fd30 delta=16 ← SSO：数据在对象内部（偏移 +16） long: obj=0x...fd40 data=0x...4150 delta=... ← 超过 15B 才堆分配（地址在堆上很远） push 0 -> capacity 1 (data 换地址) push 1 -> capacity 2 (data 换地址) push 2 -> capacity 4 (data 换地址) push 4 -> capacity 8 ... push 8 -> capacity 16 ... push 16 -> capacity 32 ... push 32 -> capacity 64 ... push 64 -> capacity 128 ... ← 按 2 倍扩容，每次 data 都搬家

string 构造的汇编 —— SSO 分界就是一次比较：

basic_string::_M_construct(...): subq %rdx, %r8 ; 字符串长度 cmpq $15, %r8 ja .L10 ; 长度 > 15 → 走堆分配 ... ; ≤15B：直接用对象内部的 16B 缓冲（SSO），零分配 ret .L10: call _M_create(...) ; 超长 → 堆分配 ... call memcpy ; 复制进新缓冲

vector::operator[] —— 基址 + 下标 × 4，一条指令：

v_get(vector<int> const&, size_t): movq (%rcx), %rax ; 第一个成员 = data 指针 movl (%rax,%rdx,4), %eax ; data[i]：连续存储的直接寻址 ret

vector 扩容（push_back 满时的展开）：

... call _Znwy ; 分配新容量（旧容量 × 2） ... call memcpy ; 把旧元素整体搬过去 call _ZdlPvy ; 释放旧缓冲

环境备注：本集在 x86-64 Windows + MinGW g++ 15.2.0（libstdc++）实测。libstdc++ 的 SSO 阈值是 15 字节、对象 32 字节；MSVC 的 STL 是 16 字节阈值，数字略有差异，机制一致。

③ 为什么这么设计

• vector= 三个指针（begin/end/capacity）→ 24 字节。元素连续存放（operator[]是"基址 + 下标"直接寻址，一条指令），所以迭代快、缓存友好——这也是它比list快得多的根本原因。
• 扩容 2 倍：让"插入"的均摊成本是 O(1)。每次"满"时分配 2 倍新缓冲、把旧元素搬过去、释放旧的。代价是：搬动时所有元素地址都变了（迭代器全部失效），且大对象搬动成本高——此时移动语义（见 E12）就是救命稻草。
• string 的 SSO（短字符串优化）：libstdc++ 里 15 字节以内直接存在对象内部的 16 字节缓冲里，完全不碰堆。只有超过 15B 才_M_create堆分配。cmpq $15, %r8就是这条分界线——"短字符串免费"是真的。
• 为什么 string 占 32 字节：对象里要塞下 16B 内部缓冲 + 大小 + 容量 + 指向缓冲的指针，32 字节刚好装下整套状态。

④ 深入一：vector 的三个指针到底是什么

std::vector<T>的内部（libstdc++ 实现）通常是这样：

偏移 0 T* _M_start （begin：首元素地址） 偏移 8 T* _M_finish （end：最后一个元素之后） 偏移 16 T* _M_end_of_storage（capacity：缓冲区末尾）

• size()=end - begin（指针相减，一条指令）；
• capacity()=end_of_storage - begin；
• operator[]=begin[i]（基址寻址，本集汇编已见）；
• 全部操作都是指针算术，没有遍历——这就是 vector"轻"的原因：24 字节，任何时刻都知道首尾和容量。

对比std::list<T>：list 每个节点独立分配、存前后指针，sizeof(list)也约 24 字节（首尾 + 哨兵），但访问要沿链走、缓存不友好。vector 的连续存储是"缓存友好"的机器基础。

⑤ 深入二：扩容的"均摊 O(1)"数学

为什么 2 倍扩容让 push_back 均摊 O(1)？

• 每次扩容：分配 2 倍大小，搬移旧元素。设最终容量为 N，则搬移成本总和 ≈ N/2 + N/4 + N/8 + … < N；
• 所以 N 次 push_back 的总成本 ≈ 2N（每次 push 本体 + 摊到每次的搬移），均摊 O(1)；
• 若按"每次 +1"扩容，总成本 O(N²)——灾难。

工程含义：知道规模就reserve，把"分配+搬移"从 N 次摊平变成 0~1 次。这也是"性能敏感代码先 reserve"的数学理由。

⑥ 深入三：SSO 的完整机制

libstdc++ 的std::string32 字节布局大致是：

偏移 0 union { char _M_local_buf[16]; char* _M_data; } ← 短串用内部缓冲 / 长串用指针 偏移 16 size_t _M_string_length （当前长度） 偏移 24 union { size_t _M_capacity; ... } （容量 / 短串标记）

• 短串（≤15B）：数据放内部_M_local_buf，_M_data指向自己内部（data = obj + 16，实测 delta=16 就是证据）；
• 长串：_M_data指向堆缓冲；
• 切换逻辑就是本集cmpq $15, %r8; ja 堆分配这一条比较；
• 代价：string 对象变大（32 字节 vs 可能更小的实现），换来"大多数短字符串零堆分配"。

SSO 的意义：绝大多数实际字符串都很短（路径、键、名字），SSO 让它们完全不碰堆——这在"大量字符串"场景（容器、map 键）里是巨大的性能红利。这也是"为什么 string 32 字节还划算"的原因。

⑦ 常见误区

• 误区 1：“vector扩容会拷贝所有元素，很慢”：扩容频率低（2 倍），均摊 O(1)；且 C++11 起优先移动（noexcept 时）。真正要避免的是"频繁小扩容"——reserve解决。
• 误区 2：“string总是堆分配”：短串 SSO 零分配。只有超过 SSO 阈值才堆分配。
• 误区 3：“vector和数组差不多，list更灵活”：list的"灵活"（任意插入 O(1)）换来节点分散、缓存差、无随机访问。99% 场景vector更快。
• 误区 4：“reserve和resize一样”：reserve只扩容量不构造元素（size 不变）；resize构造/销毁元素改变 size。用错会多构造或越界。
• 误区 5：“operator[]会检查越界”：不检查（快速）。at()才检查（抛异常，E10 讲过）。想安全用at()，想快用operator[]。
• 误区 6：“vector的size()是 O(1) 遍历计数”：size()就是end - begin一次指针相减（本集 ④ 讲过），O(1) 且常被优化成寄存器差，零成本。
• 误区 7：“std::map一定比unordered_map慢”：不一定。数据量小/键是小整数时，红黑树的 log n 和缓存行为可能反而胜过哈希的"哈希计算 + 桶冲突 + 链遍历"。选型要实测，别只看复杂度记号。
• 误区 8：“std::vector存不下就是容量不够”：还可能抛std::bad_alloc（分配失败）或触发移动/拷贝异常。处理大容器时记得 try/catchbad_alloc，或预估内存。
• 误区 9：“std::string的+=一定比+快”：s += t若容量够就地追加（零分配）；s + t总是构造新 string（分配）。但两者若触发重新分配就都慢。用reserve规划容量最稳。
• 误区 10：“std::array和vector性能一样”：访问都 O(1)、缓存友好。但array是栈/内嵌（无堆分配、构造零），vector是堆（构造要分配）。array通常更轻，但大小编译期固定。
• 误区 11：“容器都适合多线程并发使用”：标准容器非线程安全——两个线程同时改同一 vector/map 是数据竞争（UB，E16 会讲）。要么加锁，要么用并发专用容器（TBB/并发 queue 等）。
• 误区 12：“vector的元素一定在堆上”：元素在"vector 自己的缓冲区"里，缓冲区由_M_start指向（堆分配）。但std::array/局部数组在栈上。别把"vector"与"栈/堆"直接划等号。

⑧ 实战启示

1. 知道要装多少就reserve：避免反复"扩容 → 搬移 → 释放"，每次都是分配 + 复制 + 释放。
2. 不要长期保存 vector 的迭代器/裸指针：扩容后全部失效（下一集 E15 展开）。
3. 大量小字符串用string很划算（SSO 不堆分配）；但"字符串集合"别用vector<string>反复拷贝，考虑string_view、合并缓冲。
4. 按使用方式选容器：vector连续 = 缓存友好，适合随机访问/尾插；map是红黑树 = 节点分散、O(log n) 查找；unordered_map是哈希表 = 期望 O(1) 但更占内存、无序遍历。先想"怎么用"，再选容器。
5. 大对象容器用vector<unique_ptr<T>>：搬动只搬指针（8 字节），避免大对象整体搬移（E13 讲过）。

⑨ 扩展专题一：vector 与缓存友好——为什么"连续"这么值钱

E21 会专门讲性能，这里先铺垫：vector的"连续存储"是它碾压list的根本原因，因为CPU 缓存按缓存行（64B）加载：

• 遍历vector<int>：顺序访问，每个缓存行命中 16 个 int（64B/4B），几乎全命中；
• 遍历list<int>：每个节点散落在堆上（节点 = 前后指针 + int，约 24B），每次访问大概率新缓存行 + 未命中惩罚；
• 实测：遍历 vector 通常比 list 快一个数量级（几十倍），即使操作数相同。

机器理由：缓存是"空间局部性"的游戏。vector天然按顺序排布，list天然打散。所以"能连续就连续"不只是风格，是让 CPU 少跑内存的硬道理。

⑩ 扩展专题二：string_view 为什么"免费"

std::string_view是一个"只读字符串的窗口"：

voidlog(std::string_view sv){fwrite(sv.data(),1,sv.size(),stderr);}

• 内部只有两个指针/一个指针+长度（16 字节），不拥有数据、不拷贝、不分配；
• 传入std::string/const char*/ 子串都零拷贝；
• 代价：view 不保证数据生命周期——被 view 的字符串销毁后 view 悬垂（和"引用比拷贝快但危险"同理）。

对比：log(const std::string&)若临时构造 string 可能触发拷贝+分配；string_view直接读原数据。这就是"避免多余拷贝"的又一招——但它要求调用方保证数据存活。

⑪ 扩展 FAQ

• Q：vector的data()返回什么？
  A：首元素指针（_M_start），可当数组用（&v[0]）。空 vector 时可能返回空/未指定，别解引用。
• Q：shrink_to_fit一定缩容吗？
  A：非强制（实现可能忽略）。它尝试把 capacity 缩到 size，但可能仍有对齐/实现保留。
• Q：unordered_map为什么"更占内存"？
  A：哈希表要桶数组 + 节点 + 负载因子预留空间，通常比map红黑树更费内存；且迭代无序。换来期望 O(1) 查找。
• Q：deque是连续的吗？
  A：分块连续（块内连续、块间链接）。支持两端插入 O(1)，operator[]O(1)，但缓存友好度略逊 vector，迭代器结构复杂。
• Q：std::array和vector区别？
  A：array是固定大小的栈/内嵌数组（无堆分配、size 编译期定），vector是动态堆数组。能用array就用（零分配）。

⑫ 扩展实验

1. 跑容量序列：运行 demo 看 push_back 的容量变化（1/2/4/8/…/128），复现"2 倍扩容"。
2. SSO 分界：构造 14/15/16/17 字节字符串，观察data()地址与对象地址的 delta（≤15 在内部、>15 在堆）。
3. vector 布局：打印sizeof(vector<int>)=24 与三个成员的相对偏移（&v与&v[0]）。
4. reserve 前后对比：push_back1 万次，对比有/无reserve的耗时与分配次数。
5. at 与 operator[]：越界访问对比反汇编，确认at有检查、operator[]没有。

⑭ 扩展专题三：vector 扩容与移动语义的配合（E12 落地）

E12 讲过"vector 扩容依赖 noexcept 移动"，现在看完整机制：

1. push_back满时：新容量 = 旧 × 2，_Znwy分配新缓冲；
2. 搬移旧元素：若元素可移动且 noexcept→ 逐个移动构造（偷指针，快）；否则 → 拷贝构造（可能分配，慢）；
3. 旧元素析构 + 旧缓冲_ZdlPvy释放；
4. 更新三个指针（_M_start/_M_finish/_M_end_of_storage）。

对vector<std::string>扩容：每个 string 若超过 SSO，移动只"偷指针 + 置空"——比拷贝（分配 + memcpy 内容）便宜得多。这就是"给移动构造标 noexcept"让 vector 敢用移动的直接回报。

一个反直觉点：vector扩容失败（bad_alloc）时，已搬元素已离开旧缓冲——标准用"移动"时不能保证强异常安全，所以noexcept移动才被允许。这就是为什么"可能抛的移动会让 vector 回退拷贝"。

⑮ 扩展专题四：容器选型决策树

从"怎么用"出发选容器：

需要随机访问（[] / at）? ├─ 需要动态大小 → vector（默认首选） └─ 大小固定 → std::array 需要频繁头尾插删? ├─ 只尾插/尾删 → vector / deque └─ 头尾都要 → deque（分块连续） 需要按 key 查找? ├─ 有序 → std::map（红黑树，O(log n)） └─ 无序/更快 → std::unordered_map（哈希，期望 O(1)，更费内存） 需要有序唯一集合 → std::set / std::unordered_set 需要先进先出 → std::queue（deque 适配） 需要小数据集 → vector 线性扫描即可（缓存赢过 log n）

一句话：不知道选什么就vector。它连续、缓存友好、均摊 O(1) 尾插，是绝大多数场景的最优解；只有明确"随机访问不需要/有序键查找/头插为主"才换其他容器。

⑯ 扩展 FAQ（第二轮）

• Q：vector<bool>是什么？
  A：特化版本，按位存储（不是 bool 数组）——省内存但元素是"代理对象"，operator[]返回代理而非 bool&，可能有意外的性能/语义坑。别默认用，需要位集考虑std::bitset。
• Q：emplace_back和push_back区别？
  A：emplace_back(args...)在容器内就地构造（省一次临时对象构造+移动）；push_back(x)先构造 x 再移动/拷贝进容器。能用emplace_back尽量用（配合 E11/E12 的零临时对象思想）。
• Q：string的c_str()是 O(1) 吗？
  A：是，c_str()返回内部_M_data（含结尾\0）；长串是堆指针、短串是内部缓冲指针。别长期持有它（后续修改字符串会失效）。
• Q：vector能用std::initializer_list构造吗？
  A：能（vector<int> v{1,2,3}），它会先放临时数组再拷/移入——小列表无所谓，大列表注意两次拷贝。
• Q：std::span和string_view关系？
  A：span<T>是"任意连续序列的窗口"（C++20），string_view是其 char 特化。都是"不拥有、零拷贝、要保证生命周期"。

⑰ 扩展实验（第二轮）

1. emplace vs push_back：vector<std::string>用emplace_back(10,'x')与push_back(std::string(10,'x'))，反汇编对比临时对象构造次数。
2. 扩容搬移类型：vector<BigNoexcept>vsvector<BigThrowy>扩容，看反汇编是移动还是拷贝（E12 讲过 noexcept 开关）。
3. vector 坑：auto b = vb[0];看类型是std::_Bit_reference而非bool，体验代理对象的怪异。
4. string_view 生命周期：返回局部 string 的 view，运行（可能 UB）看悬垂——理解"view 不拥有"。
5. 容器性能对比：随机访问 + 遍历，vector vs list vs map vs unordered_map，计时对比数量级。

⑲ 扩展专题五：unordered_map 的"期望 O(1)"是怎么实现的

std::unordered_map是哈希表（链地址法），内部大致：

桶数组（bucket array，vector 形态） 桶 0 → 节点链（红黑树不用，这里用单向/双向链表） 桶 1 → ... 桶 N → ... 节点：{ key, value, 下一个节点指针 }

• find(key)：算哈希 → 定位桶 → 沿链比较 key → 命中/未命中；
• 期望 O(1)：负载因子低时桶里链很短（通常 <1 时平均每桶不到 1 个节点）；
• 最坏 O(n)：所有 key 撞进同一桶（差哈希函数/被攻击）。
• 代价：桶数组 + 节点分散（缓存不友好）+ 无序遍历 + 内存比 map 大。

汇编层面：find= 哈希计算（几条乘/移位）+ 桶定位（数组索引）+ 链遍历比较（循环）。对比map的红黑树（沿树指针下降，log n 步）。哈希通常更快，但"顺序性"和"稳定性"不如树。

⑳ 扩展专题六：map 的红黑树节点长什么样

std::map<K,V>是红黑树（自平衡二叉搜索树），节点：

{ color(红/黑), left, right, parent, key, value }

• 插入/删除/查找都是 O(log n)：沿树下降比较 key；
• 节点各自分配（不连续）→ 遍历缓存不友好（对比 vector 的连续）;
• operator[]（不存在就插入）依赖"查找 + 插入"，可能触发再平衡（变色 + 旋转）；
• 为什么有序：中序遍历给出升序（begin到end就是排序好的）。

选型：需要"按序访问/区间查询"→map；只求"按 key 快速取"→unordered_map。两者内部结构（树 vs 哈希表）决定了它们的性能画像——这正是本集"容器 = 数据结构 + 内存布局"的落地。

㉑ 扩展 FAQ（第三轮）

• Q：std::deque的operator[]真的 O(1) 吗？
  A：是（分块映射：块指针数组 + 块内索引，两次间接），但比 vector 的"一条指令"慢，且迭代器更复杂。
• Q：vector插入中间为什么贵？
  A：要挪动后面所有元素（O(n) 移动）。insert在中间 = 搬移尾段 + 构造新元素。头插最贵，尾插最便宜。
• Q：std::string拼接+快吗？
  A：a + b会创建新 string（分配 + 拷贝）。连续+=若容量够则就地（快）；反复+可能反复分配——用reserve或append。
• Q：std::list什么时候值得用？
  A：需要"O(1) 在任意位置插入/删除且迭代器稳定"（如 LRU 缓存、中间插删频繁）。否则 vector 更快。
• Q：容器的迭代器为什么"浅拷贝很安全"？
  A：迭代器通常是"指针/指针对"，拷贝就是复制指针，无所有权——但"失效规则"由容器结构决定（vector 扩容全失效、list/map 插入不失效）。
• Q：std::vector能存引用吗？
  A：不能（引用不是对象，无法按值存放）。存std::reference_wrapper<T>或指针。这也是"vector 存智能指针"而非引用的原因。
• Q：std::string的substr会拷贝吗？
  A：substr返回新 string（拷贝子串）。想零拷贝看子串用string_view（E14 ⑩ 讲过）。
• Q：为什么vector::insert在首部最慢？
  A：首插要搬移全部已有元素（O(n)）；尾插搬移 0 个（O(1) 均摊）。需要头插请用deque或list。
• Q：std::vector的swap是 O(1) 吗？
  A：是，只交换三个指针（swap或vector::swap）。比"拷贝所有元素"快得多——这也是"用 swap 实现强异常安全"（copy-and-swap）的机器基础。
• Q：为什么vector不设默认初始容量大点？
  A：省内存（小 vector 不浪费）。用reserve显式指定即可。默认"按需扩容"是最省内存的起点。
• Q：std::string和std::vector<char>选哪个？
  A：文本用 string（有 SSO、c_str、编码辅助）；二进制缓冲区用 vector（或std::byte）。string 的 SSO 对短文本是显著优势。
• Q：vector元素地址会变，那std::reference_wrapper呢？
  A：reference_wrapper存的是地址，vector 扩容后地址变了，wrapper 指向旧地址 → 悬垂。稳定地址要么用 list/map，要么存索引。

㉒ 扩展实验（第三轮）

1. 哈希 vs 树：同量级数据，unordered_map与map插入/查找计时，观察差距与内存占用。
2. list vs vector 遍历：遍历 100 万元素，实测 list 慢多少倍（缓存局部性的直观证明）。
3. string 拼接方式：+、+=（预 reserve）、append三种拼接 10 万次，对比分配次数/耗时。
4. vector 中间插入：往 vector 中间插入 1 万次 vs 尾插，计时对比 O(n) 搬移成本。
5. deque vs vector 头插：头插 10 万次，deque O(1) vs vector O(n)，计时对比。

㉓ 悬念

既然 vector 扩容会让所有地址搬家，那"迭代器"这种"指向容器内部"的东西，到底什么时候会失效？range-for为什么被叫"最安全"的遍历？