A C++ Map is an associative container that stores elements in key-value pairs, with each key being unique and sorted automatically. It is part of the Standard Template Library (STL) and is widely used for tasks like fast data retrieval, indexing, and mapping relationships between values. Imagine you are building a student database where each roll number maps to a name; a Map makes such data handling simple and efficient. This article will explain what a C++ Map is, how it works, its properties, basic operations, member functions, usage, and practical examples for beginners.
Table of Contents:
What is a C++ Map?
In the C++ Standard Template Library (STL), a C++ Map is an associative container that stores elements in key-value pairs. By default, it sorts the elements based on the key in ascending order. It is the part of the <map> header implemented as a self-balancing binary search tree and ensures that no duplicates are allowed.
Key Characteristics of the C++ Map
Some of the key characteristics of the C++ Map are as follows:
- Each element in a Map is stored as a pair, where the key is unique.
- It is sorted by key in ascending order by default.
- A C++ Map cannot contain any duplicate keys.
- The size of a Map changes according to the elements stored in it.
Syntax of the C++ Map
Below is the syntax of the Map in C++.
map<KeyType, ValueType> mapName;
- KeyType is the data type of the key
- ValueType is the data type of the mapped value
- mapName is the name of the Map object.
What is unordered_map in C++?
An unordered_map in C++ is an associative container in the Standard Template Library (STL) that stores the elements in key-value pairs, just like a C++ map, but the elements are not stored in any sorted order. It uses a hash table for storage, which means that the order of the elements is unpredictable. It requires the #include <unordered_map> header file.
Syntax of unordered_map in C++
Below is the syntax of the unordered_map in C++.
unordered_map<KeyType, ValueType> mapName;
- KeyType is the data type of the key
- ValueType is the data type of the mapped value
- mapName is the name of the Map object.
Example:
Output:
Explanation: In the above program, the unordered_map is created named marks, storing the marks of candidates. The values are displayed from the unordered_map as shown below.
Declaration and Initialization of C++ Map
A Map in C++ must be declared before it can store the elements, and we can initialize a Map in C++ in several ways, as shown below.
1. Empty Initialization
In this initialization, we create a Map with no elements, and the elements are inserted into it later using the insert() or operator[] dynamically from the user. It is useful when you don’t have data at the time of declaration.
Example:
map<int, string> students; // empty map
students[101] = "Ali";
students.insert({102, "Bobby"});
In the above example, the Map students is declared with the data type int as key and string as value. After that, the values are inserted into the Map using the operator[] and insert().
2. Direct Initialization
This type of initialization was introduced in C++11 and allows you to create a Map with predefined elements in a clean and readable way. It is useful when you already know all the key-value pairs.
Example:
map<int, string> students = {
{101, "Ali"},
{102, "Bobby"}
};
In the above example, the values in the Map students are stored at initialization.
3. Initialization Using pair
In this initialization, the Map stores elements as a pair<const Key, T> and creates a pair of objects to initialize the map. It is useful when you want to focus on the key-value structure and you are using a function like make_pair.
Example:
map<int, string> students({
pair<int, string>(101, "Ali"),
pair<int, string>(102, "Bobby")
});
In the above example, the values in the Map students are stored using the pair<int, string> class template, where the first element is the key and the second element is the value.
Basic Operations in a C++ Map
Below are some basic operations in the Map in C++.
1. Inserting the Elements
A Map in C++ stores the value in key-value pairs, in which every key in it is unique. If you try to insert an element without specifying a key, insert() will fail, whereas operator[] will insert or update the key’s value. The insertion into a Map can be performed in the following ways.
1. insert(): It adds a new pair to the Map without replacing the existing key, and if the key is already present, the insertion is ignored.
2. operator[]: The subscript can perform both insertion and update operations. If the key is not present, a new entry is created with the given value, and the existing value is replaced.
Example:
Output:
Explanation: In the above program, the Map students1 uses insert(pair<int, string>(key, value)) to add elements, and the Map students2 uses the operator[] to insert values.
2. Accessing the Elements
The elements in the C++ Map can be accessed using the following two methods.
- at() method: It retrieves the values with the key to it, and if the given key does not exist, then it throws an std::out_of_range exception.
- operator[] method: It retrieves the value for the given key, but if the key is not present, it automatically inserts the key with the default value, i.e., “” for strings, 0 for int.
Example:
Output:
Explanation: In the above program, at() retrieves the values for existing key, and operator[] accesses the elements for the keys 101 and 102. If a key is not present, operator[] inserts the key into the Map with a default value, which is then updated, i.e., “Chandu” in the above code.
3. Updating the Elements
The values in a C++ Map can be updated by using the operator[]. It updates the value if the key is present, and inserts the key with a new value if the key is not present.
Example:
Output:
Explanation: In the above program, the Map students consists of 2 values, Ali and Bobby, and after that, the value of Ali is changed to Akshat.
4. Finding the Elements
The find() method is used to check if the key exists and to find the element in the map, and returns an iterator if the element is found; otherwise returns an end() iterator.
Example:
Output:
Explanation: In the above program, the Map students contains two keys, 101 and 102. While searching, key 102 is found, and the output is shown, but key 105 is not found.
5. Traversing the Elements
A Map in C++ stores the values in the form of key-value pairs, and traversal is used to access other keys and values. The keys in the C++ Map can be traversed using a for-loop or an iterator.
- For-loop is a simple and concise way to go through all pairs in the map.
- Using iterators gives you more control over the Map when you want to modify the Map values during traversal or when you want to traverse partially.
Example:
Output:
Explanation: In the above program, the Map students contains the values as above. First, the Map is traversed using the for loop and then by the iterator.
6. Deleting the Elements
You can remove the elements from a Map using the erase() function, which allows you to delete a specific key or a range of elements. When the key is deleted, the associated value is automatically deleted.
Example:
Output:
Explanation: In the above program, the Map students contains three values as above, and then the key 102 is deleted as above.
Get 100% Hike!
Master Most in Demand Skills Now!
Other Common Operations in C++ Map
In this section, we will discuss some more common operations related to the Map in C++.
1. Check if a Map is Empty
In C++, you can check if a map is empty or not by using its empty() member function. This function returns true if the Map contains no elements; otherwise, it returns false.
Syntax:
map_name.empty();
Example:
Output:
Explanation: In the above program, the map students is created, and used with the empty() method, which returns true in the first case, and after the addition of the values, it returns false.
2. Find the Size of a Map
In C++, you can find how many key-value pairs are present in a Map using the size member function. It returns an integer that represents the number of elements currently stored in the map. It has a constant time complexity O(1).
Syntax:
map_name.size();
Example:
Output:
Explanation: In the above program, a map named marks is created, which stores the marks of the students. Then the size() member function is used to find the size of the map marks.
3. Swap Two Maps
To exchange the contents of the two maps, you can use the swap() member function. After using this member function, another Map will contain all the elements of the other Map while preserving the internal order based on their keys. Swapping of the elements is done in constant time O(1).
Syntax:
map1.swap(map2); // Member function
Example:
Output:
Explanation: In the above program, two maps are created, named map1 and map2. The values of the two maps are then swapped with each other, as shown above.
4. Convert a vector of Pairs to a Map
A vector of pairs can be converted into a Map by inserting each pair into the map, where each pair’s first element becomes the key and the second element becomes the value. It is useful when you have key-value data stored in a vector, but you need fast operations and a sorted order that a Map provides.
Syntax:
std::map<KeyType, ValueType> mapName(vectorName.begin(), vectorName.end());
– vectorName is the name of the vector
– vectorName.begin() and vectorName.end() are the iterators that tell the Map from where to start and end reading the elements from the vector.
Example:
Output:
Explanation: In the above program, the vector named vec contains a pair of integers and strings, and according to that, the Map is created by passing the vec.begin() and vec.end(), which inserts the pairs into the Map in sorted order.
5. Sort Map in Custom Order
A Map in C++ is sorted in ascending order by default, but you can also sort it into your custom order by using a comparator function or functor as the second template parameter in the Map definition. It allows you to define how the keys will be defined and stored in the map.
Syntax:
std::map<KeyType, ValueType, Comparator> mapName;
– Comparator is the custom comparator function to define the sorting order.
Example:
Output:
Explanation: In the above program, the Map named mymap is created with the values banana, cherry, and apple. The Map is then ordered in descending order by using the custom comparator DescendingOrder that returns true if the first key is greater than the second key. as shown above.
6. Create a Map for User-Defined Datatype
Creating a map with a user-defined datatype means in C++ means that you have to use your own struct or class as the key or value in std::map. If you are using a custom type as the key, then you have to define a comparison operator or provide a custom comparator to store keys in a sorted order.
Syntax:
std::map<CustomType, ValueType> mapName;
Example:
Output:
Explanation: In the above program, Person is a user-defined datatype that stores the age and grade of a person. A Map is created named studentmap where the key is a Person object as the name of the student and the value is a string.
7. Merge Two Maps
Merging two maps means combining the key-value pairs from both maps into a single map, and the resulting Map contains all unique keys from both maps, maintaining the sorted order of keys.
Syntax:
map1.insert(map2.begin(), map2.end());
– The above syntax will insert all the elements from map2 into map1.
Example:
Output:
Explanation: In the above program, two maps are created, named map1 and map2. The values are then combined in map1 using the insert() function, having the range map2.begin(), map2.end(), and then the values are displayed as above.
Time Complexity of C++ Map Operations
Below is the tabular representation of the Map C++ operations.
Operation |
Time Complexity |
Insertion |
O(log n) |
Access |
O(log n) |
Update |
O(log n) |
Find |
O(log n) |
Traversal |
O(n) |
Deletion |
O(log n) |
Working of C++ Map
Internally, the Map in C++ is implemented as a balanced binary search tree, which keeps the keys in a sorted order with efficient searching, deletion, and insertion operations. When an element in a Map is inserted, it is placed in the tree as a new value, which ensures balanced tree operations and makes searching in logarithmic time. And, when an element is accessed, the Map searches the element by comparing keys to keys stored at different nodes by moving left or right, depending on whether the key is smaller or larger.
For example, we are storing the following key-value pairs in the ordered map.
KEY VALUE
30 Ali
10 Bobby
20 Chandu
40 David
It will be represented as the following binary tree representation as below.
(30, Ali)
/ \
(10, Bobby) (40, David)
\
(20, Chandu)
In the above tree, first you the key 30 is inserted with the value Ali because the tree is empty that node becomes the root node. After that, the key 10 is inserted with the value Bobby, the tree compares the keys (10 < 30) and moves left; the left child is empty, so 10 Bobby is attached as the root’s left child. The process of self-balancing is maintained every time a new node is inserted into it.
Member Functions
Below are some common member functions in the map.
Constructors and Destructor
Constructors are the special functions used to create and initialize a Map object, whereas the destructor is a special function that cleans up memory when a Map or the object is no longer needed. It destroys all the elements inside the Map and releases all allocated space.
Function |
Description |
map() |
Default constructor |
map(const map&) |
Copy constructor |
map(map&&) |
Move constructor |
~map() |
Destructor |
Assignment
Assignment operators in a Map allow you to replace the contents of one Map with another map.
Function |
Description |
operator=(const map&) |
Copy assignment |
operator=(map&&) |
Move assignment |
Iterators
Iterators are the objects that allow you to traverse through all the elements in a Map one by one.
Function |
Description |
begin() |
Returns an iterator to the first element |
end() |
Returns an iterator past the last element |
cbegin() |
Returns a const_iterator to the first element |
cend() |
Returns a const_iterator past the last element |
rbegin() |
Returns reverse_iterator to the last element |
rend() |
Returns a reverse_iterator past the first element |
crbegin() |
Returns a const_reverse_iterator to the last element |
crend() |
Returns a const_reverse_iterator past the first element |
Capacity
Capacity refers to the number of elements present in the map.
Function |
Description |
empty() |
Checks if the Map is empty |
size() |
Returns the number of elements |
max_size() |
Returns the maximum possible number of elements |
Element Access
Element access method allows you to retrieve or modify the value associated with a specific key.
Function |
Description |
operator[](const key_type&) |
Accesses or inserts an element with the given key |
at(const key_type&) |
Accesses element with bounds checking (throws exception if key not found) |
Modifiers
Modifiers are the functions that change the content of the map, and allow you to add, remove, or update the data.
Function |
Description |
insert(const value_type&) |
Inserts element |
insert(InputIterator, InputIterator) |
Inserts elements from a range |
erase(const key_type&) |
Erases element by key |
erase(iterator) |
Erases element at iterator |
erase(iterator, iterator) |
Erases elements in range |
clear() |
Removes all elements |
emplace(Args&&…) |
Constructs element in-place |
emplace_hint(iterator, Args&&…) |
Constructs an element in-place with a hint |
swap(map&) |
Exchanges contents with another map |
Lookup
Lookups are the functions that allow you to search the elements in a Map on the basis of their keys.
Function |
Description |
find(const key_type&) |
Finds element by key |
count(const key_type&) |
Returns the number of elements with key (0 or 1 for map) |
lower_bound(const key_type&) |
Returns an iterator to the first element not less than the key |
upper_bound(const key_type&) |
Returns an iterator to the first element greater than key |
equal_range(const key_type&) |
Returns a pair of iterators for a range of equal keys |
Elements with Equal Keys in C++ Map
In a Map in C++, each key is unique and cannot contain more than one element with the same key. If you try to insert an element with an existing key, the value of that element will be updated. If you need to store multiple values for the same key, you can use a container like std::multimap, which allows duplicate keys and stores all elements with equal keys.
Example:
Output:
Explanation: In the above program, the std::multimap is used to store multiple values with the same key.
Storing a Map in a Map in C++
In C++, a Map can be stored inside another Map to store complex data structures, which means that the value type of a Map can be another std::map. It is useful to represent nested data.
Example:
Output:
Explanation: In the above program, there is one map named company, which contains an inner map storing employee IDs and their names. The values of the outer map are inner maps that map employee IDs (int) to employee names (std::string). The department key in the outer Map points to the inner Map that contains the employee details.
The <map> header in C++ is the header that must be included in order to use the Map from the STL. It contains the definition of Map and their functions, iterators, and member types. To use the Map in C++, the required header is
#include <map>
The <map> header file defines the map containers, and without using the header file <map>, the compiler would not be able to get the knowledge of the std::map or std::multimap classes, their functions, or types, which will lead to compilation errors.
Does Order Matter in C++ Maps?
Yes, the order matters in a Map in C++, even if you insert the items in random order. It always stores the elements in ascending order by default, which means that no matter in what order you insert the key-values in the map, iterating the Map will visit the elements in key order. The ordered storage ensures operations such as deletion, access, and insertion have logarithmic time complexity, i.e., O(log n). Some of the key points are
- Sorting in a map is handled internally; the user doesn’t have to sort the elements manually.
- You can define your own comparator to change the default order, like descending order.
- Every time you traverse through a map, the elements are visited in sorted order, hence, a predictable output.
Why Use std::map?
Some major reasons to use a C++ Map are as follows:
- Automatic Sorting: The elements in the Map are stored in sorted order by default, hence no manual sorting is needed. It is useful when the data changes more often due to it maintains the order of the map.
- Fast Operations: Internally, the Map is implemented by using a balanced binary search tree, due to which the operations performed in the map, like insertion, deletion, and so on, take O(log n) time.
- Unique Keys: Each key in a Map is unique, and if you try to insert an element in an existing key, the old value will be updated with the new value you insert, which also helps in fast lookups.
- Direct Access: In a C++ map, you can directly access the value with the help of the key, and this feature of the Map makes it efficient for large datasets.
When Not to Use a Map in C++?
Some major reasons to not use a C++ Map are as follows:
- Random Access: When you need random access to an element, just like in an array, the Map is not good, because it keyed, ordered container which will not give you the position of the index i, you ask for.
- Memory: Since the maps store the value with multiple pointers for balancing, it takes more memory compared to arrays and vectors.
- Ordered Requirement: If your requirements are not to maintain the data in an ordered way, then the Map is wasteful, because its ordering feature costs extra time and memory.
- Frequent Modification: If your program does operations like insertion and deletion frequently, then do not use the Map its balancing operations can cause performance degradation.
Difference Between std::map and std::unordered_map
Below is the difference between std::map and std::unordered_map.
Feature |
std::map |
std::unordered_map |
Data Structure |
Balanced Binary Search Tree |
Hash Table |
Order |
Stores keys in sorted order |
Stores keys in no particular order |
Time Complexity |
O(log n) for insert, erase, and find |
Average O(1), Worst O(n) for insert, erase, and find |
Memory Usage |
Less memory overhead |
More memory overhead due to hashing |
Iteration |
Iterates in sorted order of keys |
Iteration order is unpredictable |
Conclusion
From the above article, we learned that a C++ Map is used to store values in key-value pairs in ascending order by default. Internally, it uses a balanced binary search tree (Red Black Tree), which makes the operations like insertion, deletion, and search much faster, with a time complexity of O(log n). The C++ Map has many member functions like find(), size, erase(), etc, which help the user to perform different operations easily.
C++ Map – FAQs
Q1. What is a C++ Map used for?
A C++ map is used to store key–value pairs where each key is unique and automatically sorted in ascending order by default. It is useful when you need fast lookups, ordered data, and quick insertion, deletion based on keys.
Q2. Is a C++ Map ordered?
Yes, a C++ Map always stores elements in sorted order of keys, using the comparison function, but if you need an unordered collection, use std::unordered_map.
Q3. What is the time complexity of C++ Map operations?
Most common operations, like insertion, deletion, and search, have O(log n) complexity because it is implemented as a balanced binary search tree.
Q4. Does C++ Map allow duplicate keys?
No, a std::map only stores unique keys, if you need to store multiple values with the same key, use std::multimap.
Q5. What is the difference between C++ Map and unordered_map?
A Map stores keys in sorted order with O(log n) operations, while unordered_map stores keys in no specific order but usually offers O(1) average-time lookups.
Q6.Can I change the key of a Map element directly?
No, the keys in a map are immutable; to change a key, you need to remove the element and insert it again with the new key.