On 3/19/07, Ion Gaztañaga <igaztanaga@gmail.com> wrote:
The same happens with Intrusive. The user derives or stores a hook to make the class intrusive-friendly. The hook contains a minimum generic node that just stores pointers. All the low-level (link, unlink, rebalance...) algorithms operate with these minimal nodes to avoid instantiating algorithms for all user types.
Ion, does this version of Intrusive have functionality that would allow me to adapt existing classes (i.e. a non-intrusive way to provide Boost.Intrusive functionality)? I think this could be accomplished using a mechanism similar to iterator traits classes. A user would simply need to specialize a boost::intrusive::list::node_traits class. This was how I went about it when I coded an intrusive n-ary tree. It looked something like (simplified): template <typename T> struct nary_treenode_traits { static T *&parent(T &node); static T *&prev(T &node); static T *&next(T &node); static T *&first_child(T &node); static T *&last_child(T &node); // const versions too... }; And then all of my node operations went through the traits class. E.g. template <typename T> T *&parent_node(T &node) { typedef nary_treenode_traits<T> traits_type; return traits_type::parent(node); } This allows implementations where the user takes advantage of platform specific knowledge to store extra information within one pointer (linked list with next/prev pointer in the same pointer with xor to extract), as well as more commonly, existing pointers that might simply be named something different than what the generic algorithm expected. It appears that my implementation, yours, and the Generic Tree GSoC project from last year all had similar goals in trying to provide generic algorithms that only rely on certain capabilities of the input type (e.g. must have next/prev to be used as a linked list node, or must have parent to be a tree node). --Michael Fawcett