...one of the most highly
regarded and expertly designed C++ library projects in the
world.
— Herb Sutter and Andrei
Alexandrescu, C++
Coding Standards
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; }