.. Sequences/Concepts//Extensible Associative Sequence |80

Extensible Associative Sequence
===============================

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

An |Extensible Associative Sequence| is an |Associative Sequence| that supports 
insertion and removal of elements. In contrast to |Extensible Sequence|, 
|Extensible Associative Sequence| does not provide a mechanism for 
inserting an element at a specific position. 


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

|In the following table...| ``s`` is an |Associative Sequence|, 
``pos`` is an iterator into ``s``, and ``x`` and ``k`` are arbitrary types.

In addition to the |Associative Sequence| requirements, the following must be met:

+-------------------------------+---------------------------------------+---------------------------+
| Expression                    | Type                                  | Complexity                |
+===============================+=======================================+===========================+
| ``insert<s,x>::type``         | |Extensible Associative Sequence|     | Amortized constant time   |
+-------------------------------+---------------------------------------+---------------------------+
| ``insert<s,pos,x>::type``     | |Extensible Associative Sequence|     | Amortized constant time   |
+-------------------------------+---------------------------------------+---------------------------+
| ``erase_key<s,k>::type``      | |Extensible Associative Sequence|     | Amortized constant time   |
+-------------------------------+---------------------------------------+---------------------------+
| ``erase<s,pos>::type``        | |Extensible Associative Sequence|     | Amortized constant time   |
+-------------------------------+---------------------------------------+---------------------------+
| ``clear<s>::type``            | |Extensible Associative Sequence|     | Amortized constant time   |
+-------------------------------+---------------------------------------+---------------------------+


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

|Semantics disclaimer...| |Associative Sequence|.

+-------------------------------+-------------------------------------------------------------------+
| Expression                    | Semantics                                                         |
+===============================+===================================================================+
| ``insert<s,x>::type``         | Inserts ``x`` into ``s``; the resulting sequence ``r`` is         |
|                               | equivalent to ``s`` except that                                   |
|                               | ::                                                                |
|                               |                                                                   |
|                               |     at< r, key_type<s,x>::type >::type                            |
|                               |                                                                   |
|                               | is identical to ``value_type<s,x>::type``; see |insert|.          |
+-------------------------------+-------------------------------------------------------------------+
| ``insert<s,pos,x>::type``     | Equivalent to ``insert<s,x>::type``; ``pos`` is ignored;          |
|                               | see |insert|.                                                     |
+-------------------------------+-------------------------------------------------------------------+
| ``erase_key<s,k>::type``      | Erases elements in ``s`` associated with the key ``k``;           |
|                               | the resulting sequence ``r`` is equivalent to ``s`` except        |
|                               | that ``has_key<r,k>::value == false``; see |erase_key|.           |
+-------------------------------+-------------------------------------------------------------------+
| ``erase<s,pos>::type``        | Erases the element at a specific position; equivalent to          |
|                               | ``erase_key<s, deref<pos>::type >::type``; see |erase|.           |
+-------------------------------+-------------------------------------------------------------------+
| ``clear<s>::type``            | An empty sequence concept-identical to ``s``; see                 |
|                               | |clear|.                                                          |
+-------------------------------+-------------------------------------------------------------------+

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

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


Models
------

* |set|
* |map|

.. * |multiset|


See also
--------

|Sequences|, |Associative Sequence|, |insert|, |erase|, |clear|