intrusive RBLTree

[crusader-mike]

(For reasons outside of this question) I need to build an intrusive RB tree where:

• elements automatically remove themselves from the tree in their drop implementation
• iterating over rb tree produces a sequence of Rc\<T> elements (i.e. if I got cursor to point to an element -- that element will stay alive until cursor moves on)
• this rb tree is an equivalent of C++ multiset\<T> (i.e. multiple elements with the same key are allowed)

Is it possible to do this with intrusive_collections::rbtree::RBTree?

[Amanieu]

Yes for points 2 and 3. However for point 1 that is not possible, You need a mutable reference to the RBTree itself to remove an element from it. Consider the case where this is the last element in the tree: you need to be able to update the RBTree itself to set its root node pointer to null.

[crusader-mike]

I am not sure about rbtree implementation, but in theory it shouldn't be a problem -- just like in case of a keyring (double-linked list with special null node) removing last element will simply make null node it's own neighbor...