Standard Template Library Programmer's Guide

If t1 and t2 are objects of type value_type, and k1 and k2 are the keys associated with them, then a.value_comp()(t1, t2) is equivalent to a.key_comp()(k1, k2).
Lower bound	a.lower_bound(k)	Returns an iterator pointing to the first element whose key is not less than k. Returns a.end() if no such element exists.	If a contains any elements that have the same key as k, then the return value of lower_bound points to the first such element.
Upper bound	a.upper_bound(k)	Returns an iterator pointing to the first element whose key is greater than k.	Returns a.end() if no such element exists. If a contains any elements that have the same key as k, then the return value of upper_bound points to one past the last such element.
Equal range	a.equal_range(k)	Returns a pair whose first element is a.lower_bound(k) and whose second element is a.upper_bound(k).

Complexity guarantees

key_comp() and value_comp() are constant time.

Erase element is constant time.

Erase key is O(log(size()) + count(k)). [1]

Erase range is O(log(size()) + N), where N is the length of the range. [1]

Find is logarithmic. [1]

Count is O(log(size()) + count(k)). [1]

Lower bound, upper bound, and equal range are logarithmic. [1]

Invariants

Definition of value_comp	If t1 and t2 are objects of type X::value_type and k1 and k2 are the keys associated with those objects, then a.value_comp() returns a function object such that a.value_comp()(t1, t2) is equivalent to a.key_comp()(k1, k2).
Ascending order	The elements in a Sorted Associative Container are always arranged in ascending order by key. That is, if a is a Sorted Associative Container, then is_sorted(a.begin(), a.end(), a.value_comp()) is always true.

Models

• set
• multiset
• map
• multimap

Notes

[1] This is a much stronger guarantee than the one provided by Associative Container. The guarantees in Associative Container only apply to average complexity; worst case complexity is allowed to be greater. Sorted Associative Container, however, provides an upper limit on worst case complexity.

[2] This definition is consistent with the semantics described in Associative Container. It is a stronger condition, though: if a contains no elements with the key k , then a.equal_range(k) returns an empty range that indicates the position where those elements would be if they did exist. The Associative Container requirements, however, merely state that the return value is an arbitrary empty range.

See also

Associative Container, Hashed Associative Container

Hashed Associative Container

Category: containers

Component type: concept

Description

A Hashed Associative Container is an Associative Container whose implementation is a hash table. [1] The elements of a Hashed Associative Container are not guaranteed to be in any meaningful order; in particular, they are not sorted. The worst case complexity of most operations on Hashed Associative Containers is linear in the size of the container, but the average case complexity is constant time; this means that for applications where values are simply stored and retrieved, and where ordering is unimportant, Hashed Associative Containers are usually much faster than Sorted Associative Containers.

Refinement of

Associative Container

Associated types

The following new types are introduced, in addition to the types defined in the Associative Container requirements.

Hash function