unordered_map in C++

unordered_map C++

The unordered_map in C++ is like a data structure of dictionary type that store element. It has a sequence of (key, value) pair, which allows fast retrieval of an individual element based on their unique key.

The function of each unique key is to hold only a single value associated with it, and key-value is generally used to identify the element uniquely. It is often referred to as an associative array. In (key, value) pair, the mapped value is an object with content associated with each unique key. For each pair type of key and mapped value may differ.

In an unordered map, the element does not get sorted in any particular order with respect to either their key-value or mapped value. Instead, it organises values into bucket depending on their hash values that allow fast access to the individual element directly by their key values.

Note: unordered_map container performs faster than map when they have to access an individual element by their key. Generally, they get less efficient when it comes to range iteration through a subset of their elements.

Unordered_map in C++ implements the direct access operator (subscript operator []), allowing direct access of mapped value using its key value as the argument.

Example

Here is example of std:: unordered_map from <unordered_map> header file

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

Unordered_map-class template

The unordered_map class template is defined in the Standard Template Library (STL) of C++; it is a set of a Class template to use in common programming task such as in data structure and function such as in a list, stack, array etc. Usually, it is a library of container classes, algorithm, and iterators. It is a generalised library, and so, its components are parameterised.

Template Parameters 

In the reference for the unordered_map member functions, these same names (Key, T, Hash, Pred and Alloc) are assumed for the template parameters.

The elements are organised into buckets. Keys with a similar hash code are stored in the same bucket.

The number of buckets is automatically increased by a call to insert or as the result of calling rehash.

Unordered_map public types

1. typedef implementation-defined size_type;

An unsigned integral type.

‘size_type’ can represent any non-negative value of difference_type.

2. typedef implementation-defined difference_type;

A signed integral type which is identical to the difference type of iterator and ‘const_iterator’.

3. typedef implementation-defined iterator;

An iterator whose value type is the value_type.

Any iterator category except output iterator.

Convertible to const_iterator.

4. typedef implementation-defined const_iterator;

A constant iterator whose value type is the value_type.

Any iterator category except output iterator.

5. typedef implementation-defined local_iterator;

An iterator with the same value type, difference type and pointer and reference type as an iterator.

A local_iterator object could be used to iterate through a single bucket.

6. typedef implementation-defined const_local_iterator;

A constant iterator with a similar value type, difference type and pointer and reference type as the const_iterator.

A const_local_iterator object could be used to iterate through a single bucket.

Unordered_map iterators

Iterators to elements of unordered_map containers access to both the key and the mapped value. For this, the class defines what is called its value_type, which is a pair class with its first value corresponding to the const version of the key type (template parameter Key) and its second value corresponding to the mapped value (template parameter T):

1. iterator begin();
   const_iterator begin() const;

2. iterator end();
   const_iterator end() const;

3. const_iterator cbegin() const;

4. const_iterator cend() const;

Iterators of a unordered_map container point to elements of this value_type. Thus, for an iterator called it that point to an element of a map, its key and mapped value can be accessed respectively with:

Member types

The following aliases are member types of unordered_map. They are widely used as parameter and return types by member functions:

Container Properties of unordered_map:

Here are the container properties of unordered_map:

• Allocator Aware: To dynamically handle its storage needs, the container uses an allocator object.
• Map: Every element associates a key to a particular mapped value. Keys help identify the elements whose main content is the mapped value.
• Unique keys: Every element in the container has a unique key.
• Associative: In the associative container, elements are referenced by their keys and not by absolute position in the container.
• Unordered: Elements are organized using hash tables in the unordered containers to allow faster access to elements by their key.

Methods on unordered_map

Member function

• at() at() function in C++ unordered_map returns the reference to the value with the element as key k (public member function)
• operator[] Access element (public member function)
• begin() Returns an iterator that is pointing to the beginning in the container in the unordered_map container (public member function)
• end() Returns an iterator pointing to the end position past the last element in the container in the unordered_map container (public member function)
• cbegin() Return ‘const_iterator’ to beginning (public member function)
• cend() Return the const_iterator to end (public member function)
• bucket() Locate the bucket number where the element with the key k is placed in the map.(public member function)
• bucket_count () this is used to count the total no. of buckets in an unordered_map. No parameter is required to pass into this function.(public member function)
• max_bucket_count() It returns the maximum number of bucket (public member function)
• bucket_size () Returns number of elements(bucket) in each bucket of the unordered_map. (public member function)
• count() Count number of elements present in an unordered_map with a specific key.(public member function)
• equal_range() Return bounds of a range that includes all elements in the container with a key that compares equal to k.(public member function)
• find() Return iterator to the element (public member function)
• emplace() Construct and insert an element (public member function )
• emplace_hint() Construct and insert element with ‘hint’ (public member function )
• insert() Insert elements (public member function )
• erase() Erase elements (public member function )
• clear() Clear content (public member function )
• swap() Clear content (public member function )
• load_factor() Return the load factor (public member function)
• max_load_factor() Get or set the maximum load factor (public member function )
• rehash() Set the number of buckets (public member function )
• reserve() Request for a capacity change (public member function)
• hash_function() Get the hash function (public member type) 
• key_eq() Get the key equivalence predicate (public member type)
• get_alloocator() Get allocator (public member function)
• empty() Test whether the container is empty (public member function)
• size() Return the container size (public member function)
• max_size() Return the maximum size (public member function)

Non-Member function Overloads:

• swap(unordered_map): This helps to exchange the contents of two unordered_map containers.
• operators(unordered_map): Relational operators for the unordered_map.

Unordered_map Sample Code

/* m.cpp */
#include <iostream>
#include <map>
#include <unordered_map>
#include <string>

using namespace std;

int main()
{
  map<unsigned long, string> employer;
  unordered_map<unsigned long, unsigned> salary;

  employer[2014021701] = "Gaurav";
  employer[2014021702] = "Great Learning";

  for(auto e: employer)
    cout << "name: " << e.second
          << "\t id: "  << e.first << endl;

  unsigned total_payroll = 0;

  salary[2014021702] = 654321;
  salary[2014021701] = 123456;

  for(auto s: salary)
    total_payroll += s.second;

  cout << "total payrolls $" << total_payroll << endl;

  return 0;
}

unordered_map vs unordered_set

The major difference between unordered_map and unordered_set is that, unordered_set does not support key values. There is only key in unordered_set. Whereas, in unordered_map we have key as well as its value. If there is situation or a problem where you have to count the individual frequencies of each tuple in a set, you will have to use unordered_map as the latter does not support it.

unordered_map vs map

As the name gives it away, there is an orderly arrangement of the elements in the map. In unordered_map, the keys are stored in any order. A map has a balanced tree structure implementation which is the reason it is possible to maintain order between elements. The average time complexity, however, for unordered_map operations is O(1) and O(log n) for map operations.

FAQs

How is Unordered_map implemented in C++?

The unordered_map is implemented using hash tables in C++.

Is Unordered_map faster than map?

Generally, unordered_map is faster than map. But in some cases, map is faster.

Which map is faster in C++?

The unordered_map is the fastest in most of the cases in C++. The map however is faster in some of the cases.

Why is it called Unordered_map?

It is called unordered_map because the elements stored here are in a random manner. There is no order in which the keys are stored and hence the name.

What does Unordered_map return C++?

It returns a reference to the value that is mapped to a key that is equivalent to that key.

This brings us to the end of the blog on the concept of unordered_map in C++. We hope that you found this comprehensive and helpful and were able to gain the required knowledge. If you wish to up-skill and learn more such concepts, you can check out the pool of Free online courses at Great Learning Academy.

Also, if you are preparing for Interviews, check out these Interview Questions for C++ to ace it like a pro.