region/arena-like 分配的 STL 容器

Question

我正在编写一个 class（霍夫曼编码器，如果您好奇的话），它需要包含一个专门的二叉树，而 STL 容器并不直接适用于该二叉树。用一些 left/right 指针定义一个 TreeNode 结构并构建它是没有问题的。我的问题是关于节点本身的分配。

我认为如果我使用 STL 容器作为我的 "allocator"，而不是直接为每个节点调用 new，那将是非常好的。这很有吸引力，因为它会使破坏变得微不足道：我不必在析构函数中遍历我的树以单独 delete 所有节点；我用作 "allocator" 的 STL 容器的库存析构函数会自动完成。

我第一个 "allocator" 的选择是 std::vector<TreeNode>。但这根本不起作用，因为当然随着向量的增长，它必须重新分配自身并且使我所有的指针无效。所以我现在所做的是坚持 std::vector 的想法并放弃指针；我曾经有一个指针的每个地方我都有一个整数来保存我的向量的索引。也就是说，在我的 parent class 中，我有

这样的成员

std::vector<TreeNode> _heap;        // all nodes in tree
int _root;                          // index into _heap

然后为了分配一个新节点，我做了这样的事情：

TreeNode newnode(/*whatever*/);
nodei = _heap.size();
_heap.push_back(newnode);
// now do something with nodei

事实上，这一切都很好，除了：使用索引而不是指针是一件很麻烦的事情。在任何地方，我通常都会将 pointed-to 节点引用为 *nodep，但我必须改用 _heap[nodei]。（但是，它再次起作用；这不是问题。）

我的问题是：

是否有一个 STL 容器 class 可以保证其元素以后不会移动，从而使指向它们的指针在容器的生命周期内保持有效？
指向 STL 容器中元素的指针是个好主意吗？
对于这种事情（即指向容器化堆中的元素），使用迭代器或引用而不是指针会更好吗？
是否有更好的方法来实现具有简单（即隐式）销毁语义的本地堆分配器？

我对其他想法持开放态度，但我应该警告您我非常保守。我想坚持在 "baseline" C++ 中工作的东西，即我会回避只在 C++11 或其他东西中工作的东西。而且我特别担心 sigc 和 boost 等包的开销和复杂性，因此我也不太可能想要使用它们的特殊容器或分配器之一。

Answer 1

Is there an STL container class that is guaranteed not to have its elements move around later, such that pointers to them will remain valid for the container's lifetime?

std::deque 如果您只移动 push_back/emplace_back 元素，则不会移动元素，这足以完成您的任务，您可以获取指向元素的指针。

此外，std::deque 的最流行实现以块的形式分配内存，其中一个块可以顺序存储多个元素 - 这改善了局部性，并减少了分配次数（与 std::list 相比）。

Are pointers to elements within STL containers ever a good idea?

只要您了解底层语义和保证（您可以在 C++ ISO 中阅读），这是个好主意。

例如，如果您不更改 std::vector 的容量并且不缩小它的大小 - 指向向量中元素的指针就可以了。

Would it be better to use iterators or references instead of pointers for this sort of thing (that is, to point to the elements in the containerized heap)?

除了某些 STL 实现可能会在调试版本中提供额外的防御检查外，我没有看到任何好处。

Is there a better way to implement a local heap allocator, with easy (i.e. implicit) destruction semantics?

实际上我喜欢他们使用索引的想法，即像您所做的那样 region[node_index]（尽管在代码期望 "true" 指针的情况下并不总是可以接受）。我看到了这种方法的几个潜在好处：

std::vector 呈指数增长，导致 O(log N) 分配给 N 个元素。可以为指针获得类似的属性，但它更复杂 - 您应该维护不同大小的块列表，例如 std::vector<std::vector<Node>>，其中每个新块的容量为 total_size * k ，并且您应该确保不要更改它（因为指向元素的指针）。
您可以控制 sizeof(index) - 您可以使用适合您任务的索引类型，例如它可以是 1-2 个字节。但是指针的大小可以大得多，尤其是在 x64 上 - 特大号 8 字节。

region/arena-like 分配的 STL 容器

STL container for region/arena-like allocation

c++

pointers

memory-management

stl

heap-memory