Front Page / Sequences / Concepts / Extensible Associative Sequence

# 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 and subsequent specifications, `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

The semantics of an expression are defined only where they differ from, or are not defined in 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.

### Models

- set
- map

### See also

Sequences, Associative Sequence, insert, erase, clear