intrusive.qbk

来自「Boost provides free peer-reviewed portab」· QBK 代码 · 共 1,560 行 · 第 1/5 页

[/
 / Copyright (c) 2007 Ion Gaztanaga
 /
 / Distributed under the Boost Software License, Version 1.0. (See accompanying
 / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
 /]

[library Boost.Intrusive
    [quickbook 1.3]
    [authors [Krzikalla, Olaf], [Gaztañaga, Ion]]
    [copyright 2005 Olaf Krzikalla, 2006-2007 Ion Gaztañaga]
    [id intrusive]
    [dirname intrusive]
    [purpose Intrusive containers]
    [license
        Distributed under the Boost Software License, Version 1.0.
        (See accompanying file LICENSE_1_0.txt or copy at
        [@http://www.boost.org/LICENSE_1_0.txt])
    ]
]

[section:introduction Introduction]

[section:introduction_presenting Presenting Boost.Intrusive]

[*Boost.Intrusive] is a library presenting some intrusive containers to
the world of C++. Intrusive containers are special containers
that offer [link intrusive.performance better performance]
and exception safety guarantees than non-intrusive containers (like STL containers). 

The performance benefits of intrusive containers makes them ideal as a building
block to efficiently construct complex containers like multi-index containers or
to design high performance code like memory allocation algorithms.

While intrusive containers were and are widely used in C, they
became more and more forgotten in C++ due to the presence of the standard
containers which don't support intrusive techniques.[*Boost.Intrusive] not only
reintroduces this technique to C++, but also encapsulates the implementation in
STL-like interfaces. Hence anyone familiar with standard containers can easily use
[*Boost.Intrusive].

[endsect]

[section:introduction_building_intrusive Building Boost.Intrusive]

There is no need to compile anything to use [*Boost.Intrusive], since it's
a header only library. Just include your Boost header directory in your
compiler include path.

[endsect]

[endsect]

[section:intrusive_vs_nontrusive Intrusive and non-intrusive containers]

[section:differences_intrusive_vs_nontrusive Differences between intrusive and non-intrusive containers]

The main difference between intrusive containers and non-intrusive containers is
that in C++ non-intrusive containers store [*copies] of values passed by the user.
Containers use the `Allocator` template parameter to allocate the stored values:

[c++]

   #include <list>
   #include <assert.h>

   int main()
   {
      std::list<MyClass> myclass_list;

      MyClass myclass(...);
      myclass_list.push_back(myclass);

      //The stored object is different from the original object
      assert(&myclass != &myclass_list.front());
      return 0;
   }


To store the newly allocated copy of `myclass`, the container needs additional
data: `std::list` usually allocates nodes that contain pointers to the
next and previous node and the value itself. Something similar to:

[c++]

   //A possible implementation of a std::list<MyClass> node
   class list_node
   {
      list_node *next;
      list_node *previous;
      MyClass    value; 
   };


On the other hand, an intrusive container does not store copies of passed objects,
but it stores the objects themselves. The additional data needed to insert the object
in the container must be provided by the object itself. For example, to insert `MyClass`
in an intrusive container that implements a linked list, `MyClass` must contain the
needed ['next] and ['previous] pointers:

[c++]

   class MyClass
   {
      MyClass *next;
      MyClass *previous;
      //Other members...
   };

   int main()
   {
      acme_intrusive_list<MyClass> list;

      MyClass myclass;
      list.push_back(myclass);

      //"myclass" object is stored in the list
      assert(&myclass == &list.front());
      return 0;
   }

As we can see, knowing which additional data the class should contain is not
an easy task. [*Boost.Intrusive] offers several intrusive containers and an easy
way to make user classes compatible with those containers.

[endsect]

[section:properties_of_intrusive Properties of Boost.Intrusive containers]

Semantically, a [*Boost.Intrusive] container is similar to a STL container 
holding pointers to objects. That is, if you have an intrusive list holding
objects of type `T`, then `std::list<T*>` would allow you to do quite the
same operations (maintaining and navigating a set of objects of type T and
types derived from it). 

A non-intrusive container has some limitations:

*  An object can only belong to one container: If you want to share an object
   between two containers, you either have to store multiple copies of those
   objects or you need to use containers of pointers: `std::list<Object*>`.

*  The use of dynamic allocation to create copies of passed values can be a performance
   and size bottleneck in some applications. Normally, dynamic allocation imposes
   a size overhead for each allocation to store bookkeeping information and a
   synchronization to protected concurrent allocation from different threads.

*  Only copies of objects are stored in non-intrusive containers. Hence copy
   or move constructors and copy or move assignment operators are required. Non-copyable
   and non-movable objects can't be stored in non-intrusive containers.

*  It's not possible to store a derived object in a STL-container while
   retaining its original type.

Intrusive containers have some important advantages: 

*  Operating with intrusive containers doesn't invoke any memory management at all.
   The time and size overhead associated with dynamic memory can be minimized.

*  Iterating an Intrusive container needs less memory accesses than the semantically
   equivalent container of pointers: iteration is faster.

*  Intrusive containers offer better exception guarantees than non-intrusive containers.
   In some situations intrusive containers offer a no-throw guarantee that can't be 
   achieved with non-intrusive containers.

*  The computation of an iterator to an element from a pointer or reference to that element
   is a constant time operation (computing the position of `T*` in a `std::list<T*>` has
   linear complexity).

*  Intrusive containers offer predictability when inserting and erasing objects since no
   memory management is done with intrusive containers. Memory management usually is not a predictable
   operation so complexity guarantees from non-intrusive containers are looser than the guarantees
   offered by intrusive containers.

Intrusive containers have also downsides:

*  Each type stored in an intrusive container needs additional memory holding the 
   maintenance information needed by the container. Hence, whenever a certain type will
   be stored in an intrusive container [*you have to change the definition of that type]
   appropriately. Although this task is easy with [*Boost.Intrusive], touching the 
   definition of a type is sometimes a crucial issue.

*  In intrusive containers you don't store a copy of an object, [*but rather the original object
   is linked with other objects in the container]. Objects don't need copy-constructors or assignment
   operators to be stored in intrusive containers. But you have to take care of possible side effects, 
   whenever you change the contents of an object (this is especially important for 
   associative containers).

*  The user [*has to manage the lifetime of inserted objects] independently from the
   containers.

*  Again you have to be [*careful]: in contrast to STL containers [*it's easy to render an
   iterator invalid] without touching the intrusive container directly, because the object
   can be disposed before is erased from the container.

*  [*Boost.Intrusive] containers are [*non-copyable and non-assignable]. Since intrusive
   containers don't have allocation capabilities, these operations make no sense. However,
   swapping can be used to implement move capabilities. To ease the implementation of
   copy constructors and assignment operators of classes storing [*Boost.Intrusive]
   containers, [*Boost.Intrusive] offers special cloning functions. See
   [link intrusive.clone_from Cloning [*Boost.Intrusive] containers] section for more information.

*  Analyzing the thread safety of a program that uses containers is harder with intrusive containers, because
   the container might be modified indirectly without an explicit call to a container member.

[table Summay of intrusive containers advantages and disadvantages
    [[Issue]                                                                     [Intrusive]                         [Non-intrusive]]
    [[Memory management]                                                         [External]                          [Internal through allocator]]
    [[Insertion/Erasure time]                                                    [Faster]                            [Slower]]
    [[Memory locality]                                                           [Better]                            [Worse]]
    [[Can hold non-copyable and non-movable objects by value]                    [Yes]                               [No]]
    [[Exception guarantees]                                                      [Better]                            [Worse]]
    [[Computation of iterator from value]                                        [Constant]                          [Non-constant]]
    [[Insertion/erasure predictability]                                          [High]                              [Low]]
    [[Memory use]                                                                [Minimal]                           [More than minimal]]
    [[Insert objects by value retaining polymorphic behavior]                    [Yes]                               [No (slicing)]]
    [[User must modify the definition of the values to insert]                   [Yes]                               [No]]
    [[Containers are copyable]                                                   [No]                                [Yes]]
    [[Inserted object's lifetime managed by]                                     [User (more complex)]               [Container (less complex)]]
    [[Container invariants can be broken without using the container]            [Easier]                            [Harder (only with containers of pointers)]]
    [[Thread-safety analysis]                                                    [Harder]                            [Easier]]
]

For a performance comparison between Intrusive and Non-intrusive containers see
[link intrusive.performance Performance] section.

[endsect]

[endsect]

[section:usage How to use Boost.Intrusive]

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
([classref boost::intrusive::list boost::intrusive::list]), for the following
examples, but all [*Boost.Intrusive] containers are very similar. To compile
the example using [classref boost::intrusive::list boost::intrusive::list],
just include:

[c++]

   #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.

[section:usage_base_hook Using base hooks]

For [classref boost::intrusive::list list], you can publicly derive from 
[classref boost::intrusive::list_base_hook list_base_hook].

[c++]

   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
   [classref boost::intrusive::list_base_hook 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
   [link intrusive.safe_hook Safe hooks] and [link intrusive.auto_unlink_hooks 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
   [link intrusive.using_smart_pointers 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:

[c++]

   #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:

[c++]

   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 
   [link intrusive.value_traits Containers with custom ValueTraits] section.