# Associative Sequence

### Description

An Associative Sequence is a Sequence which allows efficient retrieval of elements based on keys. For some of associative sequences such as `set` it is guaranteed that no two elements have the same key. Others, such as `multiset`, allow multiple elements with the same key.

### Refinement of

Sequence

### Valid expressions

In addition to Sequence's expressions the following expressions are valid.

Expression | Expression type
--- | ---
`has_key<s,k>::type` | A model of boolean Integral Constant
`count<s,k>::type` | A model of Integral Constant
`order<s,k>::type` | A model of Integral Constant or `void_`
`at<s,k>::type` | A type
`at<s,k,default>::type` | A type

### Expression semantics

Expression | Complexity | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
`has_key<s,k>::type` | Amortized constant time |  |  |
`count<s,k>::type` | Amortized constant time |  |  |
`order<s,k>::type` | Amortized constant time |  |  |
`at<s,k>::type` | Amortized constant time |  |  |

### Invariants

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

- TODO

### Models

- `set`
- `map`
- `set_c`

### Notes

### See also

Sequences, Forward Sequence, Extensible Associative Sequence,

Table of Contents
Last edited October 25, 2003 7:40 am