intrusive.qbk

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

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

[classref boost::intrusive::list list] receives the same 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>`

[endsect]

[section:list_example Example]

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

[import ../example/doc_list.cpp]
[doc_list_code]

[endsect]

[endsect]

[section:set_multiset Intrusive associative containers: set, multiset, rbtree]

[*Boost.Intrusive] also offers associative containers that can be very useful
when creating more complex associative containers, like containers maintaining
one or more indices with different sorting semantics. Boost.Intrusive associative 
containers, like most STL associative container implemenatations are based on
red-black trees.

The memory overhead of these containers is usually 3 pointers and a bit (with
alignment issues, this means 3 pointers and an integer).
This size can be reduced to 3 pointers if pointers have even alignment
(which is usually true in most systems).

An empty, non constant-time size [classref boost::intrusive::set set],
[classref boost::intrusive::multiset multiset] or
[classref boost::intrusive::rbtree rbtree]
has also the size of 3 pointers and an integer (3 pointers when optimized for size).
These containers have logarithmic complexity in many
operations like
searches, insertions, erasures, etc. [classref boost::intrusive::set set] and
[classref boost::intrusive::multiset multiset] are the
intrusive equivalents of standard `std::set` and `std::multiset` containers.

[classref boost::intrusive::rbtree rbtree] is a superset of 
[classref boost::intrusive::set set] and
[classref boost::intrusive::multiset multiset] containers that offers
functions to insert unique and multiple keys.

[section:set_multiset_hooks set, multiset and rbtree hooks]

[classref boost::intrusive::set set],
[classref boost::intrusive::multiset multiset] and
[classref boost::intrusive::rbtree rbtree] share the same hooks.
This is an advantage, because the same
user type can be inserted first in a [classref boost::intrusive::multiset multiset]
and after that in [classref boost::intrusive::set set] without
changing the definition of the user class.

[c++]

   template <class ...Options>
   class set_base_hook;

*  [classref boost::intrusive::set_base_hook set_base_hook]:
   the user class derives publicly from
   [classref boost::intrusive::set_base_hook set_base_hook] to make
   it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.

[c++]

   template <class ...Options>
   class set_member_hook;

*  [classref boost::intrusive::set_member_hook set_member_hook]:
   the user class contains a public
   [classref boost::intrusive::set_member_hook set_member_hook] to make
   it [classref boost::intrusive::set set]/[classref boost::intrusive::multiset multiset]-compatible.

[classref boost::intrusive::set_base_hook set_base_hook] and
[classref boost::intrusive::set_member_hook set_member_hook] receive
the same options explained in the section
[link intrusive.usage How to use Boost.Intrusive] plus a size optimization option:

*  [*`tag<class Tag>`] (for base hooks only): This argument serves as a tag,
   so you can derive from more than one base 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*>`.

*  [*`optimize_size<bool Enable>`]: The hook will be optimized for size
   instead of speed. The hook will embed the color bit of the red-black
   tree node in the parent pointer if pointer alignment is even.
   In some platforms, optimizing the size might reduce speed performance a bit
   since masking operations will be needed to access parent pointer and color attributes,
   in other platforms this option improves performance due to improved memory locality.
   Default: `optimize_size<false>`.

[endsect]

[section:set_multiset_containers set, multiset and rbtree containers]

[c++]

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

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

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

These containers receive the same 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>`

And they also can receive an additional option:

*  [*`compare<class Compare>`]: Comparison function for the objects to be inserted
   in containers. The comparison functor must induce a strict weak ordering.
   Default: `compare< std::less<T> >`

[endsect]

[section:set_multiset_example Example]

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

[import ../example/doc_set.cpp]
[doc_set_code]

[endsect]

[endsect]

[section:unordered_set_unordered_multiset Semi-Intrusive unordered associative containers: unordered_set, unordered_multiset]

[*Boost.Intrusive] also offers hashed containers that can be very useful to implement
fast-lookup containers.  These containers
([classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset])
are semi-intrusive containers: they need additional memory apart from the hook
stored in the `value_type`. This additional
memory must be passed in the constructor of the container.

Unlike C++ TR1 unordered associative containers (which are also hashed containers),
the contents of these semi-intrusive containers are not rehashed to maintain a
load factor: that would require memory management and intrusive containers don't
implement any memory management at all. However, the user can request an explicit
rehashing passing a new bucket array.
This also offers an additional guarantee over TR1 unordered associative containers:
[*iterators are not invalidated when inserting an element] in the container. 

As with TR1 unordered associative containers, rehashing invalidates iterators,
changes ordering between elements and changes which buckets elements appear in,
but does not invalidate pointers or references to elements. 

Apart from expected hash and equality function objects, [*Boost.Intrusive] unordered
associative containers' constructors take an argument specifying an auxiliary
bucket vector to be used by the container.

[section:unordered_set_unordered_multiset_performance unordered_set and unordered_multiset performance notes]

The size overhead for a hashed container is moderate: 1 pointer per value plus
a bucket array per container. The size of an element of the bucket array
is usually one pointer. To obtain a good performance hashed container,
the bucket length is usually the same as the number of elements that the
container contains, so a well-balanced hashed container (`bucket_count()` is 
equal to `size()` ) will have an equivalent overhead of two pointers per element.

An empty, non constant-time size [classref boost::intrusive::unordered_set unordered_set] or
[classref boost::intrusive::unordered_multiset unordered_multiset]
has also the size of `bucket_count()` pointers. 

Insertions, erasures, and searches, have amortized constant-time complexity in
hashed containers. However, some worst-case guarantees are linear. See
[classref boost::intrusive::unordered_set unordered_set] or
[classref boost::intrusive::unordered_multiset unordered_multiset] for complexity guarantees
of each operation.

[*Be careful with non constant-time size hashed containers]: some operations, like
`empty()`, have linear complexity, unlike other [*Boost.Intrusive] containers.

[endsect]

[section:unordered_set_unordered_multiset_hooks unordered_set and unordered_multiset hooks]

[classref boost::intrusive::unordered_set unordered_set] and [classref boost::intrusive::unordered_multiset unordered_multiset] share the same hooks. This is an advantage, because the same
user type can be inserted first in a [classref boost::intrusive::unordered_multiset unordered_multiset] and after that in [classref boost::intrusive::unordered_set unordered_set] without
changing the definition of the user class.

[c++]

   template <class ...Options>
   class unordered_set_base_hook;

*  [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook]:
   the user class derives publicly from
   [classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] to make
   it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.

[c++]

   template <class ...Options>
   class unordered_set_member_hook;

*  [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook]:
   the user class contains a public
   [classref boost::intrusive::unordered_set_member_hook unordered_set_member_hook] to make
   it [classref boost::intrusive::unordered_set unordered_set]/[classref boost::intrusive::unordered_multiset unordered_multiset]-compatible.

[classref boost::intrusive::unordered_set_base_hook unordered_set_base_hook] and
[classref boost::intrusive::unordered_set_member_hook unordered_set_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 base 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*>`.

Apart from them, these hooks offer additional options:

*  [*`store_hash<bool Enabled>`]: This option reserves additional space in
   the hook to store the hash value of the object once it's introduced in the
   container. When this option is used, the unordered container will store
   the calculated hash value in the hook and rehashing operations won't need
   to recalculate the hash of the value.
   This option will improve the perfomance of unordered containers when
   rehashing is frequent or hashing the value is a slow operation.
   Default: `store_hash<false>`.

*  [*`optimize_multikey<bool Enabled>`]: This option reserves additional space in
   the hook that will be used to group equal elements in unordered multisets,
   improving significantly the performance when many equal values are inserted
   in these containers. Default: `optimize_multikey<false>`.

[endsect]

[section:unordered_set_unordered_multiset_containers unordered_set and unordered_multiset containers]

[c++]

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

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

As mentioned, unordered containers need an auxiliary array to work. [*Boost.Intrusive]
unordered containers receive this auxiliary array packed in a type called `bucket_traits`
(which can be also customized by a container option). All unordered containers receive
a `bucket_traits` object in their constructors. The default `bucket_traits` class
is initialized with a pointer to an array of buckets and its size:

[c++]

   #include <boost/intrusive/unordered_set.hpp>

   using namespace boost::intrusive;

   struct MyClass : public unordered_set_base_hook<>
   {};

   typedef unordered_set<MyClass>::bucket_type     bucket_type;
   typedef unordered_set<MyClass>::bucket_traits   bucket_traits;

   int main()
   {
      bucket_type buckets[100];
      unordered_set<MyClass> uset(bucket_traits(buckets, 100));
      return 0;
   }

Each hashed container needs [*its own bucket traits], that is, [*its own
bucket vector]. Two hashed containers
[*can't] share the same `bucket_type` elements. The bucket array [*must] be
destroyed [*after] the container using it is destroyed, otherwise, the result
is undefined.

[classref boost::intrusive::unordered_set unordered_set] and
[classref boost::intrusive::unordered_multiset unordered_multiset]