Przejdź do głównej zawartości

C++ named requirements: UnorderedAssociativeContainer (od C++11)

Unordered associative containers are Containers that provide fast lookup of objects based on keys. Worst case complexity is linear but on average much faster for most of the operations.

Unordered associative containers are parametrized by Key; Hash, a Hash function object which acts as hash function on Key; and Pred, a BinaryPredicate evaluating equivalence between Keys. std::unordered_map and std::unordered_multimap also have a mapped type T associated with the Key.

If two Keys are equal according to Pred, Hash must return the same value for both keys.


If both Hash::is_transparent and Pred::is_transparent exist and each names a type, member functions find, contains, count, and equal_range accept arguments of types other than Key and expect that Hash is callable with values of those types, and that Pred is a transparent comparison function such as std::equal_to<>. (od C++20)

std::unordered_map and std::unordered_set can contain at most one element with a given key, std::unordered_multiset and std::unordered_multimap instead can have multiple elements with the same key (which must always be adjacent on iterations).

For std::unordered_set and std::unordered_multiset the value type is the same as the key type and both iterator and const_iterator are constant iterators. For std::unordered_map and std::unordered_multimap the value type is std::pair<const Key, T>.

Elements in an unordered associative container are organized into buckets, keys with the same hash will end up in the same bucket. The number of buckets is increased when the size of the container increases to keep the average number of elements in each bucket under a certain value.

Rehashing invalidates iterator and might cause the elements to be re-arranged in different buckets but it doesn't invalidate references to the elements.

Unordered associative containers meet the requirements of AllocatorAwareContainer. For std::unordered_map and std::unordered_multimap the requirements of value_type in AllocatorAwareContainer apply to key_type and mapped_type (not to value_type).

Requirements

Legend

X Container type
a Object of type X
b const Object of type X
a_uniq Object in X when X supports unique keys
a_eq Object in X when X supports multiple equivalent keys
i, j LegacyInputIterators denoting a valid range
p, q2 valid const_iterator to a
q, q1 dereferenceable const_iterator to a denoting a valid range
il Object of std::initializer_list<X::value_type>
t Object of type X::value_type
k Object of type X::key_type
hf const Object of type X::hasher
eq const Object of type X::key_equal
n Value of type X::size_type
z Value of type float

ExpressionReturn typePre/RequirementsPost/EffectsComplexity
X::key_typeKeycompile time
X::mapped_typeTstd::unordered_map and std::unordered_multimap onlycompile time
X::value_typeKeystd::unordered_set and std::unordered_multiset only. Erasable in Xcompile time
X::value_typestd::pair<const Key, T>std::unordered_map and std::unordered_multimap only. Erasable in Xcompile time
X::hasherHashHashcompile time
X::key_equalPredBinaryPredicate taking two arguments of type Key and expressing an equivalence relation.compile time
X::local_iteratorAn LegacyIterator whose category and types are the same as X::iteratorCan be used to iterate through a single bucketcompile time
X::const_local_iteratorAn LegacyIterator whose category and types are the same as X::const_iteratorCan be used to iterate through a single bucketcompile time
X(n,hf,eq)Xhasher and key_equal CopyConstructibleConstructs an empty container with at least n buckets, using the given hash function and equality predicatelinear in n
X(n,hf)Xhasher CopyConstructible , key_equal DefaultConstructibleConstructs an empty container with at least n buckets, using the given hash function and key_equal() as equality predicatelinear in n
X(n)Xhasher and key_equal DefaultConstructibleConstructs an empty container with at least n buckets, using hasher() as hash function and key_equal() as equality predicatelinear in n
X()Xhasher and key_equal DefaultConstructibleConstructs an empty container with an unspecified number of buckets, using hasher() as hash function and key_equal() as equality predicateconstant
X(i,j,n,hf,eq)Xhasher and key_equal CopyConstructible, value_type EmplaceConstructible into X from *iConstructs an empty container with at least n buckets, using the given hash function and equality predicate, and inserts elements from [i,j) into it.average linear, worst quadratin (on the distance between i and j)
X(i,j,n,hf)Xkey_equal DefaultConstructibleAs above, with eq=key_equal()see above
X(i,j,n)Xhasher DefaultConstructibleAs above, with hf=hasher()see above
X(i,j)XAs above, with an unspecified number of bucketssee above
X(il)XX(il.begin(),il.end()see above
X(il,n)XX(il.begin(),il.end(),nsee above
X(il,n,hf)XX(il.begin(),il.end(),n,hfsee above
X(il,n,hf,eq)XX(il.begin(),il.end(),n,hf,eqsee above
X(b)XCopy constructors, also copies the hash function, predicate and maximum load factoraverage linear, worst quadratic (in b.size())
a = bX&Copy assignment, also copies the hash function, predicate and maximum load factoraverage linear, worst quadratic (in b.size())
a = ilX&value_type CopyAssignable andCopyInsertable into Xa = X(il)see above
uwaga

This section is incomplete
Reason: Unfinished requirements regarding member functions

Unordered associative containers in the standard library

pubstd::unordered_set(C++11)collection of unique keys, hashed by keys
pubstd::unordered_multiset(C++11)collection of keys, hashed by keys
pubstd::unordered_map(C++11)collection of key-value pairs, hashed by keys, keys are unique
pubstd::unordered_multimap(C++11)collection of key-value pairs, hashed by keys

C++ named requirements: UnorderedAssociativeContainer (od C++11)

Unordered associative containers are Containers that provide fast lookup of objects based on keys. Worst case complexity is linear but on average much faster for most of the operations.

Unordered associative containers are parametrized by Key; Hash, a Hash function object which acts as hash function on Key; and Pred, a BinaryPredicate evaluating equivalence between Keys. std::unordered_map and std::unordered_multimap also have a mapped type T associated with the Key.

If two Keys are equal according to Pred, Hash must return the same value for both keys.


If both Hash::is_transparent and Pred::is_transparent exist and each names a type, member functions find, contains, count, and equal_range accept arguments of types other than Key and expect that Hash is callable with values of those types, and that Pred is a transparent comparison function such as std::equal_to<>. (od C++20)

std::unordered_map and std::unordered_set can contain at most one element with a given key, std::unordered_multiset and std::unordered_multimap instead can have multiple elements with the same key (which must always be adjacent on iterations).

For std::unordered_set and std::unordered_multiset the value type is the same as the key type and both iterator and const_iterator are constant iterators. For std::unordered_map and std::unordered_multimap the value type is std::pair<const Key, T>.

Elements in an unordered associative container are organized into buckets, keys with the same hash will end up in the same bucket. The number of buckets is increased when the size of the container increases to keep the average number of elements in each bucket under a certain value.

Rehashing invalidates iterator and might cause the elements to be re-arranged in different buckets but it doesn't invalidate references to the elements.

Unordered associative containers meet the requirements of AllocatorAwareContainer. For std::unordered_map and std::unordered_multimap the requirements of value_type in AllocatorAwareContainer apply to key_type and mapped_type (not to value_type).

Requirements

Legend

X Container type
a Object of type X
b const Object of type X
a_uniq Object in X when X supports unique keys
a_eq Object in X when X supports multiple equivalent keys
i, j LegacyInputIterators denoting a valid range
p, q2 valid const_iterator to a
q, q1 dereferenceable const_iterator to a denoting a valid range
il Object of std::initializer_list<X::value_type>
t Object of type X::value_type
k Object of type X::key_type
hf const Object of type X::hasher
eq const Object of type X::key_equal
n Value of type X::size_type
z Value of type float

ExpressionReturn typePre/RequirementsPost/EffectsComplexity
X::key_typeKeycompile time
X::mapped_typeTstd::unordered_map and std::unordered_multimap onlycompile time
X::value_typeKeystd::unordered_set and std::unordered_multiset only. Erasable in Xcompile time
X::value_typestd::pair<const Key, T>std::unordered_map and std::unordered_multimap only. Erasable in Xcompile time
X::hasherHashHashcompile time
X::key_equalPredBinaryPredicate taking two arguments of type Key and expressing an equivalence relation.compile time
X::local_iteratorAn LegacyIterator whose category and types are the same as X::iteratorCan be used to iterate through a single bucketcompile time
X::const_local_iteratorAn LegacyIterator whose category and types are the same as X::const_iteratorCan be used to iterate through a single bucketcompile time
X(n,hf,eq)Xhasher and key_equal CopyConstructibleConstructs an empty container with at least n buckets, using the given hash function and equality predicatelinear in n
X(n,hf)Xhasher CopyConstructible , key_equal DefaultConstructibleConstructs an empty container with at least n buckets, using the given hash function and key_equal() as equality predicatelinear in n
X(n)Xhasher and key_equal DefaultConstructibleConstructs an empty container with at least n buckets, using hasher() as hash function and key_equal() as equality predicatelinear in n
X()Xhasher and key_equal DefaultConstructibleConstructs an empty container with an unspecified number of buckets, using hasher() as hash function and key_equal() as equality predicateconstant
X(i,j,n,hf,eq)Xhasher and key_equal CopyConstructible, value_type EmplaceConstructible into X from *iConstructs an empty container with at least n buckets, using the given hash function and equality predicate, and inserts elements from [i,j) into it.average linear, worst quadratin (on the distance between i and j)
X(i,j,n,hf)Xkey_equal DefaultConstructibleAs above, with eq=key_equal()see above
X(i,j,n)Xhasher DefaultConstructibleAs above, with hf=hasher()see above
X(i,j)XAs above, with an unspecified number of bucketssee above
X(il)XX(il.begin(),il.end()see above
X(il,n)XX(il.begin(),il.end(),nsee above
X(il,n,hf)XX(il.begin(),il.end(),n,hfsee above
X(il,n,hf,eq)XX(il.begin(),il.end(),n,hf,eqsee above
X(b)XCopy constructors, also copies the hash function, predicate and maximum load factoraverage linear, worst quadratic (in b.size())
a = bX&Copy assignment, also copies the hash function, predicate and maximum load factoraverage linear, worst quadratic (in b.size())
a = ilX&value_type CopyAssignable andCopyInsertable into Xa = X(il)see above
uwaga

This section is incomplete
Reason: Unfinished requirements regarding member functions

Unordered associative containers in the standard library

pubstd::unordered_set(C++11)collection of unique keys, hashed by keys
pubstd::unordered_multiset(C++11)collection of keys, hashed by keys
pubstd::unordered_map(C++11)collection of key-value pairs, hashed by keys, keys are unique
pubstd::unordered_multimap(C++11)collection of key-value pairs, hashed by keys