# Unique Sorted Associative Container

Category: containers | Component type: concept

### Description

A Unique Sorted Associative Container is a Sorted Associative Container that is also a Unique Associative Container. That is, it is a Sorted Associative Container with the property that no two elements in the container have the same key.

### Refinement of

Sorted Associative Container, Unique Associative Container

### Associated types

None, except for those described in the Sorted Associative Container and Unique Associative Container requirements.

### Notation

`X` | A type that is a model of Unique Sorted 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`
`c` | Object of type `X::key_compare`

### Definitions

### Valid expressions

In addition to the expressions defined in Sorted Associative Container and Unique 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]. |
Range constructor with compare |
    X(i, j, c)
    X a(i, j, c);
| `i` and `j` are Input Iterators whose value type is convertible to `T` [1]. `c` is an object of type `key_compare`. |
Insert with hint | `a.insert(p, t)` |  | `iterator`
Insert range | `a.insert(i, j)` | `i` and `j` are Input Iterators whose value type is convertible to `X::value_type`. [1] | `void`

### 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. The comparison object used by the container is `key_compare()`. | `size()` is less than or equal to the distance from `i` to `j`.
Range constructor with compare |
    X(i, j, c)
    X a(i, j, c);
| `[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. The comparison object used by the container is `c`. | `size()` is less than or equal to the distance from `i` to `j`.
Insert with hint | `a.insert(p, t)` | `p` is a nonsingular iterator in `a`. | Inserts `t` into `a` if and only if `a` does not already contain an element whose key is equivalent to `t`'s key. The argument `p` is a hint: it points to the location where the search will begin. The return value is a dereferenceable iterator that points to the element with a key that is equivalent to that of `t`. | `a` contains an element whose key is the same as that of `t`. The size of `a` is incremented by either `1` or `0`.
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 an equivalent key. | The size of `a` is incremented by at most `j - i`.

### Complexity guarantees

The range constructor, and range constructor with compare, are in general `O(N * log(N))`, where `N` is the size of the range. However, they are linear in `N` if the range is already sorted by `value_comp()`.

Insert with hint is logarithmic in general, but it is amortized constant time if `t` is inserted immediately before `p`.

Insert range is in general `O(N * log(N))`, where `N` is the size of the range. However, it is linear in `N` if the range is already sorted by `value_comp()`.

### Invariants

Strictly ascending order | The elements in a Unique Sorted Associative Container are always arranged in strictly ascending order by key. That is, if `a` is a Unique Sorted Associative Container, then `is_sorted(a.begin(), a.end(), a.value_comp())` is always `true`. Furthermore, if `i` and `j` are dereferenceable iterators in `a` such that `i` precedes `j`, then `a.value_comp()(*i, *j)` is always `true`. [2]

### Models

- `map`
- `set`

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

[2] This is a more stringent invariant than that of Sorted Associative Container. In a Sorted Associative Container we merely know that every element is less than or equal to its successor; in a Unique Sorted Associative Container, however, we know that it must be less than its successor.

### See also

Associative Container, Sorted Associative Container, Multiple Sorted Associative Container, Hashed Associative Container

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