Standard Template Library Programmer's Guide

X::hasher	A type that is a model of Hash Function. X::hasher 's argument type must be X::key_type.
Key equal	X::key_equal	A Binary Predicate whose argument type is X::key_type . An object of type key_equal returns true if its arguments are the same key, and false otherwise. X::key_equal must be an equivalence relation.

Notation

X A type that is a model of Hashed 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

n Object of type X::size_type

h Object of type X::hasher

c Object of type X::key_equal

Definitions

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.

Valid expressions

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

Name	Expression	Return type
Default constructor	X() X a;
Constructor with bucket count	X(n) X a(n);
Constructor with hash function	X(n, h) X a(n, h);
Constructor with key equal	X(n, h, k) X a(n, h, k);
Hash function	a.hash_funct()	X::hasher
Key equal	a.key_eq()	X::key_equal
Erase key	a.erase(k)	size_type
Erase element	a.erase(p)	void
Erase range	a.erase(p, q)	void
Find	a.find(k)	iterator if a is mutable, otherwise const_iterator
Count	a.count(k)	size_type