intrusive.qbk

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

*  Every time an object is inserted in the intrusive container, the container
   checks if the hook is in the well-known default state. If not,
   an assertion is raised.

*  Every time an object is being erased from the intrusive container, the container
   puts the erased object in the well-known default state.

With these features, without any external reference the user can know if the object
has been inserted in a container by calling the `is_linked()` member function.
If the object is not actually inserted 
in a container, the hook is in the default state, and if it is inserted in a container, the
hook is not in the default state.

[endsect]

[section:configuring Configuring safe-mode assertions]

By default, all safe-mode assertions raised by [*Boost-Intrusive] hooks
and containers in are implemented using `BOOST_ASSERT`, which can be configured by
the user. See [@http://www.boost.org/libs/utility/assert.html] for more
information about `BOOST_ASSERT`.

`BOOST_ASSERT` is globally configured, so the user might
want to redefine intrusive safe-mode assertions without modifying the global
`BOOST_ASSERT`. This can be achieved redefining the following macros:

*  `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT`: This assertion will be
   used in insertion functions of the intrusive containers to check that
   the hook of the value to be inserted is default constructed.
*  `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`: This assertion will be
   used in hooks' destructors to check that the hook is in a default state.

If any of these macros is not redefined, the assertion will default to `BOOST_ASSERT`.
If `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT` or `BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT`
is defined and the programmer needs to include a file to configure that assertion, it can define
`BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE` or `BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT_INCLUDE`
with the name of the file to include:

[c++]

   #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT          MYASSERT
   #define BOOST_INTRUSIVE_SAFE_HOOK_DESTRUCTOR_ASSERT_INCLUDE <myassert.h>

[endsect]

[endsect]

[section:auto_unlink_hooks Auto-unlink hooks]

[section:auto_unlink_hooks_what What's an auto-unlink hook?]

[*Boost.Intrusive] offers additional hooks with unique features:

*  When the destructor of the hook is called, the hook checks if the node is inserted
   in a container. If so, the hook removes the node from the container.
*  The hook has a member function called `unlink()` that can be used to unlink the
   node from the container at any time, without having any reference to the container,
   if the user wants to do so.

These hooks have exactly the same size overhead as their analog non auto-unlinking
hooks, but they have a restriction: they can only be used with
[link intrusive.presenting_containers non-constant time containers].
There is a reason for this: 

* Auto-unlink hooks don't store any reference to the container where they are inserted.
* Only containers with non constant-time `size()` allow removing an object from the container
  without referring to the container. 

This auto-unlink feature is useful in certain applications
but it must be used [*very carefuly]:

*  If several threads are using the same container the destructor of the auto-unlink
   hook will be called without any thread synchronization so removing the object is
   thread-unsafe.

*  Container contents change silently without modifying the container directly.
   This can lead to surprising effects.

These auto-unlink hooks have also safe-mode properties:

*  Hooks' constructors put the hook in a well-known default state.

*  Every time an object is inserted in the intrusive container, the container
   checks if the hook is in the well-known default state. If not,
   an assertion is raised.

*  Every time an object is erased from an intrusive container, the container
   puts the erased object in the well-known default state.

[endsect]

[section:auto_unlink_hooks_example Auto-unlink hook example]

Let's see an example of an auto-unlink hook:

[import ../example/doc_auto_unlink.cpp]
[doc_auto_unlink_code]

[endsect]

[section:auto_unlink_and_constant_time Auto-unlink hooks and containers with constant-time `size()`]

As explained, [*Boost.Intrusive] auto-unlink hooks are incompatible with containers
that have constant-time `size()`, so if you try to define such container with an
auto-unlink hook's value_traits, you will get a static assertion:

[c++]
   
   #include <boost/intrusive/list.hpp>

   using boost::intrusive;

   struct MyTag;

   class MyClass : public list_base_hook< link_mode<auto_unlink> >
   {/**/};

   list <MyClass, constant_time_size<true> > bad_list;

   int main()
   {
      bad_list list;
      return 0;
   }

leads to an error similar to:

[pre
  error : use of undefined type 'boost::STATIC_ASSERTION_FAILURE<false>'
]

Pointing to code like this:

[c++]

   //Constant-time size is incompatible with auto-unlink hooks!
   BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink)));

This way, there is no way to compile a program if you try to use auto-unlink hooks
in constant-time size containers.

[endsect]

[endsect]

[section:slist Intrusive singly linked list: slist]

[classref boost::intrusive::slist slist] is the simplest intrusive container of
[*Boost.Intrusive]: a singly linked list. The memory overhead
it imposes is 1 pointer per node. The size of an empty, non constant-time size 
[classref boost::intrusive::slist slist] is the size of 1 pointer. This
lightweight memory overhead comes with drawbacks, though: many operations have
linear time complexity, even some that usually are constant time, like
[classref boost::intrusive::slist::swap swap]. [classref boost::intrusive::slist slist]
only provides forward iterators.

For most cases, a doubly linked list is preferrable because it offers more
constant-time functions with a slightly bigger size overhead.
However, for some applications like
constructing more elaborate containers, singly linked lists are essential
because of their low size overhead.

[section:slist_hooks slist hooks]

Like the rest of [*Boost.Intrusive] containers,
[classref boost::intrusive::slist slist] has two hook types:

[c++]

   template <class ...Options>
   class slist_base_hook;

*  [classref boost::intrusive::slist_base_hook slist_base_hook]:
   the user class derives publicly from
   [classref boost::intrusive::slist_base_hook slist_base_hook] to make
   it [classref boost::intrusive::slist slist]-compatible.

[c++]

   template <class ...Options>
   class slist_member_hook;

*  [classref boost::intrusive::slist_member_hook slist_member_hook]:
   the user class contains a public 
   [classref boost::intrusive::slist_member_hook slist_member_hook] to make
   it [classref boost::intrusive::slist slist]-compatible.

[classref boost::intrusive::slist_base_hook slist_base_hook] and
[classref boost::intrusive::slist_member_hook slist_member_hook]
receive the same options explained in
the section [link intrusive.usage How to use Boost.Intrusive]:

*  [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
   so you can derive from more than one slist hook.
   Default: `tag<default_tag>`.

*  [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
   Default: `link_mode<safe_link>`.

*  [*`void_pointer<class VoidPointer>`]: The pointer type to be used
   internally in the hook and propagated to the container.
   Default: `void_pointer<void*>`.

[endsect]

[section:slist_container slist container]

[c++]

   template <class T, class ...Options>
   class slist;

[classref boost::intrusive::slist slist] receives the options explained in
the section [link intrusive.usage How to use Boost.Intrusive]:

*  [*`base_hook<class Hook>`] / [*`member_hook<class T, class Hook, Hook T::* PtrToMember>`] / 
   [*`value_traits<class ValueTraits>`]: To specify the hook type or value traits used
   to configure the container. (To learn about value traits go to the section
   [link intrusive.value_traits Containers with custom ValueTraits].)

*  [*`constant_time_size<bool Enabled>`]: To activate the constant-time `size()` operation.
   Default: `constant_time_size<true>`

*  [*`size_type<bool Enabled>`]: To specify the type that will be used to store the size
   of the container. Default: `size_type<std::size_t>`.

[classref boost::intrusive::slist slist] can receive additional options:

*  [*`linear<bool Enable>`]: the singly linked list is implemented as a
   null-terminated list instead of a circular list. This allows `O(1)` swap,
   but losses some operations like `container_from_end_iterator`.
*  [*`cache_last<bool Enable>`]: the singly linked also stores a pointer to the
   last element of the singly linked list. This allows `O(1)` swap,
   `splice_after(iterator, slist &)` and makes the list offer new functions
   like `push_back(reference)` and `back()`. Logically, the size an empty list is
   increased in `sizeof(void_pointer)` and the the cached last node pointer must
   be updated in every operation, and that might incur in a slight performance impact.

`auto_unlink` hooks are not usable if `linear<true>` and/or `cache_last<true>` options are
used. If `auto_unlink` hooks are used and those options are specified, a static
assertion will be raised.

[endsect]

[section:slist_example Example]

Now let's see a small example using both hooks:

[import ../example/doc_slist.cpp]
[doc_slist_code]

[endsect]

[endsect]

[section:list Intrusive doubly linked list: list]

[classref boost::intrusive::list list] is a doubly linked list. The memory overhead
it imposes is 2 pointers per node. An empty, non constant-time size [classref boost::intrusive::list list]
also has the size of 2 pointers. [classref boost::intrusive::list list]
has many more constant-time operations than [classref boost::intrusive::slist slist]
and provides a bidirectional iterator. It is recommended to use
[classref boost::intrusive::list list] instead of
[classref boost::intrusive::slist slist] if the size overhead is acceptable:

[section:list_hooks list hooks]

Like the rest of [*Boost.Intrusive] containers,
[classref boost::intrusive::list list] has two hook types:

[c++]

   template <class ...Options>
   class list_base_hook;

*  [classref boost::intrusive::list_base_hook list_base_hook]: the user class
   derives publicly from [classref boost::intrusive::list_base_hook list_base_hook]
   to make it [classref boost::intrusive::list list]-compatible.

[c++]

   template <class ...Options>
   class list_member_hook;

*  [classref boost::intrusive::list_member_hook list_member_hook]: 
   the user class contains a public 
   [classref boost::intrusive::list_member_hook list_member_hook] to make
   it [classref boost::intrusive::list list]-compatible.

[classref boost::intrusive::list_base_hook list_base_hook] and
[classref boost::intrusive::list_member_hook list_member_hook] receive
the same options explained in the section
[link intrusive.usage How to use Boost.Intrusive]:

*  [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
   so you can derive from more than one list hook.
   Default: `tag<default_tag>`.

*  [*`link_mode<link_mode_type LinkMode>`]: The linking policy.
   Default: `link_mode<safe_link>`.

*  [*`void_pointer<class VoidPointer>`]: The pointer type to be used
   internally in the hook and propagated to the container.
   Default: `void_pointer<void*>`.

[endsect]

[section:list_container list container]

[c++]