STL container for region/arena-like allocation

Question

I'm writing a class (a Huffman encoder, if you're curious) that needs to contain a specialized binary tree for which an STL container wasn't directly appropriate. And it's no problem to define a TreeNode structure with some left/right pointers and build the thing. The questions I have concern the allocation of the nodes themselves.

I thought it would be really nice if I used an STL container as my "allocator", rather than directly calling new for each node. This was attractive because it would make destruction trivial: I wouldn't have to walk my tree in the destructor to individually delete all the nodes; the stock destructor for the STL container I'd used as my "allocator" would do it automatically.

My first choice of an "allocator" was std::vector<TreeNode>. But this didn't work at all, because of course as the vector grows, it has to reallocate itself and that invalidates all my pointers. So what I'm doing for the moment is clinging to the std::vector idea and abandoning the pointers; every place I used to have a pointer I have an integer holding an index into my vector instead. That is, in my parent class I have members like

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

And then to allocate a new node I do something like this:

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

And in fact this is all working just fine, except: working with indices instead of pointers is a plain nuisance. Everywhere I'd normally reference a pointed-to node as *nodep I have to use _heap[nodei] instead. (But, again, it works; that's not the problem.)

My questions are:

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?
2. Are pointers to elements within STL containers ever a good idea?
3. 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)?
4. Is there a better way to implement a local heap allocator, with easy (i.e. implicit) destruction semantics?

I'm open to other ideas, although I should warn you that I'm pretty conservative. I'd like to stick with something that works in "baseline" C++, i.e. I'll shy away from something that's only in C++11 or something. And I'm especially leery of the overhead and complexity of packages like sigc and boost, so I'll be unlikely to want to use one of their special containers or allocators, either.

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 would not move elements if you would only push_back/emplace_back elements, which is sufficient for your task and you can take pointers to elements.

Also, most popular implementations of std::deque allocate memory in chunks, where one chunk can store multiple elements sequentially - this improves locality, and reduces allocations count (compared to std::list).

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

It is good idea as long as you know underlying semantics and guarantees (which you can read in C++ ISO).

For instance, if you do not change capacity of std::vector and do not resize it down - pointers to elements within vector would be OK.

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)?

I don't see any benefits except that some STL implementations may provide additional defensive checks in Debug builds.

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

Actually I like they idea of using index, i.e. region[node_index] as you did (though it is not always acceptable in cases where code expect "true" pointers). I see several potential benefits in this approach:

• std::vector grows exponentially, resulting in O(log N) allocations for N elements. It is possible to get similar property for pointers, but it is more complex - you should maintain list of chunks of different sizes, like std::vector<std::vector<Node>>, where each new chunk has capacity total_size * k, and you should be sure to not change it (because of pointers to elements).

• you have control of sizeof(index) - you can use index type which just fits for your task, for instance it could be 1-2 bytes. But size of pointers can be much larger, especially on x64 - king-size 8 bytes.