Standard Template Library Programmer's Guide

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() .

• map

• set

[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.

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

Category: containers

Component type: concept

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.

Sorted Associative Container, Multiple Associative Container

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

XA type that is a model of Multiple Sorted Associative Container

aObject of type X

tObject of type X::value_type

kObject of type X::key_type

p, qObject of type X::iterator

cObject of type X::key_compare

In addition to the expressions defined in Sorted Associative Container and Multiple Associative Container, the following expressions must be valid.

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() .

• multimap

• multiset

[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 .

Associative Container, Sorted Associative Container, Unique Sorted Associative Container Hashed Associative Container

Category: containers

Component type: concept

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

Hashed Associative Container, Unique Associative Container

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

XA type that is a model of Hashed Associative Container

aObject of type X