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