Map in C++ - Naukri Code 360

Introduction

The C++ STL (Standard Template Library) supports several Data Structures that play a crucial role in solving any problem. One such data container is the "Map in C++". A map in C++ is an associative container that stores elements in a mapped fashion. Every element has one key value and one mapped value. Any two elements can not have the same key.

To learn more about C++ STL, visit the C++ guided path.

This article will help you understand the map in c++ and the basic functions associated with it.

What is Map in C++?

A map in C++ is an associative container that stores elements in a mapped fashion. Maps contain sorted key-value pairs, in which every key is unique and cannot be modified. We can insert and delete a key but cannot alter it. The value associated with keys can be modified or updated. We can insert, remove, and search a map within O(n) time complexity.

Internally, the map elements are always sorted by their key values following a specific ordering criterion indicated by its internal comparison object (of type Compare). Keys are always sorted in ascending order.

Syntax

In C++, std::map is a standard library container that stores elements as key-value pairs, with unique keys and sorted order based on the key. Here is the basic syntax for using std::map:

#include <map>

std::map<KeyType, ValueType> mapName;

Creating a Map in C++

We can easily create a map with the following syntax:

map<key_type , value_type> map_name;

The above code will create a map with a key of the "Key_type" data type and the "value_type" datatype value. Remember that the key of a map and corresponding values are always inserted as a pair. We cannot insert only a key or value in the map.

Now, let’s see an example of creating and initializing maps in different ways:

C++

#include <bits/stdc++.h>
using namespace std;


int main ()
{
    // Create a map with keys 1, 2, 3 and corresponding values 4,5,6 
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };
    
    // Creates a map with keys of string  type and values of integer type
    map<string,int> map2;
    
    map2["abc"]=101;    // inserts key = "abc" with value = 101
    map2["b"]=201;      // inserts key = "b" with value = 201
    map2["c"]=301;      // inserts key = "c" with value = 301
    map2["def"]=401;    // inserts key = "def" with value = 401
    
    // Create a map which have entries copied from map2.begin() to map2.end()
    map<char,int> map3 (map2.begin(), map2.end());
    
    // create map which is a copy of map1
    map<char,int> map4 (map1);
}

You can also try this code with Online C++ Compiler

Run Code

In the above example, we have created and initialized different maps using different methods.

Basic std::map Member Functions

For a map, many functions or methods are defined, among which the most used ones are the begin, end, empty and size for capacity, find for searching a key, erase and insert for modification.

We have seen an example of functions associated with the map in C++. Now let's learn about them briefly with the help of the table below:

Function	Description
insert()	We use it to insert a new element in the map.
begin()	It returns the iterator to the first element in the map container.
end()	It returns an iterator to the end of the map.
clear()	It removes all the elements from any map and empties it.
erase()	It removes either a single element or a range of elements from the start(inclusive) to end(exclusive).
size()	It returns the total number of elements in a map container.
empty()	It checks if the map is empty or not.
upper_bound()	It returns the iterator to the first element equivalent or greater than the mapped value.
lower_bound()	It returns the iterator to the first element equivalent or just smaller to the mapped value.

Let's consider an example of declaration, insert, find and iteration in a map.

C++

#include <bits/stdc++.h>
using namespace std;


int main ()
{
    // Creates a map1 with keys 1,2,3 and corresponding values 4,5,6
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };
        
    // Using at() and [ ] method
    m.at(1) = 40;    // Updates the value associated with key 1 to 40
    m[2] = 50;         // Updates the value associated with key 2 to 50


    // Using insert() method
    m.insert(pair<int,int> (4,7));    // Inserts new entry of key = 4 and value = 7
    m.insert(make_pair(5, 8));      // Inserts new entry of key = 5 and value = 8


    // Iterating over the map
    cout<<"The Map is: \n";
    map<int, int>::iterator i;
    for(i = map1.begin(); i != map1.end(); i++){
        cout << i->first << '\t' << i->second<< '\n';
    }
}

You can also try this code with Online C++ Compiler

Run Code

The output for the above code is displayed below:

Output

Iterator in Maps

An object (like a pointer) pointing to an element inside the map container is an iterator to a map. We can use these iterators to move through the elements of the container.

Syntax:

// Initializing an iterator
map<key_type , value_type>::iterator itr;

Example:

Let’s consider an example for iterating over the complete map in c++.

C++

#include <bits/stdc++.h>
using namespace std;
 
int main()
{
     // Creates a map map1 with keys 1,2,3 and corresponding values 4,5,6
    map<int,int> map1{ {1,4} , {2,5} , {3,6} };


    // Iterating over the map
    map<int, int>::iterator i;
    for(i = map1.begin(); i != map1.end(); i++){
        cout << i->first << '\t' << i->second<< '\n';
    }
}

You can also try this code with Online C++ Compiler

Run Code

The output of the above code after iterating through the whole set is displayed below:

Output

Examples of std::map

Example 1: begin() and end() Function

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";

    cout << "Map elements:" << endl;
    for (auto it = myMap.begin(); it != myMap.end(); ++it) {
        cout << "Key: " << it->first << ", Value: " << it->second << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Map elements:
Key: 1, Value: One
Key: 2, Value: Two
Key: 3, Value: Three

Example 2: size() Function

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";

    cout << "Number of elements in the map: " << myMap.size() << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Number of elements in the map: 3

Example 3: Implementing Map

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<string, int> ageMap;
    ageMap["Alice"] = 30;
    ageMap["Bob"] = 25;
    ageMap["Charlie"] = 35;

    cout << "Alice's age: " << ageMap["Alice"] << endl;

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Alice's age: 30

Example 4: Implementing Map of Integers

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, int> squareMap;
    for (int i = 1; i <= 5; ++i) {
        squareMap[i] = i * i;
    }

    cout << "Squares of numbers from 1 to 5:" << endl;
    for (const auto& pair : squareMap) {
        cout << "Number: " << pair.first << ", Square: " << pair.second << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Squares of numbers from 1 to 5:
Number: 1, Square: 1
Number: 2, Square: 4
Number: 3, Square: 9
Number: 4, Square: 16
Number: 5, Square: 25

Example 5: erase() to Remove Individual Elements

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";

    myMap.erase(2); // Removes the element with key 2

    cout << "Map elements after erase:" << endl;
    for (const auto& pair : myMap) {
        cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Map elements after erase:
Key: 1, Value: One
Key: 3, Value: Three

Example 6: erase() to Remove a Range of Elements

C++

#include <iostream>
#include <map>
using namespace std;

int main() {
    map<int, string> myMap;
    myMap[1] = "One";
    myMap[2] = "Two";
    myMap[3] = "Three";
    myMap[4] = "Four";
    myMap[5] = "Five";

    // Erase elements in the range [2, 4) (keys 2 and 3)
    myMap.erase(myMap.find(2), myMap.find(4));

    cout << "Map elements after range erase:" << endl;
    for (const auto& pair : myMap) {
        cout << "Key: " << pair.first << ", Value: " << pair.second << endl;
    }

    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output:

Map elements after range erase:
Key: 1, Value: One
Key: 4, Value: Four
Key: 5, Value: Five

Also check out this article - Pair in C++

List of All Functions of std::map

Function	Description	Example
begin()	Returns an iterator to the first element of the map.	map.begin()
end()	Returns an iterator to one past the last element of the map.	map.end()
rbegin()	Returns a reverse iterator to the last element of the map.	map.rbegin()
rend()	Returns a reverse iterator to one before the first element of the map.	map.rend()
size()	Returns the number of elements in the map.	map.size()
empty()	Checks if the map is empty. Returns true if the map contains no elements, otherwise returns false.	map.empty()
clear()	Removes all elements from the map.	map.clear()
insert()	Inserts a new element or elements into the map.	map.insert({key, value})
erase()	Removes elements from the map by key or iterator.	map.erase(key) or map.erase(iterator)
find()	Searches for an element with the specified key and returns an iterator to it if found, otherwise returns end().	map.find(key)
count()	Returns the number of elements with a specific key. Since keys are unique, it will return 0 or 1.	map.count(key)
lower_bound()	Returns an iterator to the first element that is not less than the specified key.	map.lower_bound(key)
upper_bound()	Returns an iterator to the first element that is greater than the specified key.	map.upper_bound(key)
equal_range()	Returns a pair of iterators representing the range of elements with a specific key.	map.equal_range(key)
at()	Accesses the value associated with a specific key. Throws out_of_range exception if the key is not found.	map.at(key)
operator[]	Accesses the value associated with a specific key. If the key does not exist, inserts a new element with the default value.	map[key]
swap()	Exchanges the contents of the map with another map of the same type.	map1.swap(map2)
value_comp()	Returns a comparison object that can be used to compare keys.	map.value_comp()
key_comp()	Returns a comparison object that can be used to compare keys.	map.key_comp()

Frequently Asked Questions

What are the differences between a map and an unordered_map in C++?

A map is an ordered sequence of unique key values, whereas in an unordered_map key values can be stored in any order, so it is unordered. The average time complexity for a map operation is O(log(n)), while for an unordered_map, it is O(1).

How is a map in C++ internally implemented?

std::map is implementable using binary search trees (balanced).

What are data types supported for the key of a map in C++?

A map can contain a key of any type – user-defined or pre-defined data structure. Still, when we define a key of a user-defined type, we need to specify our custom comparison function according to compare the keys.

What is the worst and average time complexity of a map in c++?

The average time complexity and the worst-case complexity are O(log n) for a map.

Conclusion

In this article, we have extensively discussed the map in c++. We learned how to initialize a map in c++ and the different functions and methods associated with it.

We hope that this blog has helped you enhance your knowledge regarding Map in C++, and if you would like to learn more, check out our articles on STL containers in C++, Data Types in C++, and Implementing Sets Without C++ STL Containers. Do upvote our blog to help other ninjas grow. Happy Coding!