unordered_multiset Class

The template class describes an object that controls a varying-length sequence of elements of type const Key. 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 serves as both 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 Hash = std::hash<Key>,
    class Pred = std::equal_to<Key>,
    class Alloc = std::allocator<Key> >
    class unordered_multiset;

Parameters

Parameter	Description
Key	The key type.
Hash	The hash function object type.
Pred	The equality comparison function object type.
Alloc	The allocator class.

Members

Type Definition	Description
unordered_multiset::allocator_type	The type of an allocator for managing storage.
unordered_multiset::const_iterator	The type of a constant iterator for the controlled sequence.
unordered_multiset::const_local_iterator	The type of a constant bucket iterator for the controlled sequence.
unordered_multiset::const_pointer	The type of a constant pointer to an element.
unordered_multiset::const_reference	The type of a constant reference to an element.
unordered_multiset::difference_type	The type of a signed distance between two elements.
unordered_multiset::hasher	The type of the hash function.
unordered_multiset::iterator	The type of an iterator for the controlled sequence.
unordered_multiset::key_equal	The type of the comparison function.
unordered_multiset::key_type	The type of an ordering key.
unordered_multiset::local_iterator	The type of a bucket iterator for the controlled sequence.
unordered_multiset::pointer	The type of a pointer to an element.
unordered_multiset::reference	The type of a reference to an element.
unordered_multiset::size_type	The type of an unsigned distance between two elements.
unordered_multiset::value_type	The type of an element.

Member Function	Description
unordered_multiset::begin	Designates the beginning of the controlled sequence.
unordered_multiset::bucket	Gets the bucket number for a key value.
unordered_multiset::bucket_count	Gets the number of buckets.
unordered_multiset::bucket_size	Gets the size of a bucket.
unordered_multiset::cbegin	Designates the beginning of the controlled sequence.
unordered_multiset::cend	Designates the end of the controlled sequence.
unordered_multiset::clear	Removes all elements.
unordered_multiset::count	Finds the number of elements matching a specified key.
unordered_multiset::emplace	Adds an element constructed in place.
unordered_multiset::emplace_hint	Adds an element constructed in place, with hint.
unordered_multiset::empty	Tests whether no elements are present.
unordered_multiset::end	Designates the end of the controlled sequence.
unordered_multiset::equal_range	Finds range that matches a specified key.
unordered_multiset::erase	Removes elements at specified positions.
unordered_multiset::find	Finds an element that matches a specified key.
unordered_multiset::get_allocator	Gets the stored allocator object.
unordered_multiset::hash_function	Gets the stored hash function object.
unordered_multiset::insert	Adds elements.
unordered_multiset::key_eq	Gets the stored comparison function object.
unordered_multiset::load_factor	Counts the average elements per bucket.
unordered_multiset::max_bucket_count	Gets the maximum number of buckets.
unordered_multiset::max_load_factor	Gets or sets the maximum elements per bucket.
unordered_multiset::max_size	Gets the maximum size of the controlled sequence.
unordered_multiset::rehash	Rebuilds the hash table.
unordered_multiset::size	Counts the number of elements.
unordered_multiset::swap	Swaps the contents of two containers.
unordered_multiset::unordered_multiset	Constructs a container object.

Operator	Description
unordered_multiset::operator=	Copies a hash table.

Remarks

The object orders the sequence it controls by calling two stored objects, a comparison function object of type unordered_multiset::key_equal and a hash function object of type unordered_multiset::hasher. You access the first stored object by calling the member function unordered_multiset::key_eq(); and you access the second stored object by calling the member function unordered_multiset::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_set Class, an object of template class unordered_multiset does not ensure that key_eq()(X, Y) is always false for any two elements of the controlled sequence. (Keys need not be 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_multiset::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_multiset::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_set>

Namespace: std

See Also

Reference

<unordered_set>

Thread Safety in the C++ Standard Library

Standard Template Library

Concepts

Containers