How to use Boost.Intrusive

Using base hooks
Using member hooks
Using both hooks
Object lifetime

If you plan to insert a class in an intrusive container, you have to make some decisions influencing the class definition itself. Each class that will be used in an intrusive container needs some appropriate data members storing the information needed by the container. We will take a simple intrusive container, the intrusive list (boost::intrusive::list), for the following examples, but all Boost.Intrusive containers are very similar. To compile the example using boost::intrusive::list, just include:

#include <boost/intrusive/list.hpp>

Every class to be inserted in an intrusive container, needs to contain a hook that will offer the necessary data and resources to be insertable in the container. With Boost.Intrusive you just choose the hook to be a public base class or a public member of the class to be inserted. Boost.Intrusive also offers more flexible hooks for advanced users, as explained in the chapter Using function hooks, but usually base or member hooks are good enough for most users.

Using base hooks

For list, you can publicly derive from list_base_hook.

template <class ...Options>
class list_base_hook;

The class can take several options. Boost.Intrusive classes receive arguments in the form option_name<option_value>. You can specify the following options:

tag<class Tag>: this argument serves as a tag, so you can derive from more than one list_base_hook and hence put an object in multiple intrusive lists at the same time. An incomplete type can serve as a tag. If you specify two base hooks, you must specify a different tag for each one. Example: list_base_hook< tag<tag1> >. If no tag is specified a default one will be used (more on default tags later).
link_mode<link_mode_type LinkMode>: The second template argument controls the linking policy. Boost.Intrusive currently supports 3 modes: normal_link, safe_link and auto_unlink. By default, safe_link mode is used. More about these in sections Safe hooks and Auto-unlink hooks. Example: list_base_hook< link_mode<auto_unlink> >
void_pointer<class VoidPointer>: this option is the pointer type to be used internally in the hook. The default value is void *, which means that raw pointers will be used in the hook. More about this in the section titled Using smart pointers with Boost.Intrusive containers. Example: list_base_hook< void_pointer< my_smart_ptr<void> >

For the following examples, let's forget the options and use the default values:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

class Foo
   //Base hook with default tag, raw pointers and safe_link mode
   :  public list_base_hook<>
{ /**/ };

After that, we can define the intrusive list:

template <class T, class ...Options>
class list;

list receives the type to be inserted in the container (T) as the first parameter and optionally, the user can specify options. We have 3 option types:

base_hook<class Hook> / member_hook<class T, class Hook, Hook T::* PtrToMember> / value_traits<class ValueTraits>: All these options specify the relationship between the type T to be inserted in the list and the hook (since we can have several hooks in the same T type). member_hook will be explained a bit later and value_traits will be explained in the Containers with custom ValueTraits section. If no option is specified, the container will be configured to use the base hook with the default tag. Some options configured for the hook (the type of the pointers, link mode, etc.) will be propagated to the container.
constant_time_size<bool Enabled>: Specifies if a constant time size() function is demanded for the container. This will instruct the intrusive container to store an additional member to keep track of the current size of the container. By default, constant-time size is activated.
size_type<class SizeType>: Specifies an unsigned type that can hold the size of the container. This type will be the type returned by list.size() and the type stored in the intrusive container if constant_time_size<true> is requested. The user normally will not need to change this type, but some containers can have a size_type that might be different from std::size_t (for example, STL-like containers use the size_type defined by their allocator). Boost.Intrusive can be used to implement such containers specifying the type of the size. By default the type is std::size_t.

Example of a constant-time size intrusive list that will store Foo objects, using the base hook with the default tag:

typedef list<Foo> FooList;

Example of an intrusive list with non constant-time size that will store Foo objects:

typedef list<Foo, constant_time_size<false> > FooList;

Remember that the user must specify the base hook in the container declaration if the base hook has no default tag, because that usually means that the type has more than one base hook, and a container shall know which hook will be using:

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

struct my_tag1;
struct my_tag2;

typedef list_base_hook< tag<my_tag1> > BaseHook;
typedef list_base_hook< tag<my_tag2> > BaseHook2;
class Foo   :  public BaseHook, public BaseHook2
{ /**/ };

typedef list< Foo, base_hook<BaseHook>  > FooList;
typedef list< Foo, base_hook<BaseHook2> > FooList2;

Once the list is defined, we can use it:

//An object to be inserted in the list
Foo foo_object;
FooList list;

list.push_back(object);

assert(&list.front() == &foo_object);

Using member hooks

Sometimes an 'is-a' relationship between list hooks and the list value types is not desirable. In this case, using a member hook as a data member instead of 'disturbing' the hierarchy might be the right way: you can add a public data member list_member_hook<...> to your class. This class can be configured with the same options as list_base_hook except the option tag:

template <class ...Options>
class list_member_hook;

Example:

#include <boost/intrusive/list.hpp>

class Foo
{
   public:
   list_member_hook<> hook_;
   //...
};

When member hooks are used, the member_hook option is used to configure the list:

//This option will configure "list" to use the member hook
typedef member_hook<Foo, list_member_hook<>, &Foo::hook_> MemberHookOption;

//This list will use the member hook
typedef list<Foo, MemberHookOption> FooList;

Now we can use the container:

//An object to be inserted in the list
Foo foo_object;
FooList list;

list.push_back(object);

assert(&list.front() == &foo_object);

However, member hooks have some implementation limitations: If there is a virtual inheritance relationship between the parent and the member hook, then the distance between the parent and the hook is not a compile-time fixed value so obtaining the address of the parent from the member hook is not possible without reverse engineering compiler produced RTTI. Apart from this, the non-standard pointer to member implementation for classes with complex inheritance relationships in MSVC ABI compatible-compilers is not supported by member hooks since it also depends on compiler-produced RTTI information.

Using both hooks

You can insert the same object in several intrusive containers at the same time, using one hook per container. This is a full example using base and member hooks:

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

using namespace boost::intrusive;

class MyClass : public list_base_hook<>
{
   int int_;

   public:
   list_member_hook<> member_hook_;

   MyClass(int i) :  int_(i)  {}
};

//Define a list that will store MyClass using the base hook
typedef list<MyClass> BaseList;

//Define a list that will store MyClass using the member hook
typedef member_hook
   < MyClass, list_member_hook<>, &MyClass::member_hook_> MemberOption;
typedef list<MyClass, MemberOption> MemberList;

int main()
{
   typedef std::vector<MyClass>::iterator VectIt;

   //Create several MyClass objects, each one with a different value
   std::vector<MyClass> values;
   for(int i = 0; i < 100; ++i)  values.push_back(MyClass(i));

   BaseList baselist;
   MemberList memberlist;

   //Now insert them in the reverse order in the base hook list
   for(VectIt it(values.begin()), itend(values.end())
      ; it != itend  ; ++it){
      baselist.push_front(*it);
   }

   //Now insert them in the same order as in vector in the member hook list
   for(VectIt it(values.begin()), itend(values.end()); it != itend; ++it)
      memberlist.push_back(*it);

   //Now test lists
   {
      BaseList::reverse_iterator rbit(baselist.rbegin());
      MemberList::iterator mit(memberlist.begin());
      VectIt  it(values.begin()), itend(values.end());

      //Test the objects inserted in the base hook list
      for(; it != itend; ++it, ++rbit)
         if(&*rbit != &*it)   return 1;

      //Test the objects inserted in the member hook list
      for(it = values.begin(); it != itend; ++it, ++mit)
         if(&*mit != &*it)    return 1;
   }

   return 0;
}

Object lifetime

Even if the interface of list is similar to std::list, its usage is a bit different: You always have to keep in mind that you directly store objects in intrusive containers, not copies. The lifetime of a stored object is not bound to or managed by the container:

When the container gets destroyed before the object, the object is not destroyed, so you have to be careful to avoid resource leaks.
When the object is destroyed before the container, your program is likely to crash, because the container contains a pointer to an non-existing object.