# Unique Associative Container

Category: containers | Component type: concept

### Description

A Unique Associative Container is an Associative Container with the property that each key in the container is unique: no two elements in a Unique Associative Container have the same key.

### Refinement of

Associative Container

### Associated types

None, except for those defined by Associative Container.

### Notation

`X` | A type that is a model of Unique Associative Container
`a` | Object of type `X`
`t` | Object of type `X::value_type`
`k` | Object of type `X::key_type`
`p`, `q` | Object of type `X::iterator`

### Definitions

### Valid expressions

In addition to the expressions defined in Associative Container, the following expressions must be valid.

Name | Expression | Type requirements | Return type
--- | --- | --- | ---
Range constructor |
    X(i, j)
    X a(i, j);
| `i` and `j` are Input Iterators whose value type is convertible to `T` [1] |
Insert element | `a.insert(t)` |  | `pair<X::iterator, bool>`
Insert range | `a.insert(i, j)` | `i` and `j` are Input Iterators whose value type is convertible to `X::value_type`. [1] | `void`
Count | `a.count(k)` |  | `size_type`

### Expression semantics

Name | Expression | Precondition | Semantics | Postcondition
--- | --- | --- | --- | ---
Range constructor |
    X(i, j)
    X a(i, j);
| `[i,j)` is a valid range. | Creates an associative container that contains all of the elements in the range `[i,j)` that have unique keys. | `size()` is less than or equal to the distance from `i` to `j`.
Insert element | `a.insert(t)` |  | Inserts `t` into `a` if and only if `a` does not already contain an element whose key is the same as the key of `t`. The return value is a `pair` `P`. `P.first` is an iterator pointing to the element whose key is the same as the key of `t`. `P.second` is a `bool`: it is `true` if `t` was actually inserted into `a`, and `false` if `t` was not inserted into `a`, i.e. if `a` already contained an element with the same key as `t`. | `P.first` is a dereferenceable iterator. `*(P.first)` has the same key as `t`. The size of `a` is incremented by `1` if and only if `P.second` is `true`.
Insert range | `a.insert(i, j)` | `[i, j)` is a valid range. | Equivalent to `a.insert(t)` for each object `t` that is pointed to by an iterator in the range `[i, j)`. Each element is inserted into `a` if and only if `a` does not already contain an element with the same key. | The size of `a` is incremented by at most `j - i`.
Count | `a.count(k)` |  | Returns the number of elements in `a` whose keys are the same as `k`. | The return value is either `0` or `1`.

### Complexity guarantees

Average complexity for insert element is at most logarithmic.

Average complexity for insert range is at most `O(N * log(size() + N))`, where `N` is `j - i`.

### Invariants

Uniqueness | No two elements have the same key. Equivalently, this means that for every object `k` of type `key_type`, `a.count(k)` returns either `0` or `1`.

### Models

- `set`
- `map`
- `hash_set`
- `hash_map`

### Notes

[1] At present (early 1998), not all compilers support "member templates". If your compiler supports member templates then `i` and `j` may be of any type that conforms to the Input Iterator requirements. If your compiler does not yet support member templates, however, then `i` and `j` must be of type `const T*` or of type `X::const_iterator`.

### See also

Associative Container, Multiple Associative Container, Unique Sorted Associative Container, Multiple Sorted Associative Container

Copyright © 1999 Silicon Graphics, Inc. All Rights Reserved. TrademarkInformation