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<bool Enabled>: Specifies a 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 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 a 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 if the base hook has no default tag (e.g: if more than one base hook is used):

#include <boost/intrusive/list.hpp>

using namespace boost::intrusive;

struct my_tag;

typedef list_base_hook< tag<my_tag> > BaseHook;
class Foo   :  public BaseHook
{ /**/ };

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

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

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;
   typedef std::vector<MyClass>::reverse_iterator VectRit;

   //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()), rbitend(baselist.rend());
      MemberList::iterator mit(memberlist.begin()), mitend(memberlist.end());
      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.