列表节点元素删除后的内存回收

Question

我想知道，当元素从列表中删除时，STL的std::list是否实现了某种形式的节点“内存保存/回收”，以重用先前节点占用的内存，以便将来向列表中添加新元素。

例如，当调用std::list::pop_back()以删除链接列表的最后一个元素时，该节点占用的内存是某种保存的内存，因此当使用push_back()将一个新元素添加到链接列表的末尾时，新节点没有动态内存分配，而只是回收先前删除的节点的内存。

这与std::vector类似，后者具有松弛能力。

Answer 1

这是一个相当老的问题，但它出现在谷歌时，我正在寻找这方面的信息。

当从std::list中移除某项时，该项的内存将被释放和销毁，除非您提供了一个备用分配器，该分配器在请求释放内存时会执行一些不同的操作。标准库容器具有相当好的定义内存特性，我怀疑任何现代标准库实现尝试重用内存。操作系统可能试图提高分配和取消分配的效率，但是默认的分配器仍然是进行系统malloc/free调用，我认为这是您要避免的代价高昂的事情。

实现这一点的一种通用或通用方法是编写您自己的分配器。

不过，只要使用std::list，如果您想要重用内存，可以尝试使用splice()将项重新链接到另一个可重用项列表中。或者，如果同时添加项和移除另一项(例如，当项目添加到前面时，缓冲区或固定大小的队列从后面移除项)，则将旧项拼接到新位置并替换其内容等。

更多关于拼接：https://en.cppreference.com/w/cpp/container/list/splice

不要混淆splice()参数。(文档中写着“另一个列表”，但可能是同一个列表；请注意，迭代器不会失效。)

请注意，这是与自定义内存管理相邻的，因此请确保您有一个清晰、定义良好的算法来执行此操作。

与C++一样，您需要知道何时复制、分配和可能移动对象/值。仔细阅读std::list文档，了解它在分配和复制数据时的情况。https://en.cppreference.com/w/cpp/container/list

下面的示例将列表中的最后一个元素重新链接到前面：

#include <list>
#include <iostream>
#include <algorithm>

int main() {
  std::list<int> l{1, 2, 3, 4};

  std::for_each(l.begin(), l.end(), [](int i){std::cout << i << ", ";});
  std::cout << "\n";

  auto topos = l.begin();
  auto frompos = l.end();
  frompos--;
  l.splice(topos, l, frompos);

  std::for_each(l.begin(), l.end(), [](int i){std::cout << i << ", ";});
  std::cout << "\n";

  return 0;
  }

修改上面的内容，将结构或对象存储在列表中，这些结构或对象在构造、销毁、复制和移动时打印出来，然后尝试使用insert()、emplace()、remove()、pop_back()等来查看发生了什么。