[ceph.git] / ceph / src / boost / libs / mpl / doc / src / refmanual / AssociativeSequence.rst

.. Sequences/Concepts//Associative Sequence |70

Associative Sequence
====================

Description
-----------

An |Associative Sequence| is a |Forward Sequence| that allows efficient retrieval of 
elements based on keys. Unlike associative containers in the C++ Standard Library, 
MPL associative sequences have no associated ordering relation. Instead, 
*type identity* is used to impose an equivalence relation on keys, and the 
order in which sequence elements are traversed during iteration is left 
unspecified.


Definitions
-----------

.. _`key-part`:

.. _`value-part`:

* A *key* is a part of the element type used to identify and retrieve 
  the element within the sequence.

* A *value* is a part of the element type retrievied from the sequence 
  by its key.


Expression requirements
-----------------------

|In the following table...| ``s`` is an |Associative Sequence|, 
``x`` is a sequence element, and ``k`` and ``def`` are arbitrary types.

In addition to the requirements defined in |Forward Sequence|, 
the following must be met:

+-------------------------------+-----------------------------------+---------------------------+
| Expression                    | Type                              | Complexity                |
+===============================+===================================+===========================+
| ``has_key<s,k>::type``        | Boolean |Integral Constant|       | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``count<s,k>::type``          | |Integral Constant|               | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``order<s,k>::type``          | |Integral Constant| or ``void_``  | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``at<s,k>::type``             | Any type                          | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``at<s,k,def>::type``         | Any type                          | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``key_type<s,x>::type``       | Any type                          | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+
| ``value_type<s,x>::type``     | Any type                          | Amortized constant time   |
+-------------------------------+-----------------------------------+---------------------------+


Expression semantics
--------------------

|Semantics disclaimer...| |Forward Sequence|.

+-------------------------------+---------------------------------------------------------------+
| Expression                    | Semantics                                                     |
+===============================+===============================================================+
| ``has_key<s,k>::type``        | |true if and only if| there is one or more                    |
|                               | elements with the key ``k`` in ``s``; see |has_key|.          |
+-------------------------------+---------------------------------------------------------------+
| ``count<s,k>::type``          | The number of elements with the key ``k`` in ``s``;           |
|                               | see |count|.                                                  |
+-------------------------------+---------------------------------------------------------------+
| ``order<s,k>::type``          | A unique unsigned |Integral Constant| associated              |
|                               | with the key ``k`` in the sequence ``s``; see |order|.        |
+-------------------------------+---------------------------------------------------------------+
| .. parsed-literal::           | The first element associated with the key ``k``               |
|                               | in the sequence ``s``; see |at|.                              |
|    at<s,k>::type              |                                                               |
|    at<s,k,def>::type          |                                                               |
+-------------------------------+---------------------------------------------------------------+
| ``key_type<s,x>::type``       | The key part of the element ``x`` that would be               |
|                               | used to identify ``x`` in ``s``; see |key_type|.              |
+-------------------------------+---------------------------------------------------------------+
| ``value_type<s,x>::type``     | The value part of the element ``x`` that would be             |
|                               | used for ``x`` in ``s``; see |value_type|.                    |
+-------------------------------+---------------------------------------------------------------+


.. Invariants
   ----------

   For any associative sequence ``s`` the following invariants always hold: 

    * ???


Models
------

* |set|
* |map|

.. * |multiset|


See also
--------

|Sequences|, |Extensible Associative Sequence|, |has_key|, |count|, |order|, |at|, |key_type|, |value_type|


.. |key| replace:: `key`_
.. _`key`: `key-part`_

.. |value| replace:: `value`_
.. _`value`: `value-part`_
Commit	Line	Data
7c673cae FG	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