...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.
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);
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);
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; }
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: