.. 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|

.. copyright:: Copyright 2001-2009 Aleksey Gurtovoy and David Abrahams Distributed under the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)