unordered_map C++
FREE
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:
Scaler Placement Report and Statistics
Scaler learners achieved 2.5x salary growth with average post-Scaler CTC reaching ₹23L.
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
Transform Your Career
Choose from our industry-leading programs designed for career success
Modern Software and AI Engineering Program
Master full-stack development with AI integration
+1000 moreModern Data Science and ML with specialisation in AI
Advanced data science techniques with AI specialization
+1000 moreAdvanced AIML with Specialisation in Agentic AI
Deep dive into AIML with focus on Agentic systems
+1000 moreDevOps, Cloud & AI Platform Engineering
Build and manage AI-powered cloud infrastructure
+1000 moreAI Engineering Advanced Certification by IIT-Roorkee
Premier AI engineering certification from IIT-Roorkee
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(); |
Turn Learning into Career Growth
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.
Google
Amazon
Microsoft
Flipkart
Adobe1200+ more