C++ unordered_multiset - rehash() Function

The C++ unordered_multiset::rehash function is used to set the number of buckets in the unordered_multiset container to specified number (n) or more. If n is greater than the current number of buckets in the container (its bucket_count), a rehash is forced. The new bucket count will be either equal to or greater than n. A rehash may not be forced, if n is less than the current number of buckets in the container. A rehash is the reconstruction of the hash table in which all elements of the container is rearranged according to their hash values into the new set of buckets.

As an unordered_multiset is implemented using hash table where a bucket is a slot in the container's internal hash table to which elements are assigned based on the hash value. The number of buckets directly influences the load_factor of the container's hash table. The container automatically increases the number of buckets to keep the load_factor below its max_load_factor which causes rehash whenever the number of buckets is increased.

Syntax

• C++11

void rehash (size_type n);

Parameters

Return Value

None.

Time Complexity

Average case: Linear i.e, Θ(n).
Worst case: Quadratic i.e, Θ(n²).

Example:

In the example below, the unordered_multiset::rehash function is used to set the number of buckets in uMSet container.

#include <iostream>
#include <unordered_set>
using namespace std;
 
int main (){
  unordered_multiset<int> uMSet{55, 25, 128, 55};

  cout<<"uMSet contains "<<uMSet.bucket_count()<<" buckets:";
  for(unsigned int i = 0; i < uMSet.bucket_count(); i++) {
    cout<<"\nThe bucket #"<<i<<" contains: ";   
    for(auto it = uMSet.begin(i); it != uMSet.end(i); ++it) {
      cout<<*it<<" ";
    } 
  }  

  cout<<"\n\nNumber of buckets is changed using rehash function.\n\n";
  uMSet.rehash(7);

  cout<<"uMSet contains "<<uMSet.bucket_count()<<" buckets:";
  for(unsigned int i = 0; i < uMSet.bucket_count(); i++) {
    cout<<"\nThe bucket #"<<i<<" contains: ";   
    for(auto it = uMSet.begin(i); it != uMSet.end(i); ++it) {
      cout<<*it<<" ";
    } 
  } 

  return 0;
}

The output of the above code will be:

uMSet contains 5 buckets:
The bucket #0 contains: 25 55 55 
The bucket #1 contains: 
The bucket #2 contains: 
The bucket #3 contains: 128 
The bucket #4 contains: 

Number of buckets is changed using rehash function.

uMSet contains 7 buckets:
The bucket #0 contains: 
The bucket #1 contains: 
The bucket #2 contains: 128 
The bucket #3 contains: 
The bucket #4 contains: 25 
The bucket #5 contains: 
The bucket #6 contains: 55 55