All about map STL in c++ for competitive programming( initialization, traversal and methods/functions ) :

map STL

Important Points:

1. It is an associative container that stores elements in (key, value) combination.
   
2. In this container each key should be unique, otherwise the value associated with it overrides the previous value.
   
3. It stores (key, value) pairs in sorted order on the basis of key.
4. Keyword 'first' is used to refer to the 'key' and keyword 'second' is used to refer to the 'value' associated with the key.
   
5. Remember to use the header file #include<map> before using map STL.
   

Advantages of using map STL:

• It allows fast access to the values using keys. 
• Since key is unique it doesn't allow duplication of data. 
• Keys are in sorted order which sometimes comes handy during competitive coding.

 

Associative containers vs Sequence containers:

• Unlike sequence containers elements in associative container are referenced by their key and not by their absolute position in the container.
• Elements of an associative container follows strict weak ordering.
• Example for associative containers - set, map, multiset, multimap etc.
• Example for sequence containers - vector, array, deque etc.
  

 

 

Different ways to initialize a map STL

 

1. declaring a map and using insert( ) to put elements into it :  

    map < int, string > m ;
    m.insert( { 1, "Suraj" } ) ;
    m.insert( { 3, "Nidhi" } ) ;     

    m.insert( { 2, "Kapil" } ) ;

 

 

2. declaring a map and using insert( ) and make_pair( ) methods to put elements into it :  

    map < int, string > m ;
    m.insert( make_pair( 1, "Suraj" ) ) ;
    m.insert( make_pair( 3, "Nidhi" ) ) ;
    m.insert( make_pair( 2, "Kapil" ) ) ;

 

 

3. using insert( ) and pair STL to put elements into it :  

    map < char, int > m ;
    m.insert( pair < char, int > ( 's', 1 ) ) ;
    m.insert( pair < char, int > ( 'n', 3 ) ) ;
    m.insert( pair < char, int > ( 'k', 2 ) ) ;

 

 

4. Initializing like arrays:

    map < int, int > m{ {1, 10}, {3, 20}, {2, 30} } ;

 

5. Using [ ] operator:

 

    map < int, int > m;

    m[1] = 10 ;

    m[3] = 20 ;

    m[2] = 30 ;

 

6. Initializing from another map:

    map < int, int > m1{ {1, 10}, {3, 20}, {2, 30} } ;

   

    map < int, int > m ( m1.begin( ), m1.end( ) ) ;  

 

 

7. What if we want the sorting order of the keys in the map to be in descending order instead of the ascending which is the default behaviour, then initialize it like this :

 

    map < int, int, greater <  > > m ;

 

 

 

**don't worry about the methods / functions used above, i am going to explain each and every function associated with map STL below.

 

 

 

All map STL methods/ functions  

 

1. map STL important iterator functions:

Iterator definition: An iterator is something which helps in moving within the container. It points to a specific element and it moves according to our commands from one element to another.

 

1. begin( ) : returns an iterator pointing to the first (key, value) pair of the map.

 

2. end( ) :  returns an iterator pointing to the theoretical element after the last (key, value) pair of the map.

Other functions:

•  rbegin( )
•  cbegin( )
•  crbegin( )
•  rend( )
•  cend( )
•  crend( )
  

 

 

2. map STL  important capacity related functions:

1. size( ) : returns the number of (key, value) pairs in the map.

2. empty( ) : returns true if the container is empty otherwise, false.

 

3. [ ] : returns the value associated with the key (specified in the square brackets) , otherwise 0.

 

4. at( ) : returns the value associated with the key (specified in the parenthesis) , otherwise an exception called out_of_range.

 

Other functions:

•  max_size( )

 

 

3. map STL important modifying functions or modifiers:

1. insert( ) or emplace( ) :  used to insert a new (key, value) pair into the map.

2. clear( ) : used to remove all (key, value) pairs from the map container.

 

3. swap( ) : used to exchange the content of two maps of  same type (size may differ).

 

4. erase( ) : used to remove a single (key, value) pair or a range of (key, value) pairs from the map. 

 

Other functions:

•  emplace_hint( )

 

emplace( ) vs insert( ) which to use?

• emplace() avoids unnecessary copy of objects.
• for primitive data types it does not matter which one to use but for objects or bigger objects use emplace() for efficiency.
• unlike insert(), no copy or move operation are performed in emplace().

 

4. map STL other important functions (may come handy during competitions) :

1. find( ) : It searches for the key specified in the parenthesis and returns an iterator pointing towards that (key, value) pair if found. Otherwise, it returns an iterator pointing to map_name.end( ) .

 

2. count( ) :  Since set is having all unique keys, it returns 1 if the key specified in its parenthesis is present in the map. Otherwise, it returns 0.

3. lower_bound( ) :  It returns an iterator pointing to the (key, value) pair having key greater than or equal to the key specified in the parenthesis. Otherwise, it returns an iterator pointing to map_name.end( ) .

 

4. upper_bound( ) :  It returns an iterator pointing to the (key, value) pair having key greater than the value specified in the parenthesis. Otherwise, it returns an iterator pointing to map_name.end( ) .

 

 

Other functions:

• equal_range( ) 
• key_comp( )
• value_comp( )
  

 

 

 

 

List of all map STL important functions with example 

 

1. Initializing map : map< int, int > m ;

 

 2. Putting elements into it : 

     m.insert( { 1, 10 } ) ;
     m.insert( { 3, 30 } ) ;     

     m.insert( { 2, 20 } ) ;

     m.insert( { 4, 8 } ) ;

 

     Therefore, 

     m = { {1, 10}, {2, 20}, {3, 30}, {4, 8} }

 

3. cout << m.size( ) ;               //4

 

4. Checking whether map is empty or not :

    if( m.empty( ) = = false )

    cout << "not empty" ;     //it will be printed

    else

    cout << "empty" ;

 

5. cout << m[2] ;               //20

 

6. cout << m.at(2) ;           //20

  

7. m.erase( 3 ) ;     // pair {3, 30} will be removed

    Therefore, 

    m = { {1, 10}, {2, 20}, {4, 8} }

 

8. using erase( ) to remove a range of (key, value) pairs :

    //setting up an iterator named it     

    map < int, int > : : iterator it ;

    it = m.find( 2 ) ;

    //iterator pointing towards pair {2, 20} in map

    m.erase( it, m.end( ) ) ;

 

    Therefore,    

    m = { {1, 10} }

 

    m.insert( { 3, 30 } ) ;     

    m.insert( { 2, 20 } ) ;

    m.insert( { 5, 8 } ) ;

 

     Therefore, now :

     m = { {1, 10}, {2, 20}, {3, 30}, {5, 8} }

   

9. it = m.lower_bound( 5 ) ;     

    //iterator pointing towards (key, value) pair 

{5, 8} in map

 

10. it = m.upper_bound( 4 ) ;     

    //iterator pointing towards (key, value) pair 

{5, 8} in map

 

11. m.clear( )      // all  (key, value) pairs are removed from the map

map STL traversal methods 

 

Let our map be m :

map < int, int > m ;

 

1. for ( auto &i : m)

    {

          cout << i.first << " " << i.second << endl; 

    }

       

2. for ( auto i = m.begin( ) ; i ! = m.end( ) ; i++)

    {

         cout << i->first << " " << i->second << endl;

    }

 

  

3. declaring an iterator it :

    map < int, int > : : it ;

    for ( it = m.begin( ) ; it!=m.end( ) ; it++)

    {

         cout << i->first << " " << i->second << endl;

    }

 

 

 

 

 

 

 

 

Hi reader! got any queries or need more explanation for something? Feel free to comment below.