unordered_map C++ - Scaler Topics

Introduction

unordered_map is a data structure capable of storing data in the form of keys value pairs. It uses a hashing function to store a key-value pair, due to which the average time complexity for searching a key-value pair becomes O(1).

Syntax

In order to create an unordered_map in C++, we can use the following syntax.

Here, datatype1 is the data type of the keys and datatype2 is the data type of the values of the corresponding keys. The map_name is the name of the unordered_map variable.

For example, if we want to create an unordered_map with its key as an integer value and the value of the corresponding key has a string datatype, then it will look like this:

Example of an Unordered_Map in C++

In C++, if we want to create an unordered_map with the data type of key as datatype1 and the data type of the mapped values of the keys as datatype2, then we use the following syntax.

Output

Unordered_map Vs Map

Feature	unordered_map	map
Order of Elements	No specific order of elements.	Elements are stored in ascending order based on keys.
Data Structure	Uses a hash table (unordered).	Uses a balanced binary search tree (ordered).
Order Maintenance	Does not maintain order between elements.	Maintains order based on keys.
Time Complexity	Average Case O(1) for most operations.	O(log n) for most operations.
Lookup (find) Time Complexity	O(1) average case.	O(log n) average case.
Insertion and Deletion Time Complexity	O(1) average case.	O(log n) average case.
Memory Overhead	Typically lower memory overhead.	Slightly higher memory overhead due to balanced tree structure.
Duplicates	Does not allow duplicate keys.	Does not allow duplicate keys.
Custom Sorting	No custom sorting options.	Allows custom sorting via comparators.
Use Cases	Suitable for unordered data storage and quick access.	Suitable when elements need to be sorted or when custom ordering is required.

Unordered_map Vs Unordered_set

Feature	unordered_map	unordered_set
Element Type	Key-value pairs (elements with associated values).	Elements (no associated values, used for presence/absence checks).
Usage	Used to store and retrieve key-value pairs.	Used to check for the presence or absence of elements.
Operator [] for Value Access	Allows access to the associated value using keys.	Not applicable; no values associated with elements.
Element Search	Uses keys to search for elements.	Uses the find() function to search for elements.
Duplicate Elements	Does not allow duplicate keys (keys must be unique).	Automatically enforces uniqueness of elements.
Memory Overhead	Higher memory overhead due to key-value pairs.	Lower memory overhead as it only stores elements.
Example Use Cases	Storing data with associated values, e.g., dictionaries.	Checking for the presence of items, e.g., set operations.

Methods of unordered_map in C++

1. Member Functions

Some of the most commonly used member functions are discussed below.

Member Function	Description	Example
= Operator	Assign elements from one map to another	unordered_map<datatype1, datatype2> map_name_1 = map_name_2;
empty()	Check if the map is empty	bool is_empty = map_name.empty();
size()	Get the number of key-value pairs	int map_size = map_name.size();
max_size()	Get the maximum storage capacity	int max_capacity = map_name.max_size();
begin()	Get an iterator to the first element	auto map_begin = map_name.begin();
end()	Get an iterator to the end	auto map_end = map_name.end();
cbegin()	Get a constant iterator to the beginning	auto map_begin = map_name.cbegin();
cend()	Get a constant iterator to the end	auto map_end = map_name.cend();
[] Operator	Access an element by key	data_type mapped_value = map_name[k];
at()	Access an element by key with bounds checking	data_type mapped_value = map_name.at(k);
find()	Find an element by key	auto itr = map_name.find(k);
count()	Count the occurrences of a key	int count_k = map_name.count(k);
equal_range()	Get a range of elements by key	auto itr = map_name.equal_range(k);
insert()	Insert a key-value pair	map_name.insert({key, value});
emplace()	Insert a key-value pair efficiently	map_name.emplace(key, value);
erase()	Erase an element by iterator or key	map_name.erase(itr); or map_name.erase(k);
clear()	Erase all elements in the map	map_name.clear();

2. Non-member Function Overloads

Operators
There are two operators in unordered_map. These two operators are discussed below.

Equality operator (==) Two unordered_maps (map_name1 and map_name2) satisfy the equality operator (map_name1 == map_name2) if both the unordered_maps have the same sizes and all the key-value pairs that are present in both the unordered_maps are the same.
Inequality operator (!=) Two unordered_maps (map_name1 and map_name2) satisfy the inequality operator (map_name1!=map_name2) if either both of the maps have different sizes or there exists at least one key-value pair that is present in one of the unordered_map and not in the other.

Swap
This function is used to swap the entire contents of one unordered_map with the other unordered_map.

Time Complexity for Insertion, Deletion, and Update in unordered_map in C++

An unordered_map offers three commonly used operations: insertion, deletion, and updation.

Insertion: To insert a key 'k' and its value v into an unordered_map, you can use various syntax forms. The best and average case time complexity for insertion is O(1), while the worst case time complexity is O(n).
Deletion: Removing an element with key k from an unordered_map is accomplished with the erase method. The best and average case time complexity for deletion is O(1), with a worst-case time complexity of O(n).
Updation: Updating the value associated with a key to new_value can be done with simple assignment. The best and average case time complexity for updating is O(1), while the worst case time complexity is O(n).

Note: In all three operations, i.e., insertion, deletion, and updation, the best case scenario takes place when the hash function of the unordered_map is good and there are a minimal number of collisions that take place at respective operations. In contrast, the worst scenario takes place when the hash table of the unordered_map is not good, and a very high number of collisions occur at each operation.

C++ Unordered_map Class Template Parameters

An unordered_map in c++ is defined as follows.

Hence, it contains 5 class template parameters that are individually discussed below.

Key - This parameter defines the data type of the key values present in the unordered_map.
T - This parameter defines the data type of the keys' mapped values present in the unordered_map.
Hash - In unordered_map, each key is provided with a unique value. This unique value is used to perform insertion, deletion, and the updation operation in an unordered_map.
Pred - This parameter is a binary predicate that takes two values, a, and b, as input and returns a boolean value as an output. a and b have their data types the same as the data type of the key. By default, the Pred is set to equal_to, which means that the predicate returns true if a is equal to b. If a is not equal to b, it returns false. This parameter is useful when we have to search for a key or update the mapped value of the key in an unordered_map.
Alloc - This parameter defines how the memory is allocated when we want to insert a new key-value pair in an unordered_map. By default, Alloc uses an allocator class that allocates memory independent of what we insert in the unordered_map.

Member Types

The unordered_map class contains several data members/member types in the table below.

Member Type	Definition	Default Parameter
key_type	This defines the key's data type, i.e., the first parameter of the class template.
mapped_type	This defines the datatype of mapped values, i.e., the second parameter of the class template.
value_type	This defines data type of the key-value pair (i.e. pair<key_type,map_type>)
hasher	This defines the hash function i.e. the third parameter of the class template.	hash<key_type>
key_equal	This defines the Pred i.e. fourth parameter of the class template.	equal_to<key_type>
allocator_type	This defines the Alloc i.e. fifth parameter of the class template.	allocator<value_type>
reference	This defines the pointer to the key-value pair in the unordered_map.
const_reference	This defines the constant pointer to the key-value pair in the unordered_map.
pointer	This defines the pointer used by the allocator.	value_type*
const_pointer	This defines the constant pointer used by the allocator.	const value_type*
iterator	This defines the iterator to iterate through the key-value pairs inside the unordered_map.
const_iterator	This defines the iterator to iterate through the constant key-value pairs inside the unordered_map.
local_iterator	This defines the local iterator to iterate through the key-value pairs inside the unordered_map.
const_local_iterator	This defines the local iterator to iterate through the constant key-value pairs inside the unordered_map.
size_type	This is an unsigned int value that keeps track of the size of the unordered_map.	usually the same as size_t
difference_type	This is a signed integral data member.	usually the same as ptrdiff_t

Container Properties of Unordered_map in C++

The key-value pairs present inside the unordered_map container following five properties.

Associative: Unordered maps use key-based access, ensuring efficient value retrieval by key, irrespective of the key-value pair's position.
Unordered: Data inside an unordered_map lacks a specific order, allowing for swift average-case access without any predetermined sequence.
Mapping: Unordered maps establish a direct link between keys and values, streamlining key-based lookups and value retrieval.
Unique Keys: Unordered maps enforce key uniqueness, eliminating ambiguity by preventing duplicate keys in the container.
Allocator Aware: Unordered maps utilize allocators for flexible memory management, optimizing memory allocation and deallocation strategies for efficient storage handling.

Conclusion

Unordered_map: Stores data as key-value pairs.
Time complexity: Best and average cases are O(1), worst case is O(n).
Unordered_map vs. Unordered_set: Maps have key-value pairs, sets store individual values.
Unordered_map vs. Map: Unordered_map is unordered, Map is sorted.
Implementation: Unordered_map uses a hash table, Map uses a Red-Black tree.