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
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
webmaster@www.sgi.com