Map in C++ STL


Reading time: 35 minutes

Map is a dictionary like data structure. It is a sequence of (key, value) pair, where only single value is associated with each unique key. It is often referred as associative array.

In map, key values are generally used to sort the elements.In Maps each key is unique and cannot be changed, and it can be inserted or deleted but cannot be altered. Value associated with keys can be altered. We can search, remove and insert in a map within O(n) time complexity.

Maps are typically implemented as Binary Search Tree.

Zero sized maps are also valid. In that case map.begin() and map.end() points to same location.

Maps are part of the C++ STL (Standard Template Library).

For example:

A map of Employees where employee ID is the key and name is the value can be represented as:

Keys Values
101 Robin
102 Reem
103 Nisha
104 Neeta

Creating a Map in C++ STL

Syntax :

     template < class Key,                           // map::key_type  
           class T,                                 // map::mapped_type  
           class Compare = less<Key>,              // map::key_compare  
           class Alloc = allocator<pair<const Key,T> >    // map::allocator_type  
           > class map;  

Parameter

  1. key : The key data type to be stored in the map.
  2. type : The data type of value to be stored in the map.
  3. compare : A comparison class that takes two arguments of the same type bool and returns a value. This argument is optional and the binary predicate less<"key"> is the default value.
  4. alloc : Type of the allocator object. This argument is optional and the default value is allocator .

Maps can easily be created using the following statement :

map<key_type , value_type> map_name;

This will create a map with key of type Key_type and value of type value_type. One thing which is to remembered is that key of a map and corresponding values are always inserted as a pair, you cannot insert only key or just a value in a map.

Example 1 :

#include <string.h>  
#include <iostream>  
#include <map> 
#include <utility> 
using namespace std; 
int main()  
{  
   map<int, string> Employees;  
   // 1) Assignment using array index notation  
   Employees[101] = "Nikita";  
   Employees[105] = "John";  
   Employees[103] = "Dolly";  
   Employees[104] = "Deep";  
   Employees[102] = "Aman";  
   cout << "Employees[104]=" << Employees[104] << endl << endl;    cout << "Map size: " << Employees.size()<<  endl;  
   cout << endl << "Natural Order:" << endl;  
   for( map<int,string>::iterator ii=Employees.begin(); ii!=Employees.end();++ii)  
   {  
       cout <<  (*ii).first <<  ": "<<  (*ii).second<<  endl;  
   }  
   cout <<  endl << "Reverse Order:" << endl;  
   for( map<int,string>::reverse_iterator ii=Employees.rbegin(); ii!=Employees.rend(); ++ii)  
   {  
       cout << (*ii).first << ": " << (*ii).second << endl;  
   }  
}  

Output :

        Employees[104]=Deep

        Map size: 5

        Natural Order:
        101: Nikita
        102: Aman
        103: Dolly
        104: Deep
        105: John

        Reverse Order:
        105: John
        104: Deep
        103: Dolly
        102: Aman
        101: Nikita

Example 2 :

#include <iostream> 
#include <map> 
using namespace std;
int main ()
{
    map<int,int> m{ {1,2} , {2,3} , {3,4} };
    /* creates a map m with keys 1,2,3 and 
        their corresponding values 2,3,4 */  
    
    map<string,int> map1; 
    /*  creates a map with keys of type character and 
      values of type integer */
    
    map1["abc"]=100;    // inserts key = "abc" with value = 100
    map1["b"]=200;      // inserts key = "b" with value = 200
    map1["c"]=300;      // inserts key = "c" with value = 300
    map1["def"]=400;    // inserts key = "def" with value = 400
    
    map<char,int> map2 (map1.begin(), map1.end());
    /* creates a map map2 which have entries copied 
        from map1.begin() to map1.end() */ 
    
    map<char,int> map3 (m);
    /* creates map map3 which is a copy of map m */
} 

Member Functions of Map in C++ STL:

Following are some of the commonly used basic functions of Map container in STL:

1. at and [ ] :

Both at and [ ] are used for accessing the elements in the map. The only difference between them is that at throws an exception if the accessed key is not present in the map, on the other hand operator [ ] inserts the key in the map if the key is not present already in the map.

Example :

#include <iostream>  
#include <map> 
using namespace std;
int main ()
{
    map <int,string> m{ {1,”nikhilesh”} , {2,”shrikant”} , {3,”ashish”} };
    cout << m.at(1) ;  // prints value associated with key 1 ,i.e nikhilesh
    cout << m.at(2) ;  // prints value associated with key 2 ,i.e shrikant
    
    /* note that the parameters in the above at() are the keys not the index */
    cout << m[3] ; // prints value associated with key 3 , i.e ashish
    m.at(1) = "vikas";   // changes the value associated with key 1 to vikas
    m[2] = "navneet";   // changes the value associated with key 2 to navneet
    m[4] = "doodrah";   
    /* since there is no key with value 4 in the map, 
        it insert a key-value pair in map with key=4 and value = doodrah */
    m.at(5) = "umeshwa"; 
    /* since there is no key with value 5 in the map , 
     it throws an exception  */  
}

2. empty, size and max_size :

empty() returns boolean true if the map is empty, else it returns Boolean false. size() returns number of entries in the map, an entry consist of a key and a value.
max_size() returns the upper bound of the entries that a map can contain (maximum possible entries) based on the memory allocated to the map.

Example :

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

        int main() 
        { 
            map<char, int> mymap; 
            mymap['a'] = 1; 
            mymap['b'] = 2; 
            if (mymap.empty()) { 
                cout << "True"; 
            } 
            else { 
                cout << "False"; 
            } 
            return 0; 
        } 

Output :

        False

3. insert and insert_or_assign :

insert() is used to insert entries in the map. Since keys are unique in a map, it first checks that whether the given key is already present in the map or not, if it is present the entry is not inserted in the map and the iterator to the existing key is returned otherwise new entry is inserted in the map.

There are two variations of insert():

  • insert(pair) : In this variation, a pair of key and value is inserted in the map. The inserted pair is always inserted at the appropriate position as keys are arranged in sorted order.
  • insert(start_itr , end_itr): This variation inserts the entries in range defined by start_itr and end_itr of another map.

The insert_or_assing() works exactly as insert() except that if the given key is already present in the map then its value is modified.

Example :

        #include <iostream>
        #include <map>
        using namespace std;
        int main ()
        {
            map<int,int> m{{1,2} , {2,3} , {3,4} };

            m.insert( pair<int,int> (4,5));
            /* inserts a new entry of key = 4 and value = 5 in map m */

            /* make_pair() can also be used for creating a pair */
            m.insert( make_pair(5, 6));
            /* inserts a new entry of key = 5 and value = 6 */


            map::iterator i , j;
            i = m.find(2);    // points to entry having key =2
            j = m.find(5);    // points to entry having key =5

            map<int,int> new_m;

            new_m.insert(i,j);
             /* insert all the entries which are pointed 
             by iterator i to iterator j*/ 

            m.insert( make_pair(3,6));  
             // do not insert the pair as map m already contain key = 3 */ 

            m.insert_or_assign( make_pair(3,6));  // assign value = 6 to key =3   
        }

4. erase and clear :

erase() removes the entry from the map pointed by the iterator (which is passed as parameter), however if we want to remove all the elements from the map, we can use clear(), it clears the map and sets its size to 0.

There are two variations of erase :

  • erase(iterator_itr) : This removes entry from the map pointed by iterator iterator_itr, reducing the size of map by 1.
  • erase(start_iterator, end_iterator) : It removes the elements in range specified by the start_iterator and end_iterator.

Example of Clear() :

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

        int main() 
        { 
            // Take any two maps 
            map<int, string> map1, map2; 

            // Inserting values 
            map1[1] = "India"; 
            map1[2] = "Nepal"; 
            map1[3] = "Sri Lanka"; 
            map1[4] = "Myanmar"; 

            // Print the size of map 
            cout<< "Map size before running function: \n"; 
            cout << "map1 size = " << map1.size() << endl; 
            cout << "map2 size = " << map2.size() << endl;; 

            // Deleting the map elements 
            map1.clear(); 
            map2.clear(); 

            // Print the size of map 
            cout<< "Map size after running function: \n"; 
            cout << "map1 size = " << map1.size() << endl; 
            cout << "map2 size = " << map2.size(); 
            return 0; 
        }

Example of erase() :

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

        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 2, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 3, 60 }); 
            mp.insert({ 5, 50 }); 

            // prints the elements 
            cout << "The map before using erase() is : \n"; 
            cout << "KEY\tELEMENT\n"; 
            for (auto itr = mp.begin(); itr != mp.end(); ++itr) { 
                cout << itr->first 
                     << '\t' << itr->second << '\n'; 
            } 

            // function to erase given keys 
            mp.erase(1); 
            mp.erase(2); 

            // prints the elements 
            cout << "\nThe map after applying erase() is : \n"; 
            cout << "KEY\tELEMENT\n"; 
            for (auto itr = mp.begin(); itr != mp.end(); ++itr) { 
                cout << itr->first 
                     << '\t' << itr->second << '\n'; 
            } 
            return 0; 
        } 

output :

        The map before using erase() is : 
        KEY    ELEMENT
        1    40
        2    30
        3    60
        5    50

        The map after applying erase() is : 
        KEY    ELEMENT
        3    60
        5    50

5. begin, end and find :

begin, end and find returns an iterator.
begin() returns the iterator to the starting entry of the map
end() returns the iterator next to the last entry in the map
find() returns the iterator to the entry having key equal to given key (passed as parameter).

Example of begin() and end() :

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

        int main() 
        { 
            // declaration of map container 
            map<char, int> mymap; 
            mymap['a'] = 1; 
            mymap['b'] = 2; 
            mymap['c'] = 3; 

            // using begin() to print map 
            for (auto it = mymap.begin(); 
                 it != mymap.end(); ++it) 
                cout << it->first << " = "
                     << it->second << '\n'; 
            return 0; 
        } 

Example of find() :

        #include <bits/stdc++.h> 
        using namespace std; 
        int main() 
        { 

            // initialize container 
            multimap<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 2, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 3, 20 }); 
            mp.insert({ 4, 50 }); 

            cout << "The elements from position 3 in map are : \n"; 
            cout << "KEY\tELEMENT\n"; 

            // find() function finds the position at which 3 is 
            for (auto itr = mp.find(3); itr != mp.end(); itr++) 
                cout << itr->first 
                     << '\t' << itr->second << '\n'; 

            return 0; 
        } 

output :

        The elements from position 3 in map are : 
        KEY    ELEMENT
        3    20
        4    50

6. count() :

count() is a built-in function in C++ STL which returns 1 if the element with key K is present in the map container. It returns 0 if the element with key K is not present in the container.

Example :

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

        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 2, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 3, 60 }); 
            mp.insert({ 4, 20 }); 
            mp.insert({ 5, 50 }); 

            // checks if key 1 is present or not 
            if (mp.count(1)) 
                cout << "The key 1 is present\n"; 
            else
                cout << "The key 1 is not present\n"; 

            // checks if key 100 is present or not 
            if (mp.count(100)) 
                cout << "The key 100 is present\n"; 
            else
                cout << "The key 100 is not present\n"; 

            return 0; 
        } 

7. equal_range() :

equal_range() is a built-in function in C++ STL which returns an iterator of pairs. The pair refers to the bounds of a range that includes all the elements in the container which have a key equivalent to k. Since the map container only contains unique key, hence the first iterator in the pair returned thus points to the element and the second iterator in the pair points to the next key which comes after key K. If there are no matches with key K, the range returned is of length 1 with both iterators pointing to the an element which has a key denoting the size of map and elements as 0.

Example :

        #include <bits/stdc++.h> 
        using namespace std; 
        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 4, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 6, 60 }); 

            pair<map<int, int>::iterator, map<int, int>::iterator> it; 

            // iterator of pairs 
            it = mp.equal_range(1); 
            cout << "The lower bound is " <<  
            it.first->first << ":" << it.first->second; 

            cout << "\nThe upper bound is " <<  
            it.second->first << ":" << it.second->second; 

            return 0; 
        } 

Output :

        The lower bound is 1:40
        The upper bound is 4:30

8. rend() :

The rend() function is an inbuilt function in C++ STL which returns a reverse iterator pointing to the theoretical element right before the first key-value pair in the map(which is considered its reverse end).

Example of rend() :

        #include <iostream> 
        #include <map> 
        using namespace std; 
        int main() 
        { 
            map<char, int> mymap; 

            // Insert pairs in the multimap 
            mymap.insert(make_pair('a', 1)); 
            mymap.insert(make_pair('b', 3)); 
            mymap.insert(make_pair('c', 5)); 

            // Get the iterator pointing to 
            // the preceding position of 
            // 1st element of the map 
            auto it = mymap.rend(); 

            // Get the iterator pointing to 
            // the 1st element of the multimap 
            it--; 

            cout << it->first 
                 << " = "
                 << it->second; 

            return 0; 
        } 

Output :

        a = 1

9. crbegin() and crend() :

crbegin() is a built-in function in C++ STL which returns a constant reverse iterator referring to the last element in the map container. Since map container contains the element in an ordered way, crbegin() will point to that element that will come last according to the container’s sorting criterion.
crend() is a built-in function in C++ STL which returns a constant reverse iterator pointing to the theoretical element before the first element in the map. Since map container contains the element in an ordered way, crend() will point to the element theoretically before the first element according to the container’s sorting criterion.

example of crbegin() :

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

        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 2, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 3, 60 }); 
            mp.insert({ 4, 20 }); 
            mp.insert({ 5, 50 }); 

            auto ite = mp.crbegin(); 
            cout << "The last element is {" << ite->first 
                 << ", " << ite->second << "}\n"; 

            // prints the elements 
            cout << "\nThe map in reverse order is: \n"; 
            cout << "KEY\tELEMENT\n"; 
            for (auto itr = mp.crbegin(); itr != mp.crend(); ++itr) { 
                cout << itr->first 
                     << '\t' << itr->second << '\n'; 
            } 
            return 0; 
        } 

Output:

        The last element is {5, 50}
        The map in reverse order is: 
        KEY    ELEMENT
        5    50
        4    20
        3    60
        2    30
        1    40

example of crend() :

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

        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.insert({ 2, 30 }); 
            mp.insert({ 1, 40 }); 
            mp.insert({ 3, 60 }); 
            mp.insert({ 4, 20 }); 
            mp.insert({ 5, 50 }); 

            // prints the elements 
            cout << "\nThe map in reverse order is : \n"; 
            cout << "KEY\tELEMENT\n"; 
            for (auto itr = mp.crbegin(); itr != mp.crend(); ++itr) { 
                cout << itr->first 
                     << '\t' << itr->second << '\n'; 
            } 
            return 0; 
        } 

Output:

        The map in reverse order is : 
        KEY    ELEMENT
        5    50
        4    20
        3    60
        2    30
        1    40     

10. emplace() :

emplace() is a built-in function in C++ STL which inserts the key and its element in the map container. It effectively increases the container size by one. If the same key is emplaced more than once, the map stores the first element only as the map is a container which does not store multiple keys of the same value.

Example of emplace() :

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

        int main() 
        { 

            // initialize container 
            map<int, int> mp; 

            // insert elements in random order 
            mp.emplace(2, 30); 
            mp.emplace(1, 40); 
            mp.emplace(2, 20); 
            mp.emplace(1, 50); 
            mp.emplace(4, 50); 

            // prints the elements 
            cout << "\nThe map is : \n"; 
            cout << "KEY\tELEMENT\n"; 
            for (auto itr = mp.begin(); itr != mp.end(); itr++) 
                cout << itr->first << "\t" << itr->second << endl; 

            return 0; 
        } 

Output:

        The map is : 
        KEY    ELEMENT
        1    40
        2    30
        4    50