1.. Sequences/Concepts//Associative Sequence |70 2 3Associative Sequence 4==================== 5 6Description 7----------- 8 9An |Associative Sequence| is a |Forward Sequence| that allows efficient retrieval of 10elements based on keys. Unlike associative containers in the C++ Standard Library, 11MPL associative sequences have no associated ordering relation. Instead, 12*type identity* is used to impose an equivalence relation on keys, and the 13order in which sequence elements are traversed during iteration is left 14unspecified. 15 16 17Definitions 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 31Expression 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 37In addition to the requirements defined in |Forward Sequence|, 38the 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 59Expression 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 97Models 98------ 99 100* |set| 101* |map| 102 103.. * |multiset| 104 105 106See 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) 122