Standard Template Library Programmer's Guide

[3] Resizing does not invalidate iterators; however, it does not necessarily preserve the ordering relation between iterators. That is, if i and j are iterators that point into a Hashed Associative Container such that i comes immediately before j , then there is no guarantee that i will still come immediately before j after the container is resized. The only guarantee about about the ordering of elements is the contiguous storage invariant: elements with the same key are always adjacent to each other.

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

Categories: containers, functors

Component type: concept

A Hash Function is a Unary Function that is used by Hashed Associative Containers: it maps its argument to a result of type size_t . A Hash Function must be deterministic and stateless. That is, the return value must depend only on the argument, and equal arguments must yield equal results.

The performance of a Hashed Associative Container depends crucially on its hash function. It is important for a Hash Function to minimize collisions, where a collision is defined as two different arguments that hash to the same value. It is also important that the distribution of hash values be uniform; that is, the probability that a Hash Function returns any particular value of type size_t should be roughly the same as the probability that it returns any other value. [1]

Unary Function

None, except for those described in the Unary Function requirements.

• hash

[1] Note that both of these requirements make sense only in the context of some specific distribution of input values. To take a simple example, suppose that the values being hashed are the six strings "aardvark", "trombone", "history", "diamond", "forthright", and "solitude". In this case, one reasonable (and efficient) hash function would simply be the first character of each string. On the other hand, suppose that the values being hashed are "aaa0001", "aaa0010", "aaa0011", "aaa0100", "aaa0101", and "aaa0110". In that case, a different hash function would be more appropriate. This is why Hashed Associative Containers are parameterized by the hash function: no one hash function is best for all applications.

Hashed Associative Container, hash

Category: containers

Component type: concept

A Unique Associative Container is an Associative Container with the property that each key in the container is unique: no two elements in a Unique Associative Container have the same key.

Associative Container

None, except for those defined by Associative Container.

XA type that is a model of Unique Associative Container

aObject of type X

tObject of type X::value_type

kObject of type X::key_type

p, qObject of type X::iterator

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

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 .

• set

• map

• hash_set

• hash_map

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