Allow intrusive containers to work with relative pointers (ie with nodes stored in a vector)

[fdegros@…]

There is an interesting use case that Boost Intrusive containers don't seem to support yet.

I would like to store the nodes of my collection in an std::vector. The problem is: as nodes get pushed to the back of the vector, the vector reaches capacity, reallocates its internal buffer and these nodes don't stay at the same address. I therefore cannot use pointers (which hold an absolute address) to chain these nodes together.

However, I would like to use indices to chain these nodes. I call that index chaining. The idea is simple. Nodes stay at the same (relative) index inside the vector even though the vector grows and reallocates its internal buffer. Any node-based collection (linked list, red-black tree, etc), can be stored in a contiguous area of memory and represented using index chaining.

Think of the index as a relative pointer. This relative pointer needs some context to be dereferenced: the vector in which the elements are stored.

There are several good reasons why we might want to store a node-based data structure in a vector. It is more compact. It is more cache-friendly. We can use shorter integers to represent indices (eg int32_t compared to 64-bit absolute pointers), which makes the nodes more compact and the whole data structure more cache-friendly. All the nodes are colocated in a single memory block. If the nodes are trivially destructible, deleting the whole data structure is just a matter of deallocating a single memory block.

Las, the different traits class that would have helped (pointer_traits, node algorithms) are stateless and only work through static methods. And offset_ptr doesn't cut it.

I haven't found a way to get Boost intrusive to work this way. I might not be the only one trying. groups.google.com/forum/m/#!topic/boost-list/PYKJlqT_wuw describes a similar, if not the same, request.

Consider supporting this feature. That would open Boost intrusive to the realm of compact and relocatable node-based data structures.