自动关联目录：STL 容器与分配器

选容器的本质是选内存布局：连续、链式、哈希、树。布局决定了缓存命中率，而缓存命中率在现代 CPU 上往往比算法复杂度更决定性。

一句话定位：默认 std::vector；只有明确的理由才换。绝大多数"要不要用 map"的纠结，答案都是"vector + sort"。

选型

"链表为什么慢"：每个节点一次随机内存访问，缓存全废。1000 个元素的 std::list 遍历，通常比 1000 个元素的 vector 慢一个数量级，即使两者都是 O(n)。

判断流程：

需要按 key 查？ ──否──► vector
      │是
需要有序遍历？ ──是──► map
      │否
   unordered_map

vector 的关键行为

std::vector<Foo> v;
v.reserve(1000);           // 预留，避免扩容搬移
v.emplace_back(a, b);      // 原地构造，比 push_back(Foo(a,b)) 少一次移动
v.shrink_to_fit();         // 释放多余容量（可能搬移）
v.clear();                 // 析构元素，保留容量

扩容搬移是隐藏的性能杀手：vector 里存大对象时，一次扩容要移动所有元素。存 std::unique_ptr 或索引能显著缓解。

迭代器失效速查

"扩容后全部失效"是最常见的悬垂迭代器来源——如果必须先 reserve，或者干脆用索引而不是迭代器。

unordered_map 的代价

m.reserve(10000);                    // 避免 rehash
m.max_load_factor(0.7f);             // 降低装载因子换速度

小数据集（< 几十个元素）用 vector 线性查找往往更快——没有哈希开销，且缓存连续。只有元素多了才显出 O(1) 的优势。

分配器

分配器的作用是"把内存从哪来"这件事抽出来。默认 std::allocator 走 operator new → malloc。

template<typename T>
struct PoolAllocator
{
    using value_type = T;
    T* allocate(std::size_t n);
    void deallocate(T* p, std::size_t n);
};

using FastVector = std::vector<Foo, PoolAllocator<Foo>>;

std::pmr 是 C++17 之后的正解——过去自定义分配器会改变容器类型（vector<T, MyAlloc>），pmr 用类型擦除解决了这个问题：

std::pmr::monotonic_buffer_resource Pool(Buffer, sizeof(Buffer));
std::pmr::vector<int> v(&Pool);

为什么 malloc 慢

优化顺序：先减少分配次数，再换分配器。池化的收益主要来自"不再频繁 malloc"，而不是"malloc 变快了"。

与 UE 的对照

UE 用自己的容器而非 STL（理由见 容器字符串与内存）：

规则：在 UE 代码里用 UE 容器，混用会导致内存统计对不上、分析工具看不到。

常见坑