Unordered map in C++ STL

Open-Source Internship opportunity by OpenGenus for programmers. Apply now.

Reading time: 45 minutes

By its name we can say that it comes under Associative containers with Unordered property. We know that any unordered container internally implemented with hash tables. So same has hashing concept in worst case any operation takes O(n) time and in average and best case it takes O(1) time. We can say it vary based on type of hash function we used. With comparison to map containers these work efficiently to find value by using key. And one main difference is that map elements are order but unordered map elements are not in order. Since it is based on key-value pair concept all keys must be unique.

In more general terms, Unordered map is a dictionary like data structure. It is a sequence of (key, value) pair, where only single value is associated with each unique key. It is often referred to as associative array. It enables fast retrieval of individual elements based on their keys. It also implements the direct access operator(subscript operator[]) which allows for direct access of the mapped value using its key value as argument.

Unordered map does not sort its element in any particular order with respect to either their key or mapped values, instead organizes into buckets depending on their hash values to allow for fast access to individual elements directly by their key values.

Unordered map performs better than map while accessing individual elements by their keys. But for range iteration their performance is considerably low.

Syntax :

template < class Key,
           class T,
           class Hash = hash<Key>,
           class Pred = equal_to<Key>,
           class Alloc = allocator< pair<const Key,T> >
           > class unordered_map;

Parameters :

a. Key − Type of the key.
b. T − Type of the mapped values. It may be substituted by any other data type including user-defined type.
c. Hash − A unary function object type which takes an object of type key type as argument and returns a unique value of type size_t based on it.
d. Pred − A binary predicate that which two arguments of the key type and returns a bool.
e. Alloc − Type of the allocator object.where Allocators are objects responsible for encapsulating memory management. std::allocator is used when you want to separate allocation and do construction in two steps. It is also used when separate destruction and deallocation is done in two steps.All the STL containers in C++ have a type parameter Allocator that is by default std::allocator. The default allocator simply uses the operators new and delete to obtain and release memory.

Member types

Following member types can be used as parameters or return type by member functions:

1. key_type	     :   Key (First parameter of the template)
2. mapped_type	 :   T (Second parameter of the template)
3. value_type	 :   pair<const key_type,mapped_type>
4. hasher	     :   The third template parameter (defaults to: hash<key_type>)
5. key_equal	 :   The fourth template parameter (defaults to: equal_to<key_type>)
6. allocator_type      :  Alloc (Fifth parameter of the template)
7. reference           :  value_type&
8. const_reference	   :  const value_type&
9. pointer	           :  allocator_traits<Alloc>::pointer
10. const_pointer      :  allocator_traits<Alloc>::const_pointer
11. iterator           :  A forward iterator to value_type value_type
12. const_iterator     :  A forward iterator to const value_type value_type
13. local_iterator     :  A forward iterator to value_type
14. const_local_iterator	: A forward iterator to const value_type
15. difference_type     	: ptrdiff_t
16. size_type               : size_t

Methods of unordered_map :

The most commonly used methods are:

at()
begin()
end()
bucket()
bucket_count() / bucket_size()
count()
equal_range()
hash_function()
insert()
reserve()
load_factor()

1. at() :

It returns a reference to the mapped value associated with key k.

Syntax of `at()`

unordered_map.at(k);

Parameter : It is the key value of the element whose mapped value we want to access.
Return type : A reference to the mapped value of the element with a key value equivalent

Note : The method gives run-time error if key is not present.

Practical Application : This function can be used to access the mapped value and thus can edit, update etc.

Example :

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   cout << "Value of key um['a'] = " << um.at('a') << endl;

   try {
      um.at('z');
   } catch(const out_of_range &e) {
      cerr << "Exception at " << e.what() << endl;
   }

   return 0;
}

Output

Value of key um['a'] = 1
Exception at _Map_base::at

2. `begin()` :

It is a built-in function in C++ STL which returns an iterator pointing to the first element in the unordered_map container or in any of its bucket.

a. unordered_map begin() container :
It returns an iterator which refers to the first element of the map.

Syntax

unordered_map.begin()

Parameters : This function does not accepts any parameters.
Return Value : If object is constant qualified then method returns constant iterator otherwise it returns non-constant reference.

Note : In an unordered map, there is no specific element which is considered as the first element.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   cout << "Unordered map contains following elements: " << endl;

   for (auto it = um.begin(); it != um.end(); ++it)
      cout << it->first << " = " << it->second << endl;

   return 0;
}

Output

Unordered map contains following elements: 
e = 5
a = 1
b = 2
c = 3
d = 4

b. `unordered_map begin() bucket` :

It returns an iterator pointing to the first element in one of its buckets.

Syntax

unordered_map.begin( n )

Parameters : The function accepts one mandatory parameter n which specifies the bucket number whose first element’s iterator is to be returned.
Return Value : The function returns an iterator pointing to the first element in the n-th bucket.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   for (int i = 0; i < um.bucket_count(); ++i) {
      cout << "Bucket " << i << " contains:" << endl;

      for (auto it = um.begin(i); it != um.end(i); ++it)
         cout << it->first << " = " << it->second << endl;
   }

   return 0;
}

Output

Bucket 0 contains:
b = 2
Bucket 1 contains:
c = 3
Bucket 2 contains:
d = 4
Bucket 3 contains:
e = 5
Bucket 4 contains:
Bucket 5 contains:
Bucket 6 contains:
a = 1

3. `end()` :

It is a built-in function in C++ STL which returns an iterator pointing to the position past the last element in the container in the unordered_map container. In an unordered_map object, there is no guarantee that which specific element is considered its first element. But all the elements in the container are covered since the range goes from its begin to its end until invalidated.

Syntax:

iterator unordered_map_name.end(n)

Parameters : This function accepts one parameter n which is an optional parameter that specifies the bucket number. If it is set, the iterator retrieves points to the past-the-end element of a bucket, otherwise, it points to the past-the-end element of the container.
Return value : The function returns an iterator to the element past the end of the container.

a. `unordered_map end container iterator` :

It returns an iterator which points to past-the-end element in the unordered_map.

Syntax

iterator unordered_map_name.end()

**Parameters : ** None
Return value : If object is constant qualified then method returns constant iterator otherwise non-constant iterator.

Exceptions :

This member function never throw exception.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   cout << "Unordered map contains following elements" << endl;

   for (auto it = um.begin(); it != um.end(); ++it)
      cout << it->first << " = " << it->second << endl;

   return 0;
}

Output

Unordered map contains following elements
e = 5
a = 1
b = 2
c = 3
d = 4

b. `unordered_map end bucket iterator` :

It returns an iterator which points to past-the-end element in one of its buckets.

Syntax:

iterator unordered_map_name.end(n)

Parameters : n − Bucket number
Return value : If object is constant qualified then method returns constant iterator otherwise it returns non-constant reference.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   for (int i = 0; i < um.bucket_count(); ++i) {
      cout << "Bucket " << i << " contains:" << endl;

      for (auto it = um.begin(i); it != um.end(i); ++it)
         cout << it->first << " = " << it->second << endl;
   }

   return 0;
}

Output

Bucket 0 contains:
c = 3
Bucket 1 contains:
d = 4
Bucket 2 contains:
e = 5
Bucket 3 contains:
Bucket 4 contains:
Bucket 5 contains:
Bucket 6 contains:
Bucket 7 contains:
Bucket 8 contains:
Bucket 9 contains:
a = 1
Bucket 10 contains:
b = 2

4. `bucket()` :

It is a built-in STL function in C++ which returns the bucket number where the element with the key k is located in the map.
Bucket is a memory space in the container's hash table to which elements are assigned based on the hash value of their key. Valid range of buckets is from 0 to bucket_count - 1.

Syntax:

size_type bucket(key)

Parameter : The function accepts one mandatory parameter key which specifies the key whose bucket number is to be returned.
Return Value : This method returns an unsigned integral type which represents the bucket number of the key k which is passed in the parameter.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   for (auto it = um.begin(); it != um.end(); ++it) {
      cout << "Element " << "[" << it->first  << " : "
          << it->second << "] " << "is in " 
          << um.bucket(it->first) << " bucket." << endl; 
   }

   return 0;
}

Output

Element [e : 5] is in 3 bucket.
Element [d : 4] is in 2 bucket.
Element [c : 3] is in 1 bucket.
Element [b : 2] is in 0 bucket.
Element [a : 1] is in 6 bucket.

5. `bucket_count` and `bucket_size` :

a. bucket_count() :

This function is used to count the total no. of buckets in the unordered_map. No parameter is required to pass into this function.

Syntax

unordered_map.bucket_count();

Parameters : None
Return value : Returns the total number of bucket present in the unordered_map.

Exceptions

This member function does not throw exception.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   cout << "Number of buckets = " << um.bucket_count() << endl;

   return 0;
}

Output

Number of buckets = 11

b. bucket_size() :

This function count the number of elements present in each bucket of the unordered_map.

Syntax

unordered_map.bucket_size(i);

where 'i' is the bucket number in which we want 
to find no. of elements. (i < bucket_count)

Parameters : n − Bucket number.
Return value : Returns the total number of elements from current bucket.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   for (int i = 0; i < um.bucket_count(); ++i)
      cout << "Bucket " << i << " contains "
          << um.bucket_size(i) << " elements." << endl;

   return 0;
}

Output

Bucket 0 contains 1 elements.
Bucket 1 contains 1 elements.
Bucket 2 contains 1 elements.
Bucket 3 contains 0 elements.
Bucket 4 contains 0 elements.
Bucket 5 contains 0 elements.
Bucket 6 contains 0 elements.
Bucket 7 contains 0 elements.
Bucket 8 contains 0 elements.
Bucket 9 contains 1 elements.
Bucket 10 contains 1 elements.

6. `count()` :

It is a builtin method in C++ which is used to count the number of elements present in an unordered_map with a given key.

Note : As unordered_map does not allow to store elements with duplicate keys, so the count() function basically checks if there exists an element in the unordered_map with a given key or not.

Syntax :

size_type count(Key);

Parameters : This function accepts a single parameter key which is needed to be checked in the given unordered_map container.
Return Value : This function returns 1 if there exists a value in the map with the given key, otherwise it returns 0.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            {'d', 4},
            {'e', 5}
            };

   cout << "Number of buckets = " << um.bucket_count() << endl;

   return 0;
}

Output

Number of buckets = 11

7. `equal_range()` :

It is an inbuilt function in C++ STL which is used to return the bounds of a range that includes all the elements in the container with a key that compares equal to k.

The unordered_map containers are the container where keys are unique, the range will include one element at most. The range is defined by two iterators,

The first one pointing to the first element of the range.
The second one pointing past the last element of the range.

Syntax

unordered_map.equal_range(k)

Parameters : This function accepts single parameter key which is used to hold the value to be compared.
Return Value : It returns a pair which contains a pair of iterators defining the wanted range. Where its members are pair::first and pair::second. The first one is an iterator to the lower bound of the range and the second one is an iterator to its upper bound. The elements in the range are those between these two iterators, including first pair, but not second.

Example

#include <iostream> 
#include <unordered_map> 
using namespace std; 
  
// main program 
int main() 
{ 
    unordered_map <int, int> map = { { 1, 3 },  
                                     { 1, 2 },  
                                     { 3, 1 },  
                                     { 2, 3 } }; 
    for (int j = 1; j <= 3; j++) { 
        auto range = map.equal_range(j); 
          
        //'auto' is a keyword 
        for (auto i = range.first; i != range.second; i++) { 
              
            // iterates first to last 
            cout << "first : " << i->first; 
            cout << "\nsecond : " << i->second << endl 
                << endl; 
        } 
    } 
}

Output

first : 1
second : 3

first : 2
second : 3

first : 3
second : 1

8. `hash_function()` :

It Calculates the hash function object used by the unordered_map container.
The hash function is a unary function that takes an object of type key_type as argument and returns a unique value of type size_t based on it.

Syntax

unordered_map.hash_function()

Parameters : None
Return value : Returns the hash function.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map <string, string> um;

   auto fun = um.hash_function();

   cout << "Hash function for a = " << fun("a") << endl;
   cout << "Hash function for A = " << fun("A") << endl;

   return 0;
}

Output

Hash function for a = 4993892634952068459
Hash function for A = 6919333181322027406

9. `insert()` :

This function can be of various types depending upon its application
It can be :
i. unordered_map::insert :
Extends container by inserting new element in unordered_map.
ii. unordered_map::insert (move version) :
Extends container by inserting new element in unordered_map.
iii. unordered_map::insert (hint version) :
Extends conta iner by inserting new element in unordered_map.
iv. unordered_map::insert (move and hint version) :
Extends unordered_map by inserting new element.
v. unordered_map::insert (range version) :
Extends container by inserting new elements in the unordered_map.
vi. unordered_map::insert (initializer_list version) :
Extends map by inserting new element from initializer list.

Example - (move version)

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um = {
            {'a', 1},
            {'b', 2},
            {'c', 3},
            };

   um.insert(move(pair<char, int>('d', 4)));
   um.insert(move(pair<char, int>('e', 5)));

   cout << "Unordered map contains following elements" << endl;

   for (auto it = um.begin(); it != um.end(); ++it)
      cout << it->first << " = " << it->second << endl;

   return 0;
}

Output

Unordered map contains following elements
e = 5
d = 4
c = 3
a = 1
b = 2

10. `reserve()` :

It sets the number of buckets in the container to the most appropriate to contain at least n elements.
If n is greater than the current bucket_count() * max_load_factor() then the container's bucket count is increased and a rehash is forced and if n is lower than that, the function may have no effect.

Note : max_load_factor returns the current maximum load factor for the unordered_map container.

Syntax

unordered_map.reserve(n)

Parameters : n − New capacity of the container.
Return value : None

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um;

   cout << "Initial bucket count = " << um.bucket_count() << endl;

   um.reserve(5);

   cout << "Bucket count after reserve = "
       << um.bucket_count() << endl;

   return 0;
}

Output

Initial bucket count = 11
Bucket count after reserve = 5

11. `load_factor()` :

It returns the current load factor of the unordered_map container.

The load factor is calculated as follows −
load_factor = um.size() / um.bucket_count()

Syntax

unordered_map.load_factor()

Parameters : None
Return value : Returns load factor

Exceptions

This member function never throws exception.

Example

#include <iostream>
#include <unordered_map>

using namespace std;

int main(void) {
   unordered_map<char, int> um;

   cout << "load_factor of unordered_map = " << um.load_factor() << endl;

   return 0;
}

Output

load_factor of unordered_map = 0

Syntax :

Member types

Methods of unordered_map :

1. at() :

Syntax of at()

Example :

Output

2. begin() :

Syntax

Example

Output

b. unordered_map begin() bucket :

Syntax

Example

Output

3. end() :

Syntax:

a. unordered_map end container iterator :

Syntax

Exceptions :

Example

Output

b. unordered_map end bucket iterator :

Syntax:

Example

Output

4. bucket() :

Syntax:

Example

Output

5. bucket_count and bucket_size :

Syntax

Exceptions

Example

Output

Syntax

Example

Output

6. count() :

Syntax :

Example

Output

7. equal_range() :

Syntax

Example

Output

8. hash_function() :

Syntax

Example

Output

9. insert() :

Example - (move version)

Output

10. reserve() :

Syntax

Example

Output

11. load_factor() :

Syntax

Exceptions

Example

Output

Syntax of `at()`

2. `begin()` :

b. `unordered_map begin() bucket` :

3. `end()` :

a. `unordered_map end container iterator` :

b. `unordered_map end bucket iterator` :

4. `bucket()` :

5. `bucket_count` and `bucket_size` :

6. `count()` :

7. `equal_range()` :

8. `hash_function()` :

9. `insert()` :

10. `reserve()` :

11. `load_factor()` :