Hi, I would like to use some boost::intrusive data structures (lists and trees) in a project I'm working on, but I ran into trouble trying to customize the existing classes to my needs. I decided to post my problem here, in case somebody knowledgeable of boost::intrusive *implementation details* can assist me. Thank you in advance. Background: In the project I'm working on, I need to manage a large number of objects in memory. The data is dynamic, so I need to be able to alloc&dealloc objects, in addition to keeping the objects in various lists&trees (for which I'm trying to use boost::intrusive). The RAM usage is large (think, >100GB), but the number of objects is smaller than 2^32. So one thing I'd like to do is to replace 8-byte raw pointers with 4-byte offsets into a deque. Doing this would solve the alloc/dealloc part. However, I now need to customize boost::intrusive containers to work with these 4-byte offsets instead of raw pointers. Initial solution that doesn't work: The most important limitation of these 4-byte indirect pointers (say to a type T) is that if you fully dereference one to T&, you can no longer reconstruct the indirect pointer (with operator&) in constant time. I.e. converting a real-pointer to indirect-pointer must be avoided. Thus, to make methods such as insert(T&) work, I had to roll out a reference-replacement class in addition to the pointer-replacement class. This is what I initially tried: - Given a type T, I rolled out pointer-replacement class Ptr<T> which holds a 4-byte int, and upon operator*, it produces a Ref<T> object. - A reference-replacement Ref<T> class similarly holds a 4-byte int, it implements operator& which produces the associated Ptr<T> object, and it also provides an operator T& () conversion which dereferences the object from the deque. - With these, I tried a custom traits struct looking like this: value_type = node := T node_ptr = pointer := Ptr<T> reference := Ref<T> Problems: Even though intrusive data structures are designed with the stated goal of leaving memory management to the user, intrusive lists&trees do allocate one extra node object that they use as "header". The code then takes the address (&) of this node and uses it in comparisons as a node_ptr. Because of this, my custom traits above could not compile. The only way I could find to make such containers work for my needs is basically a hack: define "node" to be a "pointer holder" object (neither member nor base of "value"), that allocates a "value" struct from the deque upon construction, that responds to operator& by returning the held pointer, and that otherwise acts as a value&. From what I could gather reading the docs, boost::intrusive containers allow some type of customization via the traits structs. However, I see some drawbacks: A. The traits classes seem to be there to support 2 existing customization types, namely the situation where "node" is a base class of "value" (implementing "base hooks") and the situation where "node" is a member of "value" (implementing "member hooks"). My situation represents a 3rd customization type. B. Even though the traits classes allow one to specify pointer types, it's possible (?) that under the hood the classes were designed to support only raw pointers and smart pointers, not the indirect offset-like pointers I need. Given A&B, it seems to me that in my customization I would need 2 different hacks. In the interest of code stability, I started wondering whether it is feasible to adapt existing boost::intrusive data to my needs (my first instinct) as opposed to simply rolling out my own rbtree. Questions: 0. Obviously: Have you seen a similar situation being dealt with before? Maybe there's an existing solution out there. My reluctance to rolling out my own intrusive rbtrees is due to the fact I'd have to test them, as opposed to using a known implementation. 1. Are boost::intrusive data structures supposed to support custom pointer classes (neither real pointers nor smart pointers)? For instance, in 1.46 I found this code in boost/intrusive/detail/tree_algorithms.hpp static node_ptr uncast(const_node_ptr ptr) { return node_ptr(const_cast<node*>( ::boost::intrusive::detail::boost_intrusive_get_pointer(ptr))); } So despite all the custom traits structs defining node_ptr and const_node_ptr, under the hood you have a line of code which assumes node_ptr can be constructed from node*. This is the expensive real-pointer to offset-pointer no-no I mentioned earlier. However, intrusive lists worked just fine in 1.46, which suggests this was simply a bug. 2. Can you point me to an example of defining and using custom pointer class with boost::intrusive? To enable compilation (of lists only) in 1.46, I had to customize std::iterator_traits (that part I understood), but then also boost::pointer_to_other and boost::intrusive::detail::smart_ptr_type. Even though the code compiled, I don't know what those are doing exactly, so I'm weary of them. 3. In 1.55, I have a few more pages of errors, I think mainly due to these pointer customization issues I don't fully understand. Something seems to have changed from 1.46 to 1.55. Is there a reference about what changed? Or is there a portable way of rolling out such a custom pointer class? Many thanks, M