Skip to content

C++ STL ​


一、STL 整体概念 ​

1. 六大组件 ​

Q: STL 由哪六大组件构成?

组件作用典型代表
容器存储数据vector, list, map, set
算法处理数据sort, find, for_each
迭代器连接容器与算法的桥梁begin(), end()
适配器改造接口stack, queue, priority_queue
仿函数像函数一样被调用的对象less<T>, greater<T>
空间配置器管理内存分配/释放allocator<T>

2. 核心设计思想 ​

Q: STL 的核心设计思想是什么?

思想说明
算法与容器分离算法通过迭代器访问容器,不直接依赖具体容器类型
迭代器 = 粘合剂vector 的迭代器是原生指针,list/map 的迭代器是封装的类对象
泛型编程模板使得同一套代码可以作用于不同数据类型

二、序列容器 ​

1. vector(最高频考点) ​

(1) 底层结构 ​

Q: vector 的底层是怎么实现的?

连续内存数组,由三个指针管理:

指针含义关系
_start起始地址—
_finish有效元素末尾_finish - _start = size()
_end_of_storage容量末尾_end_of_storage - _start = capacity()
cpp
// vector 内存布局示意
// [_start ........ _finish ........ _end_of_storage]
//  |<- size() ->|                  |
//  |<------- capacity() ---------->|

(2) 为什么 vector 高效? ​

原因说明
连续内存CPU 缓存友好,相邻元素被预取到缓存,缓存命中率接近 100%
随机访问 O(1)v[i] 等价于 *(start + i),一次指针运算 + 一次解引用
尾部操作摊还 O(1)偶尔扩容 O(n),但均摊下来每次 push_back 仍是常数时间

(3) 扩容机制(必考) ​

Q: vector 的扩容过程是怎样的?增长因子是多少?

触发条件:当 size() == capacity() 时,下次插入触发扩容。

扩容过程:

  1. 分配一块更大的新连续内存(大小 = 旧容量 × 增长因子)
  2. 将旧元素移动(若移动构造为 noexcept)或拷贝到新内存
  3. 析构旧内存中的元素
  4. 释放旧内存
  5. 更新三个内部指针

增长因子:

编译器增长因子
GCC / Clang (Linux)2 倍
MSVC (Windows)1.5 倍

Q: 为什么 MSVC 选 1.5 倍而不是 2 倍?

关键在于内存复用。假设容量从 1 开始:

  • 2 倍:1→2→4→8→16→32→64…,之前释放的所有内存加起来永远小于下一次需要的,旧块无法复用 → 内存碎片
  • 1.5 倍:1→2→3→4→6→9→14→21→31→47…,大约第 6 次后,之前释放的内存块之和已超过下一次需求,malloc 可直接复用

数学上,当增长因子 **< φ(黄金比例 ≈ 1.618)**时,之前释放的内存可以被复用。


(4) reserve vs resize ​

Q: reserve 和 resize 的区别?

reserve(n)resize(n)
改变 size()?否是(新增元素值初始化)
改变 capacity()?若 n > capacity 才会若 n > capacity 才会
会构造元素吗?否是,新元素用默认构造
使用场景预分配,避免反复扩容真正改变元素个数
cpp
vector<int> v;
v.reserve(1000);  // capacity = 1000, size = 0
v.resize(500);     // size = 500, 新增 500 个 0

(5) push_back vs emplace_back ​

Q: push_back 和 emplace_back 的区别?

方式构造过程性能
push_back(x)先构造临时对象 → 拷贝/移动到容器多一次构造 + 析构
emplace_back(args...)在容器末尾就地构造,参数完美转发零拷贝
cpp
struct Point { int x, y; Point(int a, int b) : x(a), y(b) {} };

vector<Point> v;
v.push_back(Point(1, 2));   // 构造临时对象 + 移动
v.emplace_back(1, 2);        // 直接构造,无临时对象

(6) 迭代器失效(必问核心) ​

Q: vector 什么时候迭代器失效?

操作失效范围
push_back / emplace_back 触发扩容全部迭代器、指针、引用
push_back / emplace_back 不扩容仅 end() 失效
insert(触发扩容)全部迭代器
insert(不扩容)插入点及之后的所有迭代器
erase删除点及之后的所有迭代器
clear()全部失效
reserve / resize 导致扩容全部失效

记忆口诀:扩容 = 全死;中间插入/删除 = 当前位置及后面都死。


(7) 安全删除元素 ​

cpp
// ❌ 错误:迭代器失效!
for (auto it = v.begin(); it != v.end(); ++it) {
    if (condition(*it)) v.erase(it);  // it 已失效,++it 是 UB
}

// ✅ 方式一:用 erase 返回值
for (auto it = v.begin(); it != v.end(); ) {
    if (condition(*it))
        it = v.erase(it);     // erase 返回下一个有效迭代器
    else
        ++it;
}

// ✅ 方式二:Erase-Remove 惯用法(推荐)
v.erase(std::remove_if(v.begin(), v.end(), condition), v.end());

(8) clear 不会释放内存 ​

Q: clear() 会释放内存吗?

**不会!**只析构元素、置 size = 0,capacity 不变。

cpp
vector<int> v(1000000);
v.clear();                  // size = 0,但 capacity 仍为 1000000!
v.shrink_to_fit();          // 请求释放多余容量(非强制)

// 强制释放:与空 vector 交换
vector<int>().swap(v);      // 临时对象析构时带走旧内存

(9) vector<bool> 的陷阱 ​

Q: vector<bool> 有什么问题?

vector<bool> 是特化版本,每个 bool 只用 1 bit,导致:

  • v[0] 返回的不是 bool&,而是代理对象 vector<bool>::reference
  • 不能取地址:&v[0] 编译错误

建议:用 vector<char>、deque<bool> 或 bitset 替代。


2. list ​

(1) 底层结构 ​

双向循环链表,每个节点包含:数据 + prev 指针 + next 指针。64 位系统下每节点额外开销 16 字节。


(2) 核心特性 ​

特性说明
插入/删除任意位置 O(1)(已知迭代器位置)
随机访问❌ 不支持 l[i]
迭代器安全插入不影响任何迭代器,删除仅被删节点失效
spliceO(1) 将另一个 list 的整段节点嫁接过来

(3) 为什么 list 不能用 std::sort? ​

Q: 为什么 list 不能用 std::sort?

std::sort 要求随机访问迭代器,list 只提供双向迭代器(不支持 it + n)。应使用 list::sort(),内部通常使用归并排序。


(4) vector vs list(经典对比) ​

Q: vector 和 list 的区别?什么时候用哪个?(高频)

维度vectorlist
内存结构连续数组分散的链表节点
随机访问O(1)O(n)
尾部插入/删除摊还 O(1)O(1)
中间插入/删除O(n)(移动元素)O(1)
缓存命中率极高极低(每次解引用都可能 Cache Miss)
迭代器安全扩容/插入/删除都可能失效插入不影响,删除仅被删节点失效
内存额外开销几乎为零每节点两个指针(64 位下 16 字节)

经验法则:能用 vector 就不要用 list。现代 CPU 缓存层级下,连续内存的优势碾压一切。


3. deque ​

(1) 底层结构 ​

Q: deque 的底层是怎么实现的?

分段连续内存 + 中控数组(map of buffers):

  • 中控数组是一段连续内存,存储指向多个固定大小缓冲区的指针
  • 每个缓冲区大小固定(通常 512 或 4096 字节,取决于元素类型)
[buffer0] [buffer1] [buffer2] [buffer3] [buffer4]
     ↑         ↑         ↑         ↑        ↑
     └─────────┴──── map 数组  ────┴─────────┘

(2) 设计优势 ​

特性说明
头/尾插入 O(1)在两端分配新 buffer,不移动已有元素
支持随机访问两次间接寻址(查 map → 查 buffer)
扩容不移动已有元素核心优势:元素地址稳定
随机访问比 vector 慢需要两次寻址

(3) deque 迭代器 ​

deque 的迭代器是智能迭代器,包含四个指针:

指针含义
cur当前元素位置
first当前 buffer 起始
last当前 buffer 末尾
node指向中控数组中对应项

(4) 为什么 stack/queue 默认用 deque? ​

Q: 为什么 stack 和 queue 默认用 deque 而不是 vector?

原因说明
扩容不移动已有元素引用/指针不失效
可动态释放 buffervector 的 capacity 只增不减
头尾操作更高效两端都 O(1)

4. string ​

Q: std::string 的底层和常用优化?

  • 底层:连续内存(字符数组),类似 vector<char>
  • 现代 std::string 采用深拷贝(旧版 COW 已在 C++11 废弃)
  • c_str() 返回 const char*,保证以 \0 结尾
  • substr() 是 O(n),返回新 string(会分配内存)
  • data() 返回底层指针(C++17 起非 const 版本可修改)
cpp
// 优化:预分配 + 链式 append
string s;
s.reserve(1024);
s.append(s1).append(s2).append(s3);   // 避免多次临时对象

string_view(C++17):非拥有、只读的字符串视图,函数参数首选。

cpp
void process(std::string_view sv) {
    if (sv.starts_with("http")) { ... }
}
process("hello");            // 零开销,无需构造临时 string

注意:string_view 不拥有数据,不要返回局部变量的 string_view(悬垂引用)。


三、关联容器 ​

1. map / set(红黑树) ​

(1) 底层结构 ​

Q: map 和 set 的底层是什么?红黑树有什么性质?(高频)

底层是红黑树——一种自平衡二叉搜索树。元素按 key 自动排序(默认升序)。

红黑树五大性质:

#性质
1每个节点是红色或黑色
2根节点必须是黑色
3所有叶子节点(NIL) 为黑色
4红色节点的两个子节点必须都是黑色(不连红)
5从任意节点到其每个叶子节点的路径上,黑色节点数量相同

性质 4 + 5 保证 "最长路径 ≤ 2 × 最短路径",实现弱平衡。


(2) 红黑树 vs AVL 树 ​

Q: STL 为什么用红黑树而不用 AVL 树?(高频)

维度红黑树AVL 树
平衡要求弱平衡(最长 ≤ 2× 最短)严格平衡(高度差 ≤ 1)
插入/删除旋转少,O(1) 摊还多,O(log n)
查找速度O(log n),稍慢O(log n),稍快
额外空间1 bit(颜色)需存高度差
适用场景增删频繁查询频繁

STL 设计者认为实际工程中插入/删除同样频繁,红黑树综合性能更优。


(3) 核心特性 ​

  • 查找/插入/删除 O(log n)
  • 迭代器遍历是中序遍历,结果有序
  • 不能修改 key(会破坏红黑树结构)
  • set 的 value 也不能修改(value 就是 key)

(4) map vs set(高频对比) ​

Q: map 和 set 有什么区别?(高频)

维度mapset
存储内容键值对 pair<const K, V>仅单一 key(元素本身就是 key)
用途通过 key 关联/存储一个 value判断"元素是否存在"(去重 / 集合)
底层结构红黑树红黑树(完全相同)
查找find 返回 pair 迭代器,it->second 取值find 返回元素迭代器,*it 即元素
修改key 不可改,value 可改元素不可改(value 就是 key,改了破坏红黑树)
operator[]✅ m[k](key 不存在时自动插入)❌ 没有
内存占用节点多存一个 value节点只存 key,更省内存
重复元素key 唯一(multimap 可重复)元素唯一(multiset 可重复)
典型场景字典、计数、ID→对象映射去重、集合运算、存在性判断
cpp
map<string, int> m;      // 存键值对
m["a"] = 1;              // 通过 key 关联 value

set<int> s = {3, 1, 2};
s.insert(3);             // 已存在,插入无效 → 常用于去重

// 集合运算(手写题常见)
std::vector<int> v;
std::set_intersection(s1.begin(), s1.end(),
                      s2.begin(), s2.end(), back_inserter(v));

记忆点:set 可以看作"只要 key 的 map"。二者底层同为红黑树,查找/插入/删除复杂度相同(O(log n))。


(5) operator[] vs insert vs at vs find ​

Q: map 的 operator[] 有什么陷阱?

方式key 不存在时key 存在时const map 可用?
m[k]自动插入默认值返回引用❌
m.at(k)抛出 std::out_of_range返回引用✅
m.insert({k,v})插入,返回 pair不修改✅
m.find(k)返回 end()返回迭代器✅

常见陷阱:operator[] 会在 key 不存在时静默插入!

cpp
// ❌ 只想检查,却意外插入了
if (m[key] == 0) { ... }      // 如果 key 不存在,会插入 {key, 0}

// ✅ 正确
if (m.find(key) != m.end()) { ... }
// C++20
if (m.contains(key)) { ... }

(6) multimap / multiset ​

  • 允许重复 key
  • 没有 operator[](不知道该返回哪个值)
  • equal_range(k) 返回 key 对应的一组值的迭代器区间

2. unordered_map / unordered_set(哈希表) ​

(1) 底层结构 ​

Q: unordered_map 的底层是什么?

链地址法(Separate Chaining)哈希表:

  • 桶数组:连续内存,每个桶指向一个链表头
  • 节点:包含 key、value、缓存的 hash 值(避免 rehash 时重复计算)、next 指针
  • 哈希函数:std::hash<Key> 将 key 映射为 size_t
  • 相等判断:std::equal_to<Key>(默认 operator==)

(2) 负载因子与 Rehash ​

概念说明
负载因子size() / bucket_count()
触发 rehash当 load_factor > max_load_factor()(默认 1.0)
rehash 过程分配新桶数组 → 逐个重新计算哈希迁移 → O(n)
rehash 后果所有迭代器失效
cpp
unordered_map<int, string> um;
um.reserve(10000);   // 预分配桶数量,避免频繁 rehash

(3) map vs unordered_map(必问) ​

Q: map 和 unordered_map 的区别?怎么选?(高频)

维度mapunordered_map
底层红黑树哈希表
有序性有序(自动排序)无序
查找/插入/删除O(log n)(稳定)平均 O(1),最坏 O(n)
内存占用存父子指针 + 颜色哈希桶 + 链表指针 + 缓存 hash
迭代器安全erase 仅被删节点失效rehash 时全部失效
key 要求支持 <需要 hash 函数 + ==
遍历有序(中序)无序(按桶序)
范围查询✅ lower_bound❌

选型决策:

  • 需要有序遍历 / 范围查询 → map
  • 追求查询速度 → unordered_map
  • 不确定时用 unordered_map,大部分场景查找频率远高于遍历频率

(4) 自定义类型作为 key ​

unordered_map 需要:

  1. 哈希函数:特化 std::hash 或提供自定义仿函数
  2. 相等比较:operator== 或自定义仿函数
cpp
struct Person {
    string name;
    int id;
    bool operator==(const Person& o) const {
        return name == o.name && id == o.id;
    }
};

struct PersonHash {
    size_t operator()(const Person& p) const {
        return hash<string>{}(p.name) ^ (hash<int>{}(p.id) << 1);
    }
};

unordered_map<Person, int, PersonHash> um;

(5) 哈希冲突解决方法 ​

方法说明使用情况
链地址法冲突元素挂链表STL unordered_map 采用
开放地址法冲突时找下一个空位谷歌 dense_hash_map 等
再哈希法用第二个哈希函数较少单独使用

(6) 实战:线程池中为什么用 unordered_map 存储线程? ​

线程池项目中,工作线程存储在 std::unordered_map<int, std::unique_ptr<Thread>> 中,选型理由如下:

方案问题
vector<Thread>Thread 含 std::thread 成员,不可拷贝;vector 扩容时会移动元素 → 线程绑定的 this 指针失效 → 崩溃
vector<Thread*>扩容时移动指针(8字节)是安全的,但查线程需要 O(n) 遍历
vector<unique_ptr<Thread>>同原生指针,但自动管理内存;查找仍然 O(n)
unordered_map<int, unique_ptr<Thread>>O(1) 精确查找 + 自动内存管理 + 方便动态删除

关键需求:Cached 模式下,需要根据线程 ID 频繁回收空闲线程。unordered_map::erase(threadId) 可以 O(1) 精准删除,而 vector 删除中间元素会导致后续全部移动。

为什么存指针而不存对象?

原因说明
不可拷贝std::thread 对象不可拷贝,存值对象 vector 扩容时无法搬移
地址稳定性线程创建时通过 std::bind 绑定了 this。对象在堆上地址不变,容器只搬指针
独占所有权unique_ptr 明确表达"线程对象只属于这个线程池"

(7) 实战:emplace_back 在线程池中的应用 ​

已在 vector 部分详述 emplace_back vs push_back。在线程池的 Cached 模式下,可能频繁创建/销毁 Thread 对象:

cpp
// push_back:临时对象 → 移动到容器 → 析构临时对象(三步)
threads_.push_back(std::make_unique<Thread>(func));

// emplace_back:直接在容器内存中构造(一步)
threads_.emplace_back(std::make_unique<Thread>(func));

高并发海量任务场景下,省去中间临时对象的构造/析构开销。对于 unique_ptr 这种只能移动不能拷贝的类型,emplace 也更优雅。


四、容器适配器 ​

1. stack / queue ​

Q: 什么是容器适配器?

stack 和 queue 不是真正的容器,而是寄生在底层容器上、限制接口的适配器。

适配器默认底层行为可替代底层
stackdeque<T>LIFO(后进先出)vector<T>, list<T>
queuedeque<T>FIFO(先进先出)list<T>
priority_queuevector<T>优先级队列deque<T>
  • 不支持迭代器,不可遍历
  • 只能访问顶部:stack → top(),queue → front() / back()

2. priority_queue(高频) ​

(1) 本质 ​

cpp
template<class T, class Container = vector<T>, class Compare = less<T>>
class priority_queue;
  • 物理结构:数组(vector)
  • 逻辑结构:完全二叉树(堆)
  • 默认大顶堆(最大值优先)

父子关系(数组下标):

  • parent = (child - 1) / 2
  • left = parent * 2 + 1
  • right = parent * 2 + 2

(2) Less 为什么是大顶堆?(高频陷阱) ​

Q: priority_queue 用 less<T> 为什么是大顶堆?

堆调整的判断条件是:if (comp(parent, child)) → 成立就交换。

  • less<T> → parent < child 时交换 → 大的被推上去 → 大顶堆
  • greater<T> → parent > child 时交换 → 小的被推上去 → 小顶堆

记结论:less = "父小于子时交换" → 结果形成大堆。

cpp
// 默认大顶堆
priority_queue<int> pq1;                              // less<int>

// 小顶堆
priority_queue<int, vector<int>, greater<int>> pq2;   // greater<int>

(3) 建堆为什么是 O(n)? ​

直观感觉每个元素向上调整 O(log n),n 个元素 = O(n log n)。但数学上:

  • n/2 个叶子(高度 0):不调整
  • n/4 节点高度 1:最多调整 1 次
  • n/8 节点高度 2:最多调整 2 次
  • 总操作数:n/4 + 2n/8 + 3n/16 + … < n × 常数 → O(n)

(4) 典型应用 ​

问题策略复杂度
求前 K 大小顶堆(维护 K 个,堆顶最小)O(n log k)
求前 K 小大顶堆(维护 K 个,堆顶最大)O(n log k)
数据流中位数双堆法(大顶堆存较小半 + 小顶堆存较大半)O(log n) / 次

五、迭代器 ​

1. 什么是迭代器(本质) ​

Q: 什么是迭代器?为什么需要它?

迭代器是连接容器与算法的"粘合剂":算法只操作迭代器接口(*it、++it),不关心容器底层是什么结构,所以同一套 std::sort、std::find 能适配不同容器。

本质:迭代器是一个轻量小对象,内部封装"指向容器元素的指针"。节点里不存迭代器,节点只存数据和维持结构的指针。

生命周期——"遍历时才创建,用完自动销毁":

  • 迭代器不是容器"带"的:不用迭代器时,容器里也真的没有任何迭代器对象
  • 它是遍历代码里声明的局部变量(栈对象):执行到声明语句才自动创建,离开作用域自动销毁,无堆分配、无资源释放,零负担
  • begin() 只是按值返回一个临时迭代器,拷贝进你的变量后,临时对象随即消失
cpp
// ① 不用迭代器:容器里真的没有任何迭代器对象
for (size_t i = 0; i < v.size(); ++i) cout << v[i];

// ② 生命周期示例
{
    auto it = v.begin();   // ← 这行代码执行时,it 才在栈上"诞生"(自动创建)
    *it = 42;              //   使用 it
}                          // ← 离开作用域,it 自动销毁(析构就是"消失")

// ③ for 循环里 it 只创建一次,++it 只是改它内部指针的值,it 本身一直活着
for (auto it = v.begin(); it != v.end(); ++it) { ... }
容器迭代器本质对象大小
vector / string / array原生指针 T*8 字节
list / map / set封装节点指针的类8 字节
deque封装 4 个指针的智能迭代器32 字节
cpp
for (auto it = v.begin(); it != v.end(); ++it) {
    cout << *it;   // it 的类型是 vector<int>::iterator,内部就是一个 int*
}

一个容器只有一套迭代器类型,但可以同时存在任意多个实例(像多张书签,都指向不同位置)。


2. 迭代器分类:5 种能力,由弱到强(高频) ​

Q: 迭代器分哪几种?每种能做什么?

记忆方法:分类 = 能力清单,后一种包含前一种的全部能力。

类型能做什么代表
输出 Output只写、单向、单次遍历ostream_iterator、back_inserter(写端)
输入 Input只读、单向、单次遍历istream_iterator(读端)
前向 Forward读写、单向、可多次遍历forward_list、unordered_map
双向 Bidirectional前向 + 支持 -- 反向遍历list、map、set
随机访问 RandomAccess双向 + 支持 it+n / it[i] / 比较vector、deque、string
只写单向(Output) ──┐
                   ├──► 前向(读写单向) ──► 双向(可倒退) ──► 随机访问(可跳跃)
只读单向(Input) ───┘

各容器对应关系:

容器迭代器类型本质
ostream_iterator / back_inserter 等输出(写端,非容器)写流 / 插入适配器
vector / string / array随机访问原生指针(C++20 起称连续迭代器)
deque随机访问智能迭代器类(4 指针)
list双向封装的节点指针类
map / set双向封装的节点指针类
unordered_map / unordered_set前向封装的节点指针类
stack / queue不支持迭代器—

要点:std::sort 要求随机访问迭代器——快排需要 it + n 跳跃寻址;list 只有双向迭代器,所以不能用 std::sort,只能用 list::sort()。


3. 迭代器失效总结(高频) ​

Q: 各容器的迭代器什么时候失效?(高频)

操作vectordequelistmapunordered_map
尾插(不扩容)end 失效end 失效无无无
尾插(扩容/rehash)全部———全部迭代器
中间插入插入点+之后插入点+之后无无无(不 rehash)
erase删除点+之后删除点+之后仅被删仅被删仅被删
clear全部全部全部全部全部

记忆口诀:"搬家全死,删谁死谁"——连续内存容器(vector/deque)扩容或中间增删导致元素"搬家",受影响位置之后的迭代器全失效;链表/树(list/map)元素地址不变,只有被删的那个迭代器失效。


4. 迭代器适配器(补充) ​

有些"迭代器"不是容器给的,而是算法输出/输入端的适配器,来自 <iterator> 库:

适配器作用示例
back_inserter(v)把赋值的元素 push_back 进容器copy(a.begin(), a.end(), back_inserter(v))
ostream_iterator<T>(cout, " ")把元素写入输出流copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "))
istream_iterator<T>(cin)从输入流读取元素copy(istream_iterator<int>(cin), {}, back_inserter(v))
reverse_iterator反向遍历(rbegin() / rend() 返回)for (auto it = v.rbegin(); it != v.rend(); ++it)

它们属于输出/输入迭代器类别。这也解释了为什么容器表格里看不到输出迭代器——它不来自容器,来自算法库。


六、算法 ​

1. sort 内部原理(必问) ​

Q: std::sort 的底层实现?为什么这么快?(高频)

std::sort 不是纯快排,而是内省排序(Introsort)——混合算法:

主体 (快排):
  ├─ 元素数 ≤ 16:退出,交给插入排序
  ├─ 递归深度 > 2·log₂n:切换到堆排序(防止退化 O(n²))
  └─ 正常:三数取中选 pivot → 快排分区 → 单边递归优化

收尾 (插入排序):
  └─ 此时数据已基本有序,插入排序接近 O(n)
算法使用场景特点
快速排序主体平均最快 O(n log n),可能退化 O(n²)
堆排序递归过深时稳定 O(n log n),常数因子大
插入排序子区间 ≤ 16 或收尾小规模/基本有序时近乎 O(n)

核心优化:

  1. 三数取中选 pivot:避免选到极值导致退化
  2. 单边递归优化:只递归右半,左半迭代处理,省一半函数调用
  3. 无边界检查分区:三数取中保证 pivot 在范围内,省去边界判断

std::sort 是不稳定排序,要求随机访问迭代器,复杂度 O(n log n)。


2. lower_bound / upper_bound ​

Q: lower_bound 和 upper_bound 的区别?

函数含义数组 {1,2,2,2,3}
lower_bound(v, 2)第一个 ≥ 2 的位置下标 1
upper_bound(v, 2)第一个 > 2 的位置下标 4
区间[lower_bound, upper_bound)下标 1~3(三个 2)

要求有序,底层二分查找,O(log n)。


3. 常用算法速查 ​

算法作用复杂度要求
sort排序(不稳定)O(n log n)随机访问迭代器
stable_sort稳定排序O(n log n)随机访问迭代器
nth_element第 n 大到位平均 O(n)随机访问迭代器
find顺序查找O(n)—
binary_search二分查找O(log n)有序
lower_bound第一个 ≥ xO(log n)有序
upper_bound第一个 > xO(log n)有序
reverse反转O(n)双向迭代器
for_each逐元素执行O(n)—
count计数O(n)—
unique去重(配合 erase)O(n)需先排序
partition按条件分区O(n)双向迭代器
merge合并两有序序列O(n+m)有序
next_permutation下一个排列O(n)双向迭代器
fill填充O(n)—
copy / move拷贝/移动O(n)—

七、仿函数(Functor) ​

Q: 什么是仿函数?为什么用它而不用函数指针?

如果直接写一个 bool myCompare(int a, int b)函数,然后把函数名传进去,此时它依然会退化成函数指针

仿函数是重载了 operator() 的类,其对象可以像函数一样被调用。

cpp
template<class T>
struct Less {
    bool operator()(const T& a, const T& b) const { return a < b; }
};
int main() {
    Less<int> isLess;
    int x = 10, y = 20;
    // 实际上调用了 isLess.operator()(x, y)
    if (isLess(x, y))
        std::cout << x << " 小于 " << y << std::endl;

    // 使用 Less<int> 实例进行升序排序
    std::vector<int> nums = {5, 2, 8, 1, 9};
    std::sort(nums.begin(), nums.end(), Less<int>());
    return 0;
}

① 性能更高(编译器优化/内联)

  • 函数指针:是一个指向代码段地址的变量。在运行时,编译器通过地址跳转去执行函数。编译器在编译期间只知道这是一个地址,不知道具体要执行哪段代码,编译器很难对其进行内联优化。
  • 仿函数:是一个具体的类类型。当把仿函数传递给std::sort等模板函数时,模板会根据这个具体的类生成一份专门的代码。编译器清楚地知道调用的是哪个类的 operator(),从而能极高概率地进行内联优化,消除函数调用的开销。

② 可以拥有“状态”(State)

  • 函数指针:函数本身不保存状态,只能访问全局变量或传入的参数。有安全性问题
  • 仿函数:**对象本身可以拥有成员变量。**它能“记住”配置信息、计数器、上下文等。
    • 例子:可以创建一个 Add(5) 仿函数和一个 Add(10) 仿函数。它们虽然类型相同,但内部“状态”不同。

3 其他。。。。

仿函数带状态的例子:

状态一般是通过构造时,通过传参记录状态

cpp
struct SumFunctor {
    int total = 0; // 这就是“状态” (State)
    // 每调用一次,都会改变内部的状态
    int operator()(int x) {
        total += x;
        return total;
    }
};
int main() {
    SumFunctor s1; // 创建第一个累加器
    std::cout << s1(10) << std::endl; // 输出 10 (total变成了10)
    std::cout << s1(20) << std::endl; // 输出 30 (total变成了30)

    SumFunctor s2; // 创建第二个累加器(状态独立)
    std::cout << s2(5) << std::endl;  // 输出 5 (s2有自己的total)
    return 0;
}

函数指针指向的是一段纯粹的代码。代码段在程序运行期间是只读的、固定的。

  • 没有存储空间:普通函数没有像类那样的“成员变量”来存储每个实例特有的数据。
  • 无法个性化定制:函数逻辑是写死的。如果你想写一个“加 5 的函数”和一个“加 10 的函数”,你必须写两个不同的函数名。

常见内置仿函数及其应用位置:

仿函数应用位置
less<T>std::sort 默认(升序)、set/map 默认排序、priority_queue 默认(但形成大顶堆)
greater<T>小顶堆 priority_queue、降序排序的比较器参数
equal_to<T>unordered_map 的相等判断(默认 operator==)
plus/minus/multiplies数值算法(如 std::accumulate 的累加器)

Lambda 与仿函数:Lambda 的底层实现就是一个仿函数类(编译器展开生成),兼具仿函数的性能和函数指针的简洁。

为什么无状态 Lambda 能转函数指针,有状态的不能?(高频追问)

  • 无状态 lambda = 没有捕获成员的"空仿函数类",调用不依赖任何对象数据 → 可退化为普通函数指针
  • 有状态 lambda = 类里有捕获的成员变量,调用依赖对象中的数据 → 函数指针没有对象,无法转换
cpp
auto f1 = [](int x) { return x * 2; };       // 无捕获 → 空类
int (*fp)(int) = f1;                          // ✅ 可转函数指针

int base = 5;
auto f2 = [base](int x) { return base + x; }; // 捕获 base → 有成员
int (*fp2)(int) = f2;                         // ❌ 编译错误
std::function<int(int)> sf = f2;              // ✅ 用 std::function 包装(类型擦除)

为 set / map 自定义排序规则:

cpp
struct Person
{
    string name;
    int age;
};

// 方式一:自定义仿函数作为第三个模板参数
struct ByAge {
    bool operator()(const Person& a, const Person& b) const {
        return a.age < b.age;   // 语义:"a 是否排在 b 前面"(严格弱序)
    }
};
set<Person, ByAge> s;              // 按年龄排序
map<Person, int, ByAge> m;         // map 的第三个模板参数同理

// 方式二:lambda + decltype(注意构造时要传比较器对象)
auto cmp = [](const Person& a, const Person& b) { return a.age < b.age; };
set<Person, decltype(cmp)> s2(cmp);

八、空间配置器(Allocator) ​

1. 定位与职责 ​

Q: 空间配置器的作用是什么?

将内存管理与对象构造彻底分离:

操作职责底层
allocate(n)分配 n 字节原始内存malloc
deallocate(p, n)释放原始内存free
construct(p, args...)在内存上构造对象placement new
destroy(p)析构对象显式调用析构函数

new = operator new(分配) + 构造;delete = 析构 + operator delete(释放)


2. SGI STL 两级配置器(核心考点) ​

以 128 字节为分界:

级别范围策略
第一级> 128 字节直接封装 malloc/free,提供 OOM 处理
第二级≤ 128 字节内存池 + 自由链表

第二级详细机制:less<T>

组件说明
自由链表16 条链表,管理 8/16/24/…/128 字节的块,分配/释放 O(1)
内存池链表空时批量为链表补充 20 个块,减少 malloc 调用
Union 优化节点用 union 复用空间,分配给用户后不浪费指针字节
优点缺点
小块分配极快(O(1))内部碎片(对齐到 8 倍数)
减少外部碎片内存不归还 OS(进程结束才释放)
减少系统调用额外管理逻辑复杂

为什么 vector 不能原地扩容?Allocator 接口缺少 realloc,且内存池中相邻地址可能已被其他链表占用。


3. 使用空间配置器的好处 ​

Q: 为什么要空间配置器?直接用 new/malloc 不行吗?

好处说明
减少系统调用二级配置器的内存池批量向 OS 申请,小块分配不再触发 malloc/free
减少内存碎片小内存对齐到 8 的倍数统一管理,释放的小块可被复用
分配极快自由链表取块 O(1)
构造与分配分离allocate 只拿内存、construct 才构造对象,避免无谓的对象构造/析构
可替换性自定义 allocator(内存池、TLS 等)可无缝替换,容器代码不用改

一句话总结:空间配置器把**"内存获取"与"对象构造"解耦**,用内存池 + 自由链表规避频繁系统调用和内存碎片——这正是内存池项目的理论根基。


九、实战避坑 ​

1. 容器选型决策树 ​

需要随机访问?
├─ 是 → 主要尾部操作?→ vector(首选)
│       └─ 需要两端操作?→ deque
└─ 否 → 按键查找?
        ├─ 需要有序/范围查询?→ map/set
        └─ 无序 → unordered_map/set
            └─ 频繁中间插入/删除且不查找?→ list(极少用)

默认用 vector,特殊需求再换。


2. 最常见性能陷阱 ​

#陷阱错误做法正确做法
①vector 频繁扩容不预分配v.reserve(n)
②遍历时拷贝元素for (auto p : map)for (const auto& p : map)
③map[k] 意外插入if (m[k] == 0)m.find(k) != m.end() 或 m.contains(k)
④循环内反复创建容器每次 new 临时容器循环外创建,clear() 复用
⑤删除时迭代器失效v.erase(it); ++it;it = v.erase(it); 或 Erase-Remove
⑥无脑用 map不需要有序也用 map无序场景用 unordered_map(快 3~5 倍)
⑦大对象用 push_back产生临时对象用 emplace_back
⑧vector<bool> 取地址bool* p = &v[0]用 vector<char> 或 deque<bool>

4. 实战:std::array vs std::vector 选型分析 ​

Q: 什么时候用 std::array 而不是 std::vector?

内存池项目中大量使用 std::array,如自由链表数组 std::array<void*, 32768>。选型依据:

维度std::array<T, N>std::vector<T>C 数组 T[N]
内存位置栈 / 静态区堆(动态分配)栈 / 静态区
大小编译期固定运行时可变编译期固定
堆分配开销❌ 无✅ 有(new/malloc)❌ 无
STL 接口✅ size(), at(), 迭代器✅ 完整❌ 几乎没有
边界检查at() 有检查at() 有检查❌ 无

内存池为什么选 std::array?

cpp
// ThreadCache 的自由链表:编译期就知道是 32768 个槽位
std::array<void*, 32768>  freeList_;      // 约 256KB,在 TLS 中
std::array<size_t, 32768> freeListSize_;  // 约 256KB

// 如果改用 vector:
// std::vector<void*> freeList_(32768);   // 堆分配!内存池自身先产生堆碎片
考量说明
避免递归依赖内存池的目的是管理堆内存,如果自身用 vector(堆分配),等于"用堆管理堆"——逻辑矛盾
性能栈上分配 vs 堆分配:array 构造时零开销,vector 需要 new
确定性编译期固定大小,访问 O(1),无扩容担忧
缓存局部性连续内存(同 C 数组),CPU 预取高效

代价评估:32768 × sizeof(void*) = 256KB(每个 ThreadCache 的自由链表),100 个线程约 50MB。相比 pthread 默认 8MB 栈空间,这是可接受的代价。

选型原则:编译期能确定大小 → std::array;运行时大小可变 → std::vector。内存池、线程池中固定大小的表结构是 std::array 的典型应用场景。


3. 多线程环境 ​

Q: STL 容器是线程安全的吗?

**不是!**并发写需要外部加锁:

  • 可以多线程同时读同一容器
  • 任何写操作必须由调用方自行加锁
  • 迭代器生命周期内,容器必须保持不被修改
cpp
std::mutex mtx;
std::vector<int> v;

// 线程安全写法
{
    std::lock_guard<std::mutex> lock(mtx);
    v.push_back(42);
}

deque 在多线程日志系统中优势:扩容不移动已有元素,不影响消费者持有的指针。


十、手写实现类题目 ​

以下为常见的手写题框架,考察对 STL 底层原理的理解。

1. vector 简化实现 ​

cpp
template<typename T>
class MyVector {
    T* _start = nullptr;
    T* _finish = nullptr;
    T* _end_of_storage = nullptr;
public:
    MyVector() = default;
    ~MyVector() {
        clear();
        ::operator delete(_start);
    }

    MyVector(const MyVector& other) {           // 深拷贝
        reserve(other.size());
        for (size_t i = 0; i < other.size(); ++i)
            new(_start + i) T(other[i]);
        _finish = _start + other.size();
    }

    void reserve(size_t n) {
        if (n > capacity()) {
            size_t old_size = size();
            T* new_data = static_cast<T*>(::operator new(n * sizeof(T)));
            for (size_t i = 0; i < old_size; ++i)
                new(new_data + i) T(std::move(_start[i]));   // 移动旧元素
            for (size_t i = 0; i < old_size; ++i)
                _start[i].~T();                               // 析构旧元素
            ::operator delete(_start);
            _start = new_data;
            _finish = _start + old_size;
            _end_of_storage = _start + n;
        }
    }

    void push_back(const T& val) {
        if (_finish == _end_of_storage)
            reserve(capacity() == 0 ? 1 : capacity() * 2);
        new(_finish) T(val);
        ++_finish;
    }

    template<typename... Args>
    void emplace_back(Args&&... args) {
        if (_finish == _end_of_storage)
            reserve(capacity() == 0 ? 1 : capacity() * 2);
        new(_finish) T(std::forward<Args>(args)...);
        ++_finish;
    }

    void pop_back() { --_finish; _finish->~T(); }
    void clear() {
        for (size_t i = 0; i < size(); ++i) _start[i].~T();
        _finish = _start;
    }

    size_t size() const { return _finish - _start; }
    size_t capacity() const { return _end_of_storage - _start; }
    T& operator[](size_t i) { return _start[i]; }
    T* begin() { return _start; }
    T* end() { return _finish; }
};

考点:三指针管理、深拷贝、移动语义、placement new、完美转发。


2. LRU Cache(list + unordered_map 经典组合) ​

cpp
class LRUCache {
    int _capacity;
    list<pair<int, int>> _list;                        // 存 {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> _map;  // key → 链表位置

public:
    LRUCache(int cap) : _capacity(cap) {}

    int get(int key) {
        auto it = _map.find(key);
        if (it == _map.end()) return -1;
        _list.splice(_list.begin(), _list, it->second);   // O(1) 移到头部
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = _map.find(key);
        if (it != _map.end()) {
            it->second->second = value;
            _list.splice(_list.begin(), _list, it->second);
            return;
        }
        if (_list.size() == _capacity) {
            _map.erase(_list.back().first);
            _list.pop_back();
        }
        _list.push_front({key, value});
        _map[key] = _list.begin();
    }
};

考点:splice O(1) 链表嫁接、两个容器组合使用、迭代器稳定性的利用。


十一、高频问答 ​

Q1: vector 扩容机制?迭代器什么时候失效?

扩容 = 新分配 + 移动/拷贝 + 释放旧内存 + 更新指针。扩容 → 全部迭代器失效;中间插入/删除 → 当前位置及之后失效。

Q2: vector 和 list 区别?

vector 连续内存,O(1) 随机访问,缓存友好;list 链表,O(1) 任意位置增删,迭代器稳定。默认选 vector。

Q3: map 和 unordered_map 区别?

map 红黑树,有序,O(log n) 稳定;unordered_map 哈希表,无序,平均 O(1)。需要有序 → map,追求速度 → unordered_map。

Q4: 红黑树为什么不用 AVL?

红黑树弱平衡,插入删除旋转次数少(摊还 O(1)),实际工程增删和查找同样频繁。

Q5: sort 底层实现?

内省排序:快排主体 + 递归过深转堆排 + 小区间插入排序。

Q6: priority_queue 用 less 为什么是大顶堆?

判断条件是 comp(parent, child),less = parent < child 时交换,大的上浮 → 大顶堆。

Q7: emplace_back 和 push_back 区别?

emplace_back 原地构造,省去临时对象的构造和移动开销。对大对象和有参构造优先用 emplace_back。

Q8: reserve 和 resize 区别?

reserve 只改 capacity,不改 size,不构造元素;resize 改 size,会构造/析构元素。

Q9: clear() 会释放内存吗?

不会!只析构元素、size=0,capacity 不变。释放用 shrink_to_fit() 或 swap(空容器)。

Q10: 为什么 list 不能用 std::sort?

std::sort 要求随机访问迭代器,list 只提供双向迭代器。应使用 list::sort()。

Q11: vector<bool> 有什么问题?

特化版本每个 bool 占 1 bit,v[0] 返回代理对象,不能取地址。用 vector<char> 替代。

Q12: deque 和 vector 最主要的区别?

deque 扩容不移动已有元素(分段存储),vector 扩容所有元素移到新地址。元素地址稳定性是 deque 的核心优势。

Q13: unordered_map 负载因子是什么?

size() / bucket_count(),超过 max_load_factor()(默认 1.0)触发 rehash → O(n) 且迭代器全失效。

Q14: map 的 operator[] 陷阱?

key 不存在时会静默插入默认值。检查存在性用 find() 或 contains()(C++20)。

Q15: STL 容器线程安全吗?

不是!多线程写必须外部加锁。可多线程同时读。