c++与C语言向后兼容，这意味着我们可以在c++程序中使用C提供的任何功能。我们将使用的一个特定工具来实现自定义内存管理器是C内存管理函数malloc和free。要在c++程序中使用这些函数，需要使用include语句
# include < stdlib.h >
C语言malloc（或内存分配）函数用于分配内存块并返回指向该块的指针。malloc的唯一参数是以字节为单位的块大小。为了帮助我们计算特定内存块需要多少字节，malloc通常与sizeof（）操作结合使用，该操作返回特定数据类型的字节大小。
例如，假设我们正在编写一个使用node类型对象的程序。要使用malloc分配一个node类型的对象，可以使用下面的代码：
Node *ptr = (Node *)::malloc(sizeof(Node))；
要创建一个包含1000个节点的数组，我们可以这样做
Node *ptr = (Node *)::malloc(1000*sizeof(Node))；
因为malloc返回一个指向内存位置的泛型指针（称为void*指针），我们必须将malloc返回的指针类型强制转换为我们想要创建的类型。
尽管上面的代码表明我们可以在c++程序中使用malloc为对象分配内存，但这种方法忽略了c++中对象创建的一个重要方面。以这种方式分配对象不会导致调用对象的构造函数。保证调用对象构造函数的唯一方法是使用new创建对象。下面我将展示如何结合使用new和自定义分配方案。
当使用完最初由malloc分配的内存块时，可以通过调用free函数释放该内存。
::自由(ptr);
当你在c++中用new创建对象时，你是在使用c++标准库提供的通用内存管理系统。c++允许您用自己的内存管理系统替换这个通用内存管理器。这样做的关键是能够在任何类中重写operator new和operator delete。在这些课堂笔记中，我将演示如何通过实现一个自定义内存管理器来实现这一点，该管理器与我为b树分配编写的b树实现相结合。
我将使用自定义内存管理器来管理我的b树的BTreeNode对象的分配。因为赢博体育的BTreeNode对象都有相同的大小，我们只需要管理单一类型对象的分配和释放，我们可以为这个赢博体育程序设计一个简单而高效的内存管理系统。
设置自定义内存管理器的第一步是设置内存池。这只是一个用malloc分配的大型btreenode数组。为此，我们添加了一对成员变量
静态BTreeNode<T， M> *pool；静态int next；
到BTreeNode类。第一个变量是指向内存池开始的指针，第二个变量是一个索引，我们将使用它来跟踪内存池中下一个可用的未分配BTreeNode的位置。
除了这两个新的成员变量之外，我们还向BTreeNode类添加了一对静态成员函数。这些函数负责设置和删除btreenode的内存分配系统：
模板<typename T, int M> void BTreeNode<T，M>::initMemory(int maxNodes) {pool = (BTreeNode<T，M>*)::malloc(maxNodes*sizeof(BTreeNode<T， M>))；Next = 0；}模板<typename T, int M> void BTreeNode<T， M>:: releasemmemory () {::free(pool)；｝
这两个静态方法必须在我们计划在赢博体育程序中对BTreeNodes执行任何操作之前和之后调用。initMemory方法接受一个参数，即我们希望在池中拥有的节点数量。我们必须小心地将这个值设置得足够大，以便我们可以提供赢博体育程序所需的尽可能多的节点。
设置内存管理所需的最后一步是覆盖类的operator new和operator delete。下面是我们类的operator new实现的初始代码：
模板<typename T, int M> void* BTreeNode<T， M>::operator new(std::size_t size) {void* result = &(pool[next])；下一个+ +;返回结果;｝
这段代码只是返回池中下一个可用BTreeNode的地址，并增加下一个索引。
操作符new的目的是分配所需大小的内存块，并返回指向该块的指针。这里的代码通过简单地返回指向池中的一个块的指针，非常快速和有效地完成了这一点。重写操作符new的最大优点是，我们可以用我们自己的更快的内存管理器替换通用内存管理器，同时仍然保证我们正在分配的对象的构造函数将被调用。
内存分配系统的另一个功能是处理已删除对象的内存重用。为了管理这方面的内存分配，我们将在自定义内存分配器中添加一个额外的特性，一个空闲列表。空闲列表是通过调用delete释放的内存块的单链表。为了实现这个系统，我们添加了另一个静态成员变量
静态void* free；
到我们的BTreeNode类，并修改initMemory函数来初始化这个成员变量。
模板<typename T, int M> void BTreeNode<T，M>::initMemory(int maxNodes) {pool = (BTreeNode<T，M>*)::malloc(maxNodes*sizeof(BTreeNode<T， M>))；Next = 0；Free = nullptr；｝
然后，提供操作符delete的实现，该实现接受任何已删除的BTreeNode，并将其添加到空闲列表中。
模板<typename T, int M> void BTreeNode<T， M>::operator delete(void* ptr) {void** handle = (void**)ptr；*handle = free；Free = ptr；｝
这里的代码有些微妙。传递给delete操作符的参数ptr是一个通用指针，指向被删除的BTreeNode所占用的内存块的开始位置。我们要做的第一件事是将该指针类型强制转换为指向另一个指针的指针。完成这些操作后，就可以将自由指针（指向自由列表的起始点）的当前值赋给该位置。最后，更新自由指针，使其指向刚刚添加到自由列表开头的块。
一旦我们建立了一个自由列表，我们还必须返回并更新操作符new的代码，以便它将从自由列表中返回可用的块：
模板<typename T, int M> void* BTreeNode<T， M>::operator new(std::size_t size) {if (free != nullptr) {void* result = free；Void ** handle = (Void **)free；Free = *handle；返回结果;} void* result = &(pool[next])；下一个+ +;返回结果;｝
我们在这里添加的代码将跟随自由指针指向它所指向的块。在那个位置有一个指针指向空闲列表中的第二个块。通过更新自由指针以指向第二个块，我们有效地从自由列表中解钩第一个块，然后可以返回指向该块的指针。如果当前空闲列表中没有可用的空间，则操作符new将以正常方式从池中分配一个块。
这里缺少的一个重要特性是检查内存不足情况的任何附加逻辑。为了使系统更完整和正确，我们还应该在这里添加逻辑，检查系统中是否没有剩余的块，并在发生时抛出异常。
因为c++中的通用内存管理器是一个通用系统，它被设计为为赢博体育不同类型的对象分配内存，所以它往往比只需要为单一类型的对象分配内存的专用系统要慢。
为了测试我的自定义内存分配系统的性能，我编写了一个测试程序来分配和释放大量的btreenode：
int main() {BTreeNode<int, 4>::initMemory(100000)；{b树<int, 4>树；//读取第一个数字列表std::ifstream one("numbers.txt")；std::向量< int >数字;int x;While (one >> x) {numbers.push_back(x)；} one.close ();//将第一个列表中的赢博体育数字加到树中clock_t start = std::clock()；For (auto itr = numbers.begin()；= numbers.end()；tree.contains(* Itr)) tree.insert(* Itr)；std::cout << ((double)((std::clock() - start) * 1000)) / CLOCKS_PER_SEC << “ milliseconds to insert.”< < std:: endl;//读取第二个数字列表std::ifstream two("remove.txt")；numbers.clear ();While (two >> x) {numbers.push_back(x)；} two.close ();//删除第二个列表中的数字start = std::clock()；For (auto itr = numbers.begin()；= numbers.end()；如果（tree.contains(* Itr)） tree.remove(* Itr)；std::cout << ((double)((std::clock() - start) * 1000)) / CLOCKS_PER_SEC << “ milliseconds to remove.”< < std:: endl;//将第二个列表中的数字重新加入。start = std::clock()；For (auto itr = numbers.begin()；= numbers.end()；tree.contains(* Itr)) tree.insert(* Itr)；std::cout << ((double)((clock() - start) * 1000)) / CLOCKS_PER_SEC << “ milliseconds to insert.”< < std:: endl;} BTreeNode<int, 4>:: releasmemory ()；返回0;｝
我还编写了该程序的第二个版本，它对赢博体育对象（包括BTreeNode类）使用内置内存管理器。
上面的代码从文本文件中读取100,000个随机整数，并将它们存储在b树中。然后，它读取第二个包含50,000个随机整数的列表，从b树中删除它们，然后将它们添加回b树中。这将测试空闲列表的性能，因为从b树中删除大量项将导致大量的btreenode被删除并返回到空闲列表。
为了测量插入和删除操作的性能，我使用std::clock（）函数来测量执行这些操作所需的时间量。要使用这个函数，您需要包含
使用内置的内存管理器，程序报告这些时间：
100.354毫秒插入。35.284毫秒。插入62.58毫秒。
使用我们自己的自定义内存管理器，程序报告：
86.817毫秒插入。移除时间为29.14毫秒。52.784毫秒插入。
总的来说，速度提高了15%。