1.. Sequences/Concepts//Extensible Associative Sequence |80 2 3Extensible Associative Sequence 4=============================== 5 6Description 7----------- 8 9An |Extensible Associative Sequence| is an |Associative Sequence| that supports 10insertion and removal of elements. In contrast to |Extensible Sequence|, 11|Extensible Associative Sequence| does not provide a mechanism for 12inserting an element at a specific position. 13 14 15Expression requirements 16----------------------- 17 18|In the following table...| ``s`` is an |Associative Sequence|, 19``pos`` is an iterator into ``s``, and ``x`` and ``k`` are arbitrary types. 20 21In addition to the |Associative Sequence| requirements, the following must be met: 22 23+-------------------------------+---------------------------------------+---------------------------+ 24| Expression | Type | Complexity | 25+===============================+=======================================+===========================+ 26| ``insert<s,x>::type`` | |Extensible Associative Sequence| | Amortized constant time | 27+-------------------------------+---------------------------------------+---------------------------+ 28| ``insert<s,pos,x>::type`` | |Extensible Associative Sequence| | Amortized constant time | 29+-------------------------------+---------------------------------------+---------------------------+ 30| ``erase_key<s,k>::type`` | |Extensible Associative Sequence| | Amortized constant time | 31+-------------------------------+---------------------------------------+---------------------------+ 32| ``erase<s,pos>::type`` | |Extensible Associative Sequence| | Amortized constant time | 33+-------------------------------+---------------------------------------+---------------------------+ 34| ``clear<s>::type`` | |Extensible Associative Sequence| | Amortized constant time | 35+-------------------------------+---------------------------------------+---------------------------+ 36 37 38Expression semantics 39-------------------- 40 41|Semantics disclaimer...| |Associative Sequence|. 42 43+-------------------------------+-------------------------------------------------------------------+ 44| Expression | Semantics | 45+===============================+===================================================================+ 46| ``insert<s,x>::type`` | Inserts ``x`` into ``s``; the resulting sequence ``r`` is | 47| | equivalent to ``s`` except that | 48| | :: | 49| | | 50| | at< r, key_type<s,x>::type >::type | 51| | | 52| | is identical to ``value_type<s,x>::type``; see |insert|. | 53+-------------------------------+-------------------------------------------------------------------+ 54| ``insert<s,pos,x>::type`` | Equivalent to ``insert<s,x>::type``; ``pos`` is ignored; | 55| | see |insert|. | 56+-------------------------------+-------------------------------------------------------------------+ 57| ``erase_key<s,k>::type`` | Erases elements in ``s`` associated with the key ``k``; | 58| | the resulting sequence ``r`` is equivalent to ``s`` except | 59| | that ``has_key<r,k>::value == false``; see |erase_key|. | 60+-------------------------------+-------------------------------------------------------------------+ 61| ``erase<s,pos>::type`` | Erases the element at a specific position; equivalent to | 62| | ``erase_key<s, deref<pos>::type >::type``; see |erase|. | 63+-------------------------------+-------------------------------------------------------------------+ 64| ``clear<s>::type`` | An empty sequence concept-identical to ``s``; see | 65| | |clear|. | 66+-------------------------------+-------------------------------------------------------------------+ 67 68.. Invariants 69 ---------- 70 71 For any extensible associative sequence ``s`` the following invariants always hold: 72 73 74Models 75------ 76 77* |set| 78* |map| 79 80.. * |multiset| 81 82 83See also 84-------- 85 86|Sequences|, |Associative Sequence|, |insert|, |erase|, |clear| 87 88 89.. copyright:: Copyright � 2001-2009 Aleksey Gurtovoy and David Abrahams 90 Distributed under the Boost Software License, Version 1.0. (See accompanying 91 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) 92