ceph/src/boost/libs/mpl/doc/src/refmanual/AssociativeSequence.rst

   1 .. Sequences/Concepts//Associative Sequence |70
   2
   3 Associative Sequence
   4 ====================
   5
   6 Description
   7 -----------
   8
   9 An |Associative Sequence| is a |Forward Sequence| that allows efficient retrieval of
  10 elements based on keys. Unlike associative containers in the C++ Standard Library,
  11 MPL associative sequences have no associated ordering relation. Instead,
  12 *type identity* is used to impose an equivalence relation on keys, and the
  13 order in which sequence elements are traversed during iteration is left
  14 unspecified.
  15
  16
  17 Definitions
  18 -----------
  19
  20 .. _`key-part`:
  21
  22 .. _`value-part`:
  23
  24 * A *key* is a part of the element type used to identify and retrieve
  25   the element within the sequence.
  26
  27 * A *value* is a part of the element type retrievied from the sequence
  28   by its key.
  29
  30
  31 Expression requirements
  32 -----------------------
  33
  34 |In the following table...| ``s`` is an |Associative Sequence|,
  35 ``x`` is a sequence element, and ``k`` and ``def`` are arbitrary types.
  36
  37 In addition to the requirements defined in |Forward Sequence|,
  38 the following must be met:
  39
  40 +-------------------------------+-----------------------------------+---------------------------+
  41 | Expression                    | Type                              | Complexity                |
  42 +===============================+===================================+===========================+
  43 | ``has_key<s,k>::type``        | Boolean |Integral Constant|       | Amortized constant time   |
  44 +-------------------------------+-----------------------------------+---------------------------+
  45 | ``count<s,k>::type``          | |Integral Constant|               | Amortized constant time   |
  46 +-------------------------------+-----------------------------------+---------------------------+
  47 | ``order<s,k>::type``          | |Integral Constant| or ``void_``  | Amortized constant time   |
  48 +-------------------------------+-----------------------------------+---------------------------+
  49 | ``at<s,k>::type``             | Any type                          | Amortized constant time   |
  50 +-------------------------------+-----------------------------------+---------------------------+
  51 | ``at<s,k,def>::type``         | Any type                          | Amortized constant time   |
  52 +-------------------------------+-----------------------------------+---------------------------+
  53 | ``key_type<s,x>::type``       | Any type                          | Amortized constant time   |
  54 +-------------------------------+-----------------------------------+---------------------------+
  55 | ``value_type<s,x>::type``     | Any type                          | Amortized constant time   |
  56 +-------------------------------+-----------------------------------+---------------------------+
  57
  58
  59 Expression semantics
  60 --------------------
  61
  62 |Semantics disclaimer...| |Forward Sequence|.
  63
  64 +-------------------------------+---------------------------------------------------------------+
  65 | Expression                    | Semantics                                                     |
  66 +===============================+===============================================================+
  67 | ``has_key<s,k>::type``        | |true if and only if| there is one or more                    |
  68 |                               | elements with the key ``k`` in ``s``; see |has_key|.          |
  69 +-------------------------------+---------------------------------------------------------------+
  70 | ``count<s,k>::type``          | The number of elements with the key ``k`` in ``s``;           |
  71 |                               | see |count|.                                                  |
  72 +-------------------------------+---------------------------------------------------------------+
  73 | ``order<s,k>::type``          | A unique unsigned |Integral Constant| associated              |
  74 |                               | with the key ``k`` in the sequence ``s``; see |order|.        |
  75 +-------------------------------+---------------------------------------------------------------+
  76 | .. parsed-literal::           | The first element associated with the key ``k``               |
  77 |                               | in the sequence ``s``; see |at|.                              |
  78 |    at<s,k>::type              |                                                               |
  79 |    at<s,k,def>::type          |                                                               |
  80 +-------------------------------+---------------------------------------------------------------+
  81 | ``key_type<s,x>::type``       | The key part of the element ``x`` that would be               |
  82 |                               | used to identify ``x`` in ``s``; see |key_type|.              |
  83 +-------------------------------+---------------------------------------------------------------+
  84 | ``value_type<s,x>::type``     | The value part of the element ``x`` that would be             |
  85 |                               | used for ``x`` in ``s``; see |value_type|.                    |
  86 +-------------------------------+---------------------------------------------------------------+
  87
  88
  89 .. Invariants
  90    ----------
  91
  92    For any associative sequence ``s`` the following invariants always hold:
  93
  94     * ???
  95
  96
  97 Models
  98 ------
  99
 100 * |set|
 101 * |map|
 102
 103 .. * |multiset|
 104
 105
 106 See also
 107 --------
 108
 109 |Sequences|, |Extensible Associative Sequence|, |has_key|, |count|, |order|, |at|, |key_type|, |value_type|
 110
 111
 112 .. |key| replace:: `key`_
 113 .. _`key`: `key-part`_
 114
 115 .. |value| replace:: `value`_
 116 .. _`value`: `value-part`_
 117
 118
 119 .. copyright:: Copyright ©  2001-2009 Aleksey Gurtovoy and David Abrahams
 120    Distributed under the Boost Software License, Version 1.0. (See accompanying
 121    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)