[Boost-bugs] [Boost C++ Libraries] #13141: Allow intrusive containers to work with relative pointers (ie with nodes stored in a vector)

Subject: [Boost-bugs] [Boost C++ Libraries] #13141: Allow intrusive containers to work with relative pointers (ie with nodes stored in a vector)
From: Boost C++ Libraries (noreply_at_[hidden])
Date: 2017-07-28 05:23:14

#13141: Allow intrusive containers to work with relative pointers (ie with nodes
stored in a vector)
------------------------------+---------------------------
 Reporter:  fdegros@…         |      Owner:  Ion Gaztañaga
     Type:  Feature Requests  |     Status:  new
Milestone:  To Be Determined  |  Component:  intrusive
  Version:  Boost 1.64.0      |   Severity:  Optimization
 Keywords:                    |
------------------------------+---------------------------
 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.

-- 
Ticket URL: <https://svn.boost.org/trac10/boost/ticket/13141>
Boost C++ Libraries <http://www.boost.org/>
Boost provides free peer-reviewed portable C++ source libraries.