Recursive Boost.Intrusive containers

| Home | Libraries | People | FAQ | More

## Recursive Boost.Intrusive containers

Boost.Intrusive containers can be used to define recursive structures very easily, allowing complex data structures with very low overhead. Let's see an example:

    #include <boost/intrusive/list.hpp>
    #include <cassert>

    using namespace boost::intrusive;

    typedef list_base_hook<> BaseHook;

    //A recursive class
    class Recursive : public BaseHook
    {
       private:
       Recursive(const Recursive&);
       Recursive & operator=(const Recursive&);

       public:
       Recursive() : BaseHook(), children(){}
       list< Recursive, base_hook<BaseHook> > children;
    };

    int main()
    {
       Recursive f, f2;
       //A recursive list of Recursive
       list< Recursive, base_hook<BaseHook> > l;

       //Insert a node in parent list
       l.insert(l.begin(), f);

       //Insert a node in child list
       l.begin()->children.insert(l.begin()->children.begin(), f2);

       //Objects properly inserted
       assert(l.size() == l.begin()->children.size());
       assert(l.size() == 1);

       //Clear both lists
       l.begin()->children.clear();
       l.clear();
       return 0;
    }

Recursive data structures using Boost.Intrusive containers must avoid using hook deduction to avoid early type instantiation:

    //This leads to compilation error (Recursive is instantiated by
    //'list' to deduce hook properties (pointer type, tag, safe-mode...)
    class Recursive
    {  //...

       list< Recursive > l;
       //...
    };

    //Ok, programmer must specify the hook type to avoid early Recursive instantiation
    class Recursive
    {  //...
       list< Recursive, base_hook<BaseHook> > l;
       //...
    };

Member hooks are not suitable for recursive structures:

    class Recursive
    {
       private:
       Recursive(const Recursive&);
       Recursive & operator=(const Recursive&);

       public:
       list_member_hook<> memhook;
       list< Recursive, member_hook<Recursive, list_member_hook<>, &Recursive::memhook> > children;
    };

Specifying `&Recursive::memhook` (that is, the offset between memhook and Recursive) provokes an early instantiation of `Recursive`. To define recursive structures using member hooks, a programmer should use `function_hook`:

    #include <boost/intrusive/list.hpp>
    #include <boost/intrusive/parent_from_member.hpp>

    using namespace boost::intrusive;

    class Recursive;

    //Declaration of the functor that converts betwen the Recursive
    //class and the hook
    struct Functor
    {
       //Required types
       typedef list_member_hook<>    hook_type;
       typedef hook_type*            hook_ptr;
       typedef const hook_type*      const_hook_ptr;
       typedef Recursive             value_type;
       typedef value_type*           pointer;
       typedef const value_type*     const_pointer;

       //Required static functions
       static hook_ptr to_hook_ptr (value_type &value);
       static const_hook_ptr to_hook_ptr(const value_type &value);
       static pointer to_value_ptr(hook_ptr n);
       static const_pointer to_value_ptr(const_hook_ptr n);
    };

    //Define the recursive class
    class Recursive
    {
       private:
       Recursive(const Recursive&);
       Recursive & operator=(const Recursive&);

       public:
       Recursive() : hook(), children() {}
       list_member_hook<> hook;
       list< Recursive, function_hook< Functor> > children;
    };

    //Definition of Functor functions
    inline Functor::hook_ptr Functor::to_hook_ptr (Functor::value_type &value)
       {  return &value.hook; }
    inline Functor::const_hook_ptr Functor::to_hook_ptr(const Functor::value_type &value)
       {  return &value.hook; }
    inline Functor::pointer Functor::to_value_ptr(Functor::hook_ptr n)
       {  return get_parent_from_member<Recursive>(n, &Recursive::hook);  }
    inline Functor::const_pointer Functor::to_value_ptr(Functor::const_hook_ptr n)
       {  return get_parent_from_member<Recursive>(n, &Recursive::hook);  }

    int main()
    {
       Recursive f, f2;
       //A recursive list of Recursive
       list< Recursive, function_hook< Functor> > l;

       //Insert a node in parent list
       l.insert(l.begin(), f);

       //Insert a node in child list
       l.begin()->children.insert(l.begin()->children.begin(), f2);

       //Objects properly inserted
       assert(l.size() == l.begin()->children.size());
       assert(l.size() == 1);

       //Clear both lists
       l.begin()->children.clear();
       l.clear();
       return 0;
    }