.. 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-part`_

.. |value| replace:: `value`__
__ `value-part`_