
ALINK="#ff0000">
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
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
