C++ STL

Containers

vector

实现是动态数组 dynamic array. 动态维护数组的长度。当pushback的时候，判断 size() 是否到 capacity(), 如果到了需要扩容。

扩容可以扩旧容量的 1.5-2 倍。然后分配新内存块，移动或者复制到新内存块。扩容的消耗是 $$ 1+2+4+8+..+n/2 $$ 根据等比数列 (geometric series) , 这个是 \(n-1\) 所以是 \(O(1)\) 均摊的

deque

deque是分段内存 (segmented array) . 内部有一个 T* buffer[] 指向各个buffer块。在查询的时候，可以计算offset。扩展的时候分配内存：

• 一开始只分配 512bytes 的block

list

双向链表。

set

用红黑树实现。

multiset

也是用红黑树实现。

map

用红黑树实现。

unordered_set

实现是hash with chaining. 会有不同的桶，添加的时候把元素放到后面。

当元素太多（load_factor > max_load_factor）时：

1. 分配更大的桶数组；
2. 所有节点重新计算哈希值；
3. 根据新的桶数重新分配到新的桶链中。

load factor是元素个数除以桶的数量。可以选择 0.75 或者 1

初始桶数量设置为 1 (GCC) 或者 8 (MSVC), 扩容的时候直接rehash，容量翻倍

unordered_map

和set一样用哈希链表实现，只是存储键值对

Adapters

容器适配器

• stack → 基于 deque 实现
• queue → 基于 deque 实现
• priority_queue → 基于 vector + make_heap 实现

priority queue

本质上是基于动态数组的二叉堆（binary heap）封装，默认是最大堆。

make heap 操作，对每个非叶子节点检查，如果不符合堆性质就下调。

作变量替换 \(d=h-k\)（到叶子的“下滤距离”）： $$ T(h)=\sum_{d=1}^{h} 2^{h-d}\,d = 2^{h}\sum_{d=1}^{h}\frac{d}{2^{d}} \;\le\; 2^{h}\sum_{d=1}^{\infty}\frac{d}{2^{d}} = 2^{h}\cdot 2 = 2^{h+1} \le 2n. $$ 同样得到线性上界。

Allocator

STL 的 allocator 的实现

• operator new和 delete 的封装

ext/pool_allocator.h

• 当小于128Bytes的时候，采用内存池
• 否则用malloc

尺寸类别（size class）

• 比如： 8, 16, 32, 64, 128, 256, ... 字节
• 分配 13 字节 → 向上对齐到 16 字节；

chunk（大块内存块）

• 当某个 size class 的 free list 用完时：
• 一次向系统要一块大内存（比如 4KB、32KB、更多）

malloc

• 小于 128KB的时候，用brk申请堆内存，回收到内存池
• 否则用mmap做文件映射

malloc 最核心的一部分就是：怎样管理空闲块（free chunk）。典型做法：根据大小分不同“桶”（bins），每个桶是一个双向链表或树。

C++17 内存池

std::pmr::unsynchronized_pool_resource
std::pmr::synchronized_pool_resource

String

“带长度 + 自动管理内存的 char 动态数组”

通常带小字符串优化（SSO），底层通过 allocator 用 new/malloc 在堆上分配、扩容、释放。

std::string 的内存管理逻辑基本和 std::vector 类似：

智能指针

在 memory 头文件里

unique pointer

只有一个 unique_ptr 拥有资源；

析构时自动 delete；

不能复制，但可以移动（std::move()）；

shared pointer

• 通过 make_shared 创建
• 当访问计数归0, 自动释放指针
• 线程安全

控制块（control block）包含引用计数与删除器；

多个 shared_ptr 指向同一控制块。

为什么不建议用数组

std::shared_ptr 以前（C++17 之前）极其不建议用于数组，主要是因为它默认会删错对象导致程序崩溃；而在现代 C++（C++17 及以后）虽然支持了数组，但依然不推荐，是因为有更好的替代方案（如 std::vector）比如不知道长度，没有越界检查

weak pointer

不增加引用计数；

常用于解决 shared_ptr 循环引用问题；

不能直接解引用，需 lock() 转为 shared_ptr。

使用场景

场景	建议做法	说明
局部对象、生命周期局限在作用域内	值对象 / 放进 std::vector	不要 new
必须在堆上、单一拥有者	std::unique_ptr<T>	默认选择；零额外控制块
多个组件共同拥有	std::shared_ptr<T>	有原子引用计数成本
观察但不拥有 / 断开循环引用	std::weak_ptr<T>	lock() 临时拿共享所有权
成员指向外部对象但不拥有	原生指针 T\* / 引用 T&	“观察者指针”，不负责释放
容器里存多态对象	std::vector<unique_ptr<Base>>	典型多态持有方式
管理非内存资源（FILE、Socket）	unique_ptr<Res, Deleter>	自定义删除器做 RAII
双向链/图等互指结构	裸指针/weak_ptr 断环	不要 shared_ptr ↔ shared_ptr

condition variable

虚假唤醒

通常指：线程在 std::condition_variable::wait() 等等待操作中，即使没有任何线程调用 notify_one()/notify_all()，也可能“自己醒来”；或者即使收到了通知，醒来时条件并不成立

常见原因（你不需要依赖某一种具体原因）：

• 操作系统/运行时实现允许“无原因返回”以提高实现自由度与性能
• notify_all 唤醒了很多线程，但只有一个线程能真正拿到资源，其他线程醒来后发现条件不成立
• 竞争/时序：通知发生在你重新拿到锁之前，状态又被别的线程改变了

实现：

一个 mutex 保护等待队列

一个等待队列 waiters

wait()：把自己加入队列，然后原子地释放外部 mutex 并睡眠

notify_one()：从队列里选一个 waiter 唤醒

notify_all()：唤醒所有 waiter

shared mutex

C++ 里实现读写锁最常用、最标准的方式是用 std::shared_mutex（C++17）。读线程用共享锁（shared lock），写线程用独占锁（unique lock）

C++14 没有 shared_mutex，但有 shared_timed_mutex

自己实现：用cv维护 active read, active write, wating read, wating write.

自己实现：原子状态 + 等待队列

标准库，Linux / POSIX：

很多实现会优先使用系统提供的读写锁：

• pthread_rwlock_t（或更底层的 futex 方案）

• 一个“读者计数 + 阶段机”的原子状态机

外加 1~2 个 futex 队列用于阻塞/唤醒

semaphore (C++20)

本质是一个计数器 + 等待队列.控制并发度：最多允许 N 个线程同时进入某个区域（限流/资源池）从 C++20 开始，标准库提供了 std::counting_semaphore 和 std::binary_semaphore

C++ 只规定了 语义，不规定具体实现。但主流实现（libstdc++ / libc++）在 Linux 上基本都是这个思路：

用户态的原子计数器 + 慢路径用内核 futex 等待/唤醒

future(C++11)

简单来说，std::future 是一个“凭据”或“存根”（Stub），用来在未来某个时间点获取异步操作的结果。

packaged task

如果你想把任务的定义和任务的执行（比如丢进线程池）分开，用这个。它把一个函数包装起来，让它可以生成 future。

promise

这是最灵活但也最麻烦的方式。你在一个线程里持有 promise（承诺），在另一个线程持有 future。当你手动调用 promise.set_value() 时，future 就能收到数据。

实现

共享状态 (Shared State)

这是实现的关键。这个对象通常是在堆上分配的，并且通过类似 std::shared_ptr 的引用计数机制来管理生命周期

template<typename T>
struct SharedState {
    // 1. 互斥锁：保证线程安全
    std::mutex mtx;

    // 2. 条件变量：用于阻塞和唤醒
    std::condition_variable cv;

    // 3. 存储结果：可能是正常值，也可能是异常
    // std::variant 是 C++17 的，这里仅作示意
    // 实际上可能用 union 或者指针
    std::variant<std::monostate, T, std::exception_ptr> result;

    // 4. 状态标记
    bool is_ready = false;

    // 5. 引用计数 (原子操作)
    std::atomic<int> ref_count = 0;
};

为什么 future 也是有成本的？

看懂了实现，你就明白为什么 C++ 社区一直在说 std::future 比较“重”（Heavyweight）：

1. 堆内存分配：SharedState 必须在堆上（因为不知道 Promise 和 Future 谁活得长），这涉及到 new/malloc，会有内存分配开销。
2. 锁的开销：内部必须使用 mutex 和 condition_variable 来保证线程安全，即使你确定没有竞争，这层锁也是存在的。
3. 虚函数/类型擦除：如果是 std::async，为了通用性，内部往往涉及 std::function 类似的类型擦除机制，带来额外的间接调用开销。

对比 C++20 Coroutines (协程)： C++20 的协程为了解决这个问题，尽量将状态分配在栈帧上，并且在很多场景下是“无锁”的（通过状态机切换），因此比 std::future 轻量级得多。

std::function

你把任意“能像函数一样被调用”的东西（函数指针、lambda、bind 结果、成员函数包装器、仿函数对象）塞进去，它对外只暴露统一的签名 R(Args...)

实现里通常会有一个函数指针表

std::function 内部会有一块“能放东西”的内存：

• 如果 F 足够小、对齐满足、并且移动/拷贝满足要求，就直接放在 std::function 自己内部的 buffer 里（SBO）
• 否则就在堆上 new F(...)，storage 里只放一个指针

而 ops->call 是针对真实类型 F 的模板函数，比如：

• SBO 情况：把 storage.buf reinterpret_cast 成 F*，然后 (*fp)(args...)
• 堆情况：把 storage.ptr 转成 F*，然后调用

只要你是通过 std::function 去调用（写 f(args...)），就几乎一定是间接调用（type erasure 带来的“经由函数指针/跳板函数”调用）

lambda

lambda 表达式不是函数指针，它会生成一个匿名类（闭包类型）

struct __Lambda_2 {
  int a;                       // 捕获的数据成员
  int operator()(int x) const { return a + x; }
};
__Lambda_2 lam{a};

以“传给 std::function”的其实是这个闭包对象 lam。

仿函数 struct

就是Functor

std::move_only_function

在传入捕获了uniqueptr的lambda的时候，要用这个

scoped guard

variant 和 any

variant

std::variant 的实现可以把它当成一个“带标签（tag）的 union”，外加一整套自动生命周期管理（构造/析构/拷贝/移动）和访问分派（get/visit）。

union 最大的坑是：你得自己保证“现在活着的是哪个成员”，以及切换成员时要不要析构/构造。

template<class... Ts>
struct variant_like {
  alignas(max_align) unsigned char storage[max_size];
  unsigned index; // 当前 active 类型
};

any

std::any 的实现核心就是一句话：类型擦除（type erasure）+ 运行期保存“这个盒子里到底是什么类型” + 一套按类型执行拷贝/析构的函数表。

你可以把它想成“把任意 T 塞进去，然后在盒子里偷偷记录 T 是谁，并且记住怎么销毁/拷贝/移动它”。

std::any 里通常存了什么（概念结构）

一个典型实现（不同标准库细节不同）大概长这样：

• 指向类型信息的指针（通常是 std::ttype_info* 或等价物）
• 一套操作函数指针（像小型 vtable）：
• destroy：怎么析构里面的对象
• copy：怎么拷贝出一份
• move：怎么移动出一份 -（可能还有）type() 返回 type_info
• 存储区：
• 小对象：直接放在 any 内部的固定缓冲区（SBO：Small Buffer Optimization）
• 大对象：放堆上，any 内部只存一个指针

所以你会看到 any 通常比一个指针大：因为它要存“类型 + 管理器 + 存储”。

barrier(C++20)

latch(C++20)

coroutine

#include <print>

#include <coroutine>

struct SimpleTask {

    struct promise_type {
        SimpleTask get_return_object() {
            return {};
        }

        std::suspend_never initial_suspend() {
            return {};
        }

        std::suspend_never final_suspend() noexcept {
            return {};
        }   

        void return_void() {}

        void unhandled_exception() {}
    };
};

SimpleTask myCoroutine() {
    std::println("Start");

    co_return;
}

auto main() -> int {
    myCoroutine();
    std::println("Finish");
}

promise type

C++ 标准规定：如果你想让一个函数的返回值是 SimpleTask 并且它是一个协程，那么 SimpleTask 里面必须有一个叫 promise_type 的类型。它是协程的大脑。

1. get_return_object():
2. 作用： 制造出给调用者（main函数）看的那个对象。
3. 对应代码： main 函数里拿到的 SimpleTask 对象，就是这里造出来的。
4. initial_suspend():
5. 作用： 协程创建好了，要不要立马执行用户代码？
6. 你的代码： std::suspend_never（不暂停）。
7. 含义： “不要等，直接冲进 myCoroutine 的花括号里执行代码。”
8. 对比： 如果返回 std::suspend_always，协程创建后会卡在第一行，需要你在 main 里手动 .resume() 才会跑。
9. final_suspend():
10. 作用： 用户代码跑完了，协程要销毁了，要不要最后暂停一下？
11. 你的代码： std::suspend_never（不暂停）。
12. 含义： “跑完就自杀”。协程执行完逻辑后，直接销毁所有内存。
13. 对比： 通常如果我们要从外部读取结果，这里会返回 std::suspend_always，保持协程尸体不腐烂，读完数据再手动销毁。
14. return_void():
15. 作用： 对应代码里的 co_return;。如果是 co_return 1;，这里就需要定义 return_value(int v)。

调用流程

1. 分配内存 (The Frame)

编译器在堆 (Heap) 上申请一块内存，叫做 "协程帧 (Coroutine Frame)"。 这块内存里存放了：

• 协程的参数（这里没有）
• promise_type 对象
• 局部变量
• 暂停点的状态（IP 寄存器等）

2. 构造 Promise

在协程帧里，调用 promise_type 的构造函数。

此时：大管家就位。

3. 获取返回值 (Get Return Object)

调用 promise.get_return_object()。

• 这个函数创建了一个 SimpleTask 对象。
• 注意： 这个对象现在被暂存在栈上，还没有返回给 main 函数！编译器先把它捏在手里。

4. 初始挂起 (Initial Suspend)

调用 promise.initial_suspend()。

• 你的代码返回了 std::suspend_never。
• 结果： 编译器决定不暂停，直接跳转到用户的函数体开始执行。

5. 执行你的代码 (User Body)

程序指针 (IP) 指向你写的代码：

屏幕打印出 "Start..."。

6. 遇到结束 (Return)

执行到 co_return; 或者函数结尾。

• 调用 promise.return_void()。

7. 最终挂起 (Final Suspend)

调用 promise.final_suspend()。

• 你的代码返回了 std::suspend_never。
• 结果： 编译器决定不暂停，直接清理现场。

8. 销毁与返回

• 因为最终没有挂起，协程帧调用 delete 销毁自己（释放堆内存）。
• 关键一步： 之前在第 3 步捏在手里的那个 SimpleTask 对象，现在终于返回给了 main 函数。

Awaitable（可等待对象）

这个结构体有

await ready

bool await_ready()

作用：询问“数据是不是已经准备好了？”

• 如果返回 true：说明菜已经做好了（或者不用做）。编译器会直接跳过暂停环节，不挂起协程，直接拿结果走人。这是一种性能优化。
• 如果返回 false：说明“还没好，得等”。编译器这才会去执行暂停（挂起）的逻辑。

await suspend

void await_suspend(std::coroutine_handle<> h)

作用：协程暂停后，我们要去安排异步任务。

这是最关键的一步。当这个函数被调用时，协程已经暂停了（状态已经保存到了堆内存中）。

• 参数 h (Handle)：这就是协程的遥控器。
• 谁拿到了 h，谁就有能力按下“播放键”让协程复活。
• 你必须把这个 h 存起来（存到线程池、定时器队列、或者网络库的回调里）。如果你把 h 弄丢了，这个协程就永远“植物人”了，再也醒不过来。

await resume

std::string await_resume()

作用：协程醒来后，产出最终的值。