intrusive.qbk

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

   [*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, contant-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:

[c++]

   typedef list<Foo> FooList;

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

[c++]

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

[c++]

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

[c++]

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

   list.push_back(object);

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

[endsect]

[section:usage_member_hook 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`:

[c++]

   template <class ...Options>
   class list_member_hook;

Example:

[c++]

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

[c++]

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

[c++]

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

   list.push_back(object);

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

[endsect]

[section:usage_both_hooks 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:

[import ../example/doc_how_to_use.cpp]
[doc_how_to_use_code]

[endsect]

[section:usage_lifetime Object lifetime]

Even if the interface of [classref boost::intrusive::list 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.

[endsect]

[endsect]

[section:usage_when When to use?]

Intrusive containers can be used for highly optimized algorithms, where speed is a crucial
issue and:

*  additional memory management should be avoided.
*  the programmer needs to efficiently track the construction and destruction of objects.
*  exception safety, especially the no-throw guarantee, is needed.
*  the computation of an iterator to an element from a pointer or reference
   to that element should be a constant time operation.
*  it's important to achieve a well-known worst-time system response.
*  localization of data (e.g. for cache hit optimization) leads to measureable effects.

The last point is important if you have a lot of containers over a set of elements. E.g. if 
you have a vector of objects (say, `std::vector<Object>`), and you also have a list
storing a subset of those objects (`std::list<Object*>`), then operating on an Object
from the list iterator (`std::list<Object*>::iterator`) requires two steps:

*  Access from the iterator (usually on the stack) to the list node storing a pointer to `Object`.
*  Access from the pointer to `Object` to the Object stored in the vector.

While the objects themselves are tightly packed in the memory of the vector
(a vector's memory is guaranteed to be contiguous), and form something
like a data block, list nodes may be dispersed in the heap memory.
Hence depending on your system you might get a lot of cache misses. The same doesn't hold
for an intrusive list. Indeed, dereferencing an iterator from an intrusive list is performed in
the same two steps as described above. But the list node is already embedded in the Object, so
the memory is directly tracked from the iterator to the Object. 

It's also possible to use intrusive containers when the objects to be stored can
have different or unknown size. This allows storing base and derived objects
in the same container, as shown in the following example: 

[import ../example/doc_window.cpp]
[doc_window_code]

Due to certain properties of intrusive containers 
they are often more difficult to use than their STL-counterparts. That's why you
should avoid them in public interfaces of libraries. Classes to be stored in intrusive
containers must change their implementation to store the hook and this is not always
possible or desirable.

[endsect]

[section:concepts_summary Concept summary]

Here is a small summary of the basic concepts that will be used in the following
chapters:

[variablelist Brief Concepts Summary
[[Node Algorithms][A class containing typedefs and static functions that define 
   basic operations that can be applied to a group of nodes. It's independent
   from the node definition and configured using a NodeTraits template
   parameter that describes the node.]]
[[Node Traits][A class that stores basic information and operations to insert a node into a group of nodes.]]
[[Hook][A class that a user must add as a base class or as a member to make the user class compatible with intrusive containers.]]
[[Intrusive Container][A class that stores user classes that have the needed hooks. It takes a ValueTraits template parameter as configuration information.]]
[[Semi-Intrusive Container][Similar to an intrusive container but a semi-intrusive container needs additional memory (e.g. an auxiliary array) to work.]]
[[Value Traits][A class containing typedefs and operations to obtain the node to be used by Node Algorithms from the user class and the inverse.]]
]

[endsect]

[section:presenting_containers Presenting Boost.Intrusive containers]

[*Boost.Intrusive] offers a wide range of intrusive containers:

*  [*slist]: An intrusive singly linked list. The size overhead is very small
   for user classes (usually the size of one pointer) but many operations have linear
   time complexity, so the user must be careful if he wants to avoid performance problems.

*  [*list]: A `std::list` like intrusive linked list. The size overhead is quite
   small for user classes (usually the size of two pointers). Many operations have
   constant time complexity.

*  [*set/multiset/rbtree]: `std::set/std::multiset` like intrusive associative containers
   based on red-black trees.
   The size overhead is moderate for user classes (usually the size of three pointers).
   Many operations have logarithmic time complexity.

*  [*avl_set/avl_multiset/avltree]: A `std::set/std::multiset` like intrusive associative
   containers based on AVL trees.
   The size overhead is moderate for user classes (usually the size of three pointers).
   Many operations have logarithmic time complexity.

*  [*splay_set/splay_multiset/splaytree]: `std::set/std::multiset` like intrusive associative
   containers based on splay trees. Splay trees have no constant operations, but they  
   have some interesting caching properties.
   The size overhead is moderate for user classes (usually the size of three pointers).
   Many operations have logarithmic time complexity.

*  [*sg_set/sg_multiset/sgtree]: A `std::set/std::multiset` like intrusive associative
   containers based on scapegoat trees. Scapegoat can be configured with the desired
   balance factor to achieve the desired rebalancing frequency/search time compromise.
   The size overhead is moderate for user classes (usually the size of three pointers).
   Many operations have logarithmic time complexity.

[*Boost.Intrusive] also offers semi-intrusive containers:

*  [*unordered_set/unordered_multiset]: `std::tr1::unordered_set/std::tr1::unordered_multiset`
   like intrusive unordered associative containers.
   The size overhead is moderate for user classes (an average of two pointers per element).
   Many operations have amortized constant time complexity.

Most of these intrusive containers can be configured with constant or linear time
size:

*  [*Linear time size]: The intrusive container doesn't hold a size member that is
updated with every insertion/erasure. This implies that the `size()` function doesn't have constant
time complexity. On the other hand, the container is smaller, and some operations, like
`splice()` taking a range of iterators in linked lists, have constant time complexity
instead of linear complexity.

*  [*Constant time size]: The intrusive container holds a size member that is updated
with every insertion/erasure. This implies that the `size()` function has constant time
complexity. On the other hand, increases the size of the container, and some operations,
like `splice()` taking a range of iterators, have linear time complexity in linked lists.

To make user classes compatible with these intrusive containers [*Boost.Intrusive]
offers two types of hooks for each container type:

*  [*Base hook]: The hook is stored as a public base class of the user class.

*  [*Member hook]: The hook is stored as a public member of the user class.

Apart from that, [*Boost.Intrusive] offers additional features:

*  [*Safe mode hooks]: Hook constructor initializes the internal data to a well-known
   safe state and intrusive containers check that state before inserting a value in the
   container. When erasing an element from the container, the container puts the hook
   in the safe state again. This allows a safer use mode and it can be used to detect
   programming errors. It implies a slight performance overhead in some operations
   and can convert some constant time operations to linear time operations.

*  [*Auto-unlink hooks]: The hook destructor removes the object from the container
   automatically and the user can safely unlink the object from the container without
   referring to the container.

*  [*Non-raw pointers]: If the user wants to use smart pointers instead of raw pointers, 
   [*Boost.Intrusive] hooks can
   be configured to use any type of pointer. This configuration information is also
   transmitted to the containers, so all the internal pointers used by intrusive containers
   configured with these hooks will be smart pointers. As an example,
   [*Boost.Interprocess] defines a smart pointer compatible with shared memory,
   called `offset_ptr`. [*Boost.Intrusive] can be configured to use this smart pointer
   to allow shared memory intrusive containers.

[endsect]

[section:safe_hook Safe hooks]

[section:features Features of the safe mode]

[*Boost.Intrusive] hooks can be configured to operate in safe-link mode.
The safe mode is activated by default, but it can be also explicitly activated:

[c++]

   //Configuring the safe mode explicitly
   class Foo : public list_base_hook< link_mode<safe_link> >
   {};

With the safe mode the user can detect if the object
is actually inserted in a container without any external reference. Let's review the basic features of the safe mode:

*  Hook's constructor puts the hook in a well-known default state.

*  Hook's destructor checks if the hook is in the well-known default state. If not,
   an assertion is raised.