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）时：

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

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 的实现

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 指向同一控制块。

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`