# Multiple Sorted Associative Container

Category: containers | Component type: concept

### Description

A Multiple Sorted Associative Container is a Sorted Associative Container that is also a Multiple Associative Container. That is, it is a Sorted Associative Container with the property that any number of elements in the container may have equivalent keys.

### Refinement of

Sorted Associative Container, Multiple Associative Container

### Associated types

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

### Notation

`X` | A type that is a model of Multiple 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 Multiple 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]. | `X`
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`. | `X`
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)`. The comparison object used by the container is `key_compare()`. | `size()` is 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)`. The comparison object used by the container is `c`. | `size()` is 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`. 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 that was just inserted. | `a` contains an element whose key is the same as that of `t`. The size of `a` is incremented by `1`.
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`. | The size of `a` is incremented by `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

### Models

- `multimap`
- `multiset`

### 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, Sorted Associative Container, Unique Sorted Associative Container Hashed Associative Container

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