浅谈C++中的内存分配

zhuziyue321 · 2025-10-16 22:14:59 · 科技·工程

0. 前言

在 OI 竞赛中，你通常 完全不需要 考虑手动内存管理。STL 已经足够了。

然而，这篇文章是写给需要卡掉两个 \log 的人和抢最优解的人的。 接下来我会从最简单到最复杂分析各种内存分配策略。

1. 静态空间

在编译期就确定大小的数组，比如全局或静态数组。

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

2. 栈空间

栈空间通过函数调用栈进行分配。 C 语言提供了 alloca() 函数来动态地在栈上分配空间。

• 优点：分配速度 极快（通常只是一条指令调整栈指针）。函数返回时自动释放，不易造成内存泄漏。

• 缺点：

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

3. 堆空间

可以负责任地说，99.9% 的动态内存需求都由堆空间满足，无论是 OI 环境还是开发环境。 因此，这里是内存分配性能优化最重要的部分。

我们将从底层到高层进行讲解。

3.1. malloc / free

这是 C/C++ 中最底层的内存分配接口。

• 优点：速度快，是其他高级接口的基石。

• 缺点：

  • 没有异常处理：分配失败时返回 NULL，需要手动检查。
  • 不易管理：需要手动计算大小、类型转换，以及确保配对释放，容易导致内存泄漏和越界访问。

3.2. ::operator new / ::operator delete

这是 C++ 中与 malloc/free 对等的操作符函数。

• 与 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

当之无愧的 STL 之光。

• 工作原理：分离内存分配和对象构造。

• 优点：

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

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

针对 OI 场景的特定优化。

• 优化点：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。

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

静态空间 >> 栈空间 > 第三方内存池 ≈ 手写内存池 > 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

附：如果不用 std::allocator，手写 std::vector 时可以通过构造时 reserve(4) 凑合一下。 倍增时可以开 4 倍减少开销。 实现宏 + 栈空间时不要嫌麻烦或不优雅，没有自动构造/析构的都不推荐。 内存池推荐块长与系统页长相同，也可以尝试用静态数组代替动态内存（经测试不佳）。 linux 里 brk 比 mmap 快，但是不能释放。