unordered_map 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 

Parameter  Description
KeyIt has a type of key values as each element in an unordered map is uniquely identified by its key value.  
TType of mapped value as each element in an unordered map is used to store some data as its mapped value.
HashA unary function object type that takes an object of type key type as an argument and returns a unique value of the type size_t based on it. This can be either a class implementing a function call operator or a pointer to function. This defaults to hash<key>, which return a hash value with a Probability of the collision approaching 1.0/std :: numeric_limits <size_t> :: max().The unordered map object uses the hash values returned by this function to organise its elements internally, speeding up the process of locating individual elements.
PredA binary predicate that takes up two arguments of the key type and returns a bool. The expression pred(a,b), where ‘pred’ is an object of this type, and a and b are key values, shall return true if a is to be considered equivalent to b. This can be either a class implementing a function call operator or a pointer to a function (see the constructor for an example). This defaults to the equal_to<Key>, which returns the same as applying the equal-to operator (a==b). The unordered_map object uses this expression to determine whether two-element keys are equivalent. No two elements in an unordered_map container can have keys that yield true using this predicate.
AllocIt is a type of allocator object used to define the storage allocation model. The allocator class template is used by default, which defines the simplest memory allocation model and is value-independent.

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):

 typedef pair<const Key, T> value_type;
  1. iterator begin();
    const_iterator begin() const;
Returns:An iterator that refers to the first element of the container or, if the box is empty, the past-the-end value for the container.
  1. iterator end();
    const_iterator end() const;
Returns:An iterator referring to the past-the-end value for the container.
  1. const_iterator cbegin() const;
Returns:A constant iterator that refers to the first element of the container, or if the container is empty, the past-the-end value for the container.
  1. const_iterator cend() const;
Returns:A constant iterator referring to the past-the-end value for the container.

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:

member typedefinitionnotes
key_typethe first template parameter (Key)
mapped_typethe second template parameter (T)
value_typepair<const key_type,mapped_type>
hasherthe third template parameter (Hash)defaults to: hash<key_type>
key_equalthe fourth template parameter (Pred)defaults to: equal_to<key_type>
allocator_typethe fifth template parameter (Alloc)defaults to: allocator<value_type>
referencevalue_type&
const_referenceconst value_type&
pointerallocator_traits<Alloc>::pointerfor the default allocator: value_type*
const_pointerallocator_traits<Alloc>::const_pointerfor the default allocator: const value_type*
iteratora forward iterator to value_type
const_iteratora forward iterator to const value_type
local_iteratora forward iterator to value_type
const_local_iteratora forward iterator to const value_type
size_typean unsigned integral typeusually the same as size_t
difference_typea signed integral typeusually the same as ptrdiff_t


Methods of unordered_map in C++:

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)

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;
}

Output:

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.

0

LEAVE A REPLY

Please enter your comment!
Please enter your name here

nine − 1 =