MAP Container in STL

Maps are used to replicate associative arrays. Maps contain sorted key-value pair, in which 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.

For example: A map of students where roll number is the key and name is the value can be represented graphically as :

Notice that keys are arranged in ascending order, its because maps always arrange its keys in sorted order. In case the keys are of string type, they are sorted lexicographically.

Creating a Map in C++ STL

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.

Here is a program that will illustrate creating a map in different ways:

#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 function of Map container in STL:

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.

#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  */  
}

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.

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.

#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   
}

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.

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 and find() returns the iterator to the entry having key equal to given key (passed as parameter).