# Multiple Associative Container

Category: containers | Component type: concept

### Description

A Multiple Associative Container is an Associative Container in which there may be more than one element with the same key. That is, it is an Associative Container that does not have the restrictions of a Unique Associative Container.

### Refinement of

Associative Container

### Associated types

None, except for those defined by Associative Container

### Notation

`X` | A type that is a model of Multiple 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)` |  | `X::iterator`
Insert range | `a.insert(i, j)` | `i` and `j` are Input Iterators whose value type is convertible to `X::value_type`. | `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 elements in the range `[i,j)`. | `size()` is equal to the distance from `i` to `j`. Each element in `[i, j)` is present in the container.
Insert element | `a.insert(t)` |  | Inserts `t` into `a`. | The size of `a` is incremented by `1`. The value of `a.count(t)` is incremented by `a`.
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

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

### Models

- `multiset`
- `multimap`
- `hash_multiset`
- `hash_multimap`

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

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