Boost C++ Libraries

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