unordered_map Class

The template class describes an object that controls a varying-length sequence of elements of type std::pair<const Key, Ty>. The sequence is weakly ordered by a hash function, which partitions the sequence into an ordered set of subsequences called buckets. Within each bucket a comparison function determines whether any pair of elements has equivalent ordering. Each element stores two objects, a sort key and a value. The sequence is represented in a way that permits lookup, insertion, and removal of an arbitrary element with a number of operations that can be independent of the number of elements in the sequence (constant time), at least when all buckets are of roughly equal length. In the worst case, when all of the elements are in one bucket, the number of operations is proportional to the number of elements in the sequence (linear time). Moreover, inserting an element invalidates no iterators, and removing an element invalidates only those iterators which point at the removed element.

template<class Key,
    class Ty,
    class Hash = std::tr1::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_map;

Parameters

Members

Remarks

The object orders the sequence it controls by calling two stored objects, a comparison function object of type unordered_map::key_equal and a hash function object of type unordered_map::hasher. You access the first stored object by calling the member function unordered_map::key_eq(); and you access the second stored object by calling the member function unordered_map::hash_function(). Specifically, for all values X and Y of type Key, the call key_eq()(X, Y) returns true only if the two argument values have equivalent ordering; the call hash_function()(keyval) yields a distribution of values of type size_t. Unlike template class unordered_multimap Class, an object of template class unordered_map ensures that key_eq()(X, Y) is always false for any two elements of the controlled sequence. (Keys are unique.)

The object also stores a maximum load factor, which specifies the maximum desired average number of elements per bucket. If inserting an element causes unordered_map::load_factor() to exceed the maximum load factor, the container increases the number of buckets and rebuilds the hash table as needed.

The actual order of elements in the controlled sequence depends on the hash function, the comparison function, the order of insertion, the maximum load factor, and the current number of buckets. You cannot in general predict the order of elements in the controlled sequence. You can always be assured, however, that any subset of elements that have equivalent ordering are adjacent in the controlled sequence.

The object allocates and frees storage for the sequence it controls through a stored allocator object of type unordered_map::allocator_type. Such an allocator object must have the same external interface as an object of template class allocator. Note that the stored allocator object is not copied when the container object is assigned.

Requirements

Header: <unordered_map>

Namespace: std::tr1

See Also

Reference

<unordered_map>

unordered_map Class