0. 前言

1. 静态空间

• 优点：分配速度极快（可视为 0 开销），生命周期与程序相同。
• 缺点：大小固定，缺乏灵活性，无法利用多余的空间。
• 结论：在 OI 中，对于已知最大数据规模的题目，这是一种简单粗暴且高效的选择，但已经太快了所以 没有优化空间。

2. 栈空间

• 优点：分配速度 极快（通常只是一条指令调整栈指针）。函数返回时自动释放，不易造成内存泄漏。
• 缺点：
  1. 栈空间通常较小（尽管 OI 环境限制较宽）。
  2. 极难封装：由于内存会在函数结束时自动释放，你无法将其安全地返回给调用者（会导致悬空指针）。通常只能用宏（#define）进行局部封装。
• 结论：因其封装性极差，在需要构建通用数据结构时 基本没用。

3. 堆空间

3.1. malloc / free

• 优点：速度快，是其他高级接口的基石。
• 缺点：
  • 没有异常处理：分配失败时返回 NULL，需要手动检查。
  • 不易管理：需要手动计算大小、类型转换，以及确保配对释放，容易导致内存泄漏和越界访问。

3.2. ::operator new / ::operator delete

• 与 malloc 的区别： ::operator new 在分配失败时会抛出 std::bad_alloc 异常，而非返回 nullptr。 比 malloc 多一次检查分支，但在 -O2 优化下，其效率与 malloc 基本相当。
• 缺点：同 malloc/free，需要手动管理类型和生命周期。

3.3. new / delete

说明：在 OI 中，基本不会单独分配对象，更多的是分配数组。

3.4. new[] / delete[]

• 重要细节：
  1. 对于 POD（Plain Old Data）类型（如 int， double），new Type[N] 不会 进行值初始化，内存内容是未定义的，而 new Type[N]{} 会将其初始化为零。
  2. 性能开销：即使是 int 这样没有构造/析构函数的类型，new[] 和 delete[] 的实现中也可能包含一个循环来（-O0）处理每个元素的构造与析构，这会带来微小的开销。
• 结论：在追求极致性能的场景下，它并非最佳选择。

3.5. std::allocator

• 工作原理：分离内存分配和对象构造。
• 优点：
  • 极快：现代标准库（如 GCC 的 libstdc++ 与 Clang 的 libc++）对其进行了高度优化，通常包含内存池、碎片整理等机制，其性能往往优于直接调用 malloc。
  • 极易封装：它是所有 STL 容器默认的分配器，使用起来无缝衔接。
• 缺点：无。
• 结论：在绝大多数情况下，这是手写容器时的 最佳选择。

3.6. 手写 operator new[] / operator delete[]

• 优化点：OI 中使用的动态数组（如 int， char）大多是 POD 类型，不需要调用构造函数和析构函数。 我们可以自己重载 operator new[] 和 operator delete[]，直接调用底层的 malloc/free 或 ::operator new/::operator delete，跳过那个无用的构造/析构循环。
• 优点：快，接近底层接口的速度。
• 缺点：需要自己实现，但代码非常简单。

// 一个简单的 POD 类型 operator new[] 重载示例
void* operator new[](std::size_t count) {
    return ::operator new(count);
}
void operator delete[](void* ptr) noexcept {
    ::operator delete(ptr);
}

3.7. 手写内存池

一个功能齐全且效率不低的内存池通常极长。 幸运的是，OI 环境是单线程的，可以减少大量码量。 👉 简易实现

• 目标：通过批量申请大块内存，并自行管理分配与释放，来减少调用 malloc/free 的次数，从而降低系统调用开销和内存碎片。
• 优点：在特定场景下可以做到 极快 的分配/释放。
• 缺点：需要较深理解，但优化效果不一定显著。在 OI 中 不推荐投入过多精力。

常见的内存池优化技术（由重要到次要）

1. 碎片处理
   • 场景：邻接表中有大量小的 std::vector。若无内存池，每个 vector 的扩容都会调用 malloc，产生巨大开销。
   • 方案：预分配一大块内存（一个池），维护一个指针指向剩余空间的起始位置。分配内存仅仅是将该指针向后移动指定大小，速度极快。
2. 分类
   • 场景：产生了长度不一的内存需求，不能统一使用一个内存池。
   • 方案：提前定义多个内存池，选择能够使用的内存池中最小的一个，并在需要的内存过大时直接分配。
3. 拉链表 / 空闲链表
   • 场景：池内的内存被分配后又释放，产生内部碎片，需要回收利用。
   • 方案：将释放出来的内存块组织成一个链表（空闲链表）。下次分配时，先从空闲链表中寻找合适大小的块。

3.8. 第三方库内存池

• mimalloc
• tcmalloc
• jemalloc
• 缺点：OI 竞赛环境通常不允许链接外部库。
• 优点：所有。

4. 总结

性能（速度）排名（大致）

静态空间 >> 栈空间 > 第三方内存池 ≈ 手写内存池 > std::allocator >
malloc/free ≈ ::operator new/delete > 手写 new[]/delete[] >
new/delete >> new[]/delete[]

易封装性排名

第三方内存池 > 手写内存池 > std::allocator >>
手写 new[]/delete[] > new[]/delete[] >
new/delete > ::operator new/delete = malloc/free >> 栈空间

易管理性排名

手写内存池 > 第三方内存池 > 栈空间 >
std::allocator > 手写 new[]/delete[] >
new[]/delete[] > new/delete >
::operator new/delete = malloc/free