Standard Template Library Programmer's Guide

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]

• set

• multiset

• map

• multimap

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

Associative Container, Hashed Associative Container

Category: containers

Component type: concept

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.

Associative Container

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

XA type that is a model of Hashed Associative Container

aObject of type X

tObject of type X::value_type

kObject of type X::key_type

p, qObject of type X::iterator

nObject of type X::size_type

hObject of type X::hasher

cObject of type X::key_equal

A hash function for a Hashed Associative Container X is a Unary Function whose argument type is X::key_type and whose return type is size_t . A hash function must be deterministic (that is, it must always return the same value whenever it is called with the same argument), but return values of the hash function should be as uniform as possible: ideally, no two keys will hash to the same value. [2]

Elements in a Hashed Associative Container are organized into buckets . A Hashed Associative Container uses the value of the hash function to determine which bucket an element is assigned to.

The number of elements in a Hashed Associative Container divided by the number of buckets is called the load factor . A Hashed Associative Container with a small load factor is faster than one with a large load factor.