一、std::string

1. 本质

• 是 std::basic_string<char> 的特化，专门管理字符序列。

• 行为极像 vector<char>，但增加了大量字符串专属操作（查找、子串、拼接、比较、c_str等）。

2. 内部实现

• 连续内存存储字符，尾部有 '\0' 保证 c_str() 兼容C风格字符串。

• 通常采用小字符串优化（SSO）：短字符串直接存在对象内部，避免堆分配。

• 动态扩容类似 vector（1.5倍或2倍增长）。

3. 常用操作

操作	说明
s.length() / s.size()	字符数（不含\0）
s.c_str()	返回C风格字符串
s.substr(pos, count)	子串
s.find(str)	查找
s.append(str) / +=	追加
s.insert(pos, str)	插入
s.erase(pos, len)	删除
s.replace(pos, len, str)	替换

4. 特点

• 专为字符串设计，重载了 +、==、< 等运算符。

• 有输入输出流操作 >>, <<, getline。

• 支持数字转换：to_string, stoi, stod 等。

---

二、std::vector

1. 本质

• 动态数组，可随机访问任何元素，容量可自动增长。

• 元素存储在一段连续内存上。

2. 内部实现

• 三指针结构：start, finish, end_of_storage。

• 插入元素时如果容量不足，会重新分配一块更大的内存，将原元素拷贝/移动过去，并释放旧内存。

• 扩容因子通常为 2 或 1.5。

3. 常用操作

操作	说明
v.size()	元素个数
v.capacity()	当前分配内存能容纳的元素数
v.push_back(x)	尾插
v.emplace_back(args...)	尾部就地构造
v.pop_back()	尾删
v.insert(it, x)	任意位置插入，可能引起元素整体后移
v.erase(it)	任意位置删除，可能引起元素整体前移
v.clear()	清空（size=0，capacity不变）
v.shrink_to_fit()	释放多余容量
v.reserve(n)	预留容量，避免反复分配

4. 特点

• 随机访问 O(1)，通过 [] 或 at()。

• 尾插/尾删均摊 O(1)。

• 头插/中间插入/删除 O(n)，因为需要移动元素。

• 扩容会导致所有迭代器、指针、引用失效。

• 内存连续，缓存友好。

---

三、std::deque（双端队列）

1. 本质

• 双端队列，支持在头部和尾部高效插入/删除。

• 不是连续一整块内存，而是分段连续：多个定长数组通过指针数组（中枢控制块）连在一起。

2. 内部实现

• 有一个“中控器”数组存储指向各段缓冲区的指针。

• 每段缓冲区大小固定（如 512 字节或若干元素）。

• 首尾插入时，若当前缓冲区满，则分配新缓冲区并加入中控器，无需移动原有元素。

• 支持随机访问，但需要两级间接寻址（计算所在块 + 块内偏移）。

3. 常用操作

操作	说明
d.push_back(x) / emplace_back	尾插，均摊O(1)
d.push_front(x) / emplace_front	头插，均摊O(1)
d.pop_back() / pop_front()	尾/头删除，O(1)
d.insert(it, x)	任意位置插入，O(n)（但如果靠近两端，移动元素较少）
d.erase(it)	任意位置删除，O(n)
d[n] / d.at(n)	随机访问，O(1)（比vector稍慢）

4. 特点

• 首尾插入/删除非常快，不会引起大段元素移动。

• 任意位置插入/删除仍可能移动元素（选择移动较少的一端）。

• 扩容时：中控器可能重新分配，但元素本身所在的缓冲区不移动，因此元素的指针和引用不会失效（但迭代器可能会失效）。

• 与 vector 比，随机访问略慢，内存开销更大（多一级中控结构）。

• 默认不提供 reserve/capacity 概念（或者说没有连续的 capacity 保障），但可调 shrink_to_fit。

---

四、三者的核心对比

特性	string	vector	deque
存储内容	字符	任意类型 T	任意类型 T
内存布局	连续（含末尾\0）	严格连续	分段连续
头插/头删效率	O(n)	O(n)	O(1)
尾插/尾删效率	O(1) 均摊	O(1) 均摊	O(1) 均摊
中间插入/删除	O(n)	O(n)	O(n) （但可优化到移动少的一侧）
随机访问	O(1)	O(1)	O(1)（略慢，需两次间接寻址）
扩容时元素移动	整体迁移	整体迁移	不移动原有元素（只可能移动中控指针）
扩容迭代器/指针/引用失效	全部失效	全部失效	引用和指针不失效，迭代器可能失效
SSO 优化	有	无	无
专属功能	丰富字符串处理	通用动态数组	双端快速操作
reserve / capacity	支持	支持	无（实现可能提供，但非标准保障）
典型使用场景	字符串处理	需要连续内存、顺序存储、高效尾操作的场合	需要在两端频繁插入删除、又需随机访问的场合（如任务队列）