unordered_multiset

 Overview

 The standard library provides unordered_multiset to store keys in a lookup table. The keys are unsorted and nonunique.

Details

unordered_multiset is basically a unsorted hash table of non unique elements that can be used to search and retrieve elements fast. elements are stored in buckets using the hash function provided as the template parameter. 

A bucket is a slot in the container's internal hash table to which elements are assigned based on their hash value.

Syntax

The syntax is as below. Template parameter Key represents the datatype to store, Hash represents hash function object to generate, Pred represents comparison function object  to compare two Key data types and Alloc represents the allocator used for storage.

template <class Key, class Hash = hash<Key>, class Pred = equal_to<Key>, class Alloc = allocator<Key>> 
class unorered_multiset;

Members

 It defines following types

Name	Description
key_type	The first template parameter (Key)
value_type	The first template parameter (Key)
hasher	The second template parameter (Hash)
key_equal	The third template parameter (Pred)
allocator_type	The third template parameter (Alloc)
reference	value_type&
const_reference	const value_type&
pointer	allocator_traits<allocator_type>::pointer
const_pointer	allocator_traits<allocator_type>::const_pointer
iterator	forward iterator to value_type convertible to const_iterator
const_iterator	forward iterator to const value_type
local_iterator	Same as iterator. This iterator can be used to iterate through a single bucket but not across buckets.
const_local_iterator	Same as const_iterator. This iterator can be used to iterate through a single bucket but not across buckets.
difference_type	a signed integral type
size_type	an unsigned integral type

Operation

unordered_multiset can be graphically represented as below. It's basically a hashtable. It holds values [1,2,3,4,5,3].

New elements can be added or removed or searched in the unordered_multiset .  A hashtable is internally used for storage. 

As shown above, a hashtable basically comprises of multiple  buckets where the elements are stored. The hash function determines to which bucket the element will go. A bucket can contain multiple elements in such case, equal_to function is used to determine correct element.

The hashtable can be created with a user defined value. Otherwise a default value is used. Similarly custom hash and equal_to functions can be supplied. Otherwise default hash and equal_to function objects are used for hashing and equality checks.

The load_factor influences the probability of collision in the hash table (i.e., the probability of two elements being located in the same bucket). load_factor is calculated as 

load_factor = size / bucket_count.

The container automatically increases the number of buckets to keep the load factor below  max_load_factor, causing a rehash each time an expansion is needed. This will invalidate iterators.

reserve can be used allocate more buckets.

Complexity

The cost of Insertion or removal or search is O(1).

Functionality

Constructors

In following constructors use default values. Custom number of buckets, custom hash, custom compare operations, custom allocators can be supplied  by passing them as an additional arguments. 

Name	Description
unordered_multiset ()	Default Constructor. Example: //v:{} unordered_multiset<int> v;
unordered_multiset (InputIterator first, InputIterator last)	Constructs a set and copies the elements in the range. Example: int a[]{1,2,3,4,5,3}; //v:{5,4,3,3,2,1} unordered_multiset<int> v(begin(a),end(a));
unordered_multiset (const unordered_multiset & x)	copy constructor.
unordered_multiset (unordered_multiset && x)	move constructor.
unordered_multiset (initializer_list<value_type> il)	initializer_list constructor. Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3});

Iterator

Name	Description
iterator begin() iterator end()	Returns iterator to beginning and end of the unordered_multiset . Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //prints 5 4 3 3 2 1 for (auto itr=v.begin(); itr!=v.end(); ++itr) cout << *itr << ' ';
const_iterator cbegin() const_iterator cend()	Returns const_iterator to beginning and end of the unordered_multiset. Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //prints 1 2 3 3 4 5 for (auto itr=v.cbegin(); itr!=v.cend(); ++itr) cout << *itr << ' ';

Capacity

Name	Description
size_type size()	Returns the number of elements in the unordered_multiset. Example: unordered_multiset<int> v({1,2,3,4,5,3}); //prints 6 cout << v.size();
size_type max_size()	Returns maximum  possible number of elements possible. A very large number.
bool empty()	Test whether unordered_multiset  is empty.

Element Access

Name	Description
iterator find(const value_type& val)	Returns iterator to the first element or end if not found. Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //itr = v.begin()+4 auto itr = v.find(2); //itr = v.begin()+2 itr = v.find(3); //itr = v.end() itr = v.find(6);
size_type count (const value_type& val)	Returns number of elements matching val. Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //knt=1 auto knt = v.count(2); //knt=2 knt = v.count(3); //knt=0 knt = v.count(6);
iterator lower_bound(const value_type& val) iterator upper_bound(const value_type& val)	Returns iterator to the first element matching val or end Returns iterator next to the last  element matching val or end. Note that end will be returned if matching element is the last in the set.
Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //itr = v.begin()+4 auto itr = v.lower_bound(2); //itr = v.begin()+5 itr = v.upper_bound(2); //itr = v.begin()+2 itr = v.lower_bound(3); //itr = v.begin()+4 itr = v.upper_bound(3); //itr = v.begin()+5 itr = v.lower_bound(1); //itr = v.end() itr = v.upper_bound(5); //itr = v.end() itr = v.lower_bound(6); //itr = v.end() itr = v.upper_bound(6);
pair<iterator,iterator>  equal_range(const value_type& val)	Returns a pair object containing lower_bound and upper_bound iterators matching value val. Example: //v:{5,4,3,3,2,1} unordered_set<int> v({1,2,3,4,5,3}); //p: {v.begin()+4,v.begin()+5} auto p = v.equal_range(2); //p: {v.begin()+2,v.begin()+4} p = v.equal_range(3); //p: {v.begin()+0,v.begin()+1} p = v.equal_range(5); //p: {v.end(),v.end()} p = v.equal_range(6);

Modifiers

iterator emplace(Args ...arg)

Constructs and inserts an element using arg. Returns a pair object containing an iterator to the inserted element and true if succeeded or an iterator to the existing element and false on failure. Example: unordered_multiset<int> v({1,2,3,4,5,3}); //v:{5,4,3,3,2,2,1} //itr: v.begin()+4 auto itr = v.emplace(2); //v:{6,5,4,3,3,2,2,1}1 //itr: v.begin()p = v.emplace(6);

iterator emplace_hint(iterator hintpos, Args ...arg))

Constructs and attempts to insert an element at the hintpos using arg. If returns an iterator to the new element or existing element. Note that the hintpos is used as starting point to scout to add new element. It  will go round robin if the scout is exhausted. Example: //v:{5,4,3,3,2,1} unordered_multiset<int> v({1,2,3,4,5,3}); //v:{5,4,3,3,2,2,1} //itr = v.begin()+4 auto itr = v.emplace_hint(begin(v), 2); //v:{6,5,4,3,3,2,2,1} //itr = v.begin() itr = v.emplace_hint(begin(v), 6);

Buckets

Name	Description
size_type bucket_count()	Returns the number of buckets in the unordered_multiset. Example: unordered_multiset<int> v({1,2,3,4,5,3}); //prints Buckets # : 7 cout << "Buckets # : " << v.bucket_count();
size_type max_bucket_count()	Returns maximum  possible number of buckets possible. A very large number.
size_type  bucket_size(size_type  n)	Returns number of elements in the current bucket. Example: unordered_multiset<int> v({1,2,3,4,5,3}); vector<int> v2; unique_copy(v.begin(),v.end(),back_inserter(v2)); cout << "bucket\tbucket_size" << endl; for ( auto i:v2) cout << v.bucket(i) << "\t" << v.bucket_size(v.bucket(i)) << endl; /* bucket bucket_size 5 1 4 1 3 2 2 1 1 1 */
size_type  bucket(const key_type key)	Returns the bucket number where the key is located. Example: unordered_multiset<int> v({1,2,3,4,5,3}); cout << "key\tbucket" << endl; for ( auto itr=v.begin(); itr != v.end(); ++itr) cout << *itr << "\t" << v.bucket(*itr) << endl; /* key bucket 5 5 4 4 3 3 3 3 2 2 1 1 */

Hash Policy

Name	Description
size_type load_factor()	Returns the current load factor. It needs to stay under  or equal to max_load_factor(). Example: unordered_multiset<int> v({1,2,3,4,5,3}); cout << "size = \t\t" << v.size() << endl; cout << "bucket_count = \t" << v.bucket_count() << endl << endl; cout << "load_factor = size() / bucket_count()" << endl << endl; cout << "load_factor = \t\t" << v.load_factor() << endl; cout << "max_load_factor = \t" << v.max_load_factor() << endl; /* output: size = 6 bucket_count = 7 load_factor = size() / bucket_count() load_factor = 0.857143 max_load_factor = 1 */
float max_load_factor()  void max_load_factor(float z)	Returns current maximum  load factor  Sets current maximum  load factor
Example: float amlf[]{1.0f,0.5f}; for (auto clf :amlf) { unordered_multiset<char> v; v.max_load_factor (clf); for (auto c='a'; c <= 'z'; ++c) v.emplace(c);     cout << "max_load_factor: " << v.max_load_factor() << endl;     cout << "size: " << v.size() << endl;     cout << "bucket_count: " << v.bucket_count() << endl;     cout << "load_factor: " << v.load_factor() << endl;     cout << endl;     } /* output: max_load_factor: 1 size: 26 bucket_count: 29 load_factor: 0.896552 max_load_factor: 0.5 size: 26 bucket_count: 97 load_factor: 0.268041 */
void reserve(size_type  n)	Sets the number of buckets in the container to hold at least  n elements. Example: unordered_multiset<int> v; cout << "bucket_count before reserve: " << v.bucket_count() << endl; v.reserve(10); v.insert({1,2,3,4,5,3}); cout << "bucket_count after reserve: " << v.bucket_count() << endl; /* output: bucket_count before reserve: 1 bucket_count after reserve: 11 */
void rehash(size_type  n)	Sets the number of buckets in the container to n or more. Example: unordered_multiset<int> v; cout << "bucket_count before rehash: " << v.bucket_count() << endl; v.rehash(10); cout << "bucket_count after rehash: " << v.bucket_count() << endl; /* output: bucket_count before rehash: 1 bucket_count after rehash: 11 */