Boost C++ Libraries Home Libraries People FAQ More

PrevUpHomeNext

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;
}

PrevUpHomeNext