×

Search anything:

Sort Map in C++ STL

Internship at OpenGenus

Get this book -> Problems on Array: For Interviews and Competitive Programming

In this article, we have explained different ways to sort a Map in C++ STL using C++ code snippets.

In order to proceed with this topic first we need to understand that what is a Map?
Map are a part of STL library in C++.They are used to implement ordered associative arrays that store elements in a combination of key values and mapped values in associative containers.

Table of contents:

  1. Introduction to Problem Statement
  2. Solving the problem (With Few Examples and code)

Introduction to Map in C++ STL

Sorting in a map is not always straightforward. It needs a comparison function object. If the comparison object is ignored, default sorting takes place.
There sorting a map of can done by the following ways-

  1. Sorted During Creation
  2. Comparing two Elements by Key
  3. Sorting of Map by value

Sorted During Creation

A map is normally created sorted by keys during creation. If the keys are const char*, then the pointers to the quoted literal strings will be sorted, not the literal texts. To have strings as keys sorted during creation, the strings have to be literals of string objects instantiated from the string class. This means the string library has to be included, as well as the map library.
Code-

#include <iostream>
#include <map>v
#include <string>//u can use bits/stdc++.h as it contains all the files
using namespace std;

int main()
{
    //declaration of map
    map<string, const char*, less<string>> Mp;
    //intialising maps
    Mp = { { "Banana", "yellow" },
      {  "Apple", "red" },
      { "Orange", "orange" } };
    //sorting of map during creation 
    for (map<string, const char*>::iterator it = Mp.begin(); it != Mp.end();             it++)
        cout << it->first << " => " << it->second << endl;

    return 0;
}

OUTPUT-

Apple => red
Banana => yellow
Orange => orange

Comparing two Elements by Key

In this we use key_compare key_comp().This member function returns a copy of the comparison object used by the map container to compare keys. A comparison object is a function object. It would take two keys as arguments and return true if the left key is less than right.

Code-

 #include <iostream>
 #include <map>
 #include <string>//u can use bits/stdc++.h as it contains all the files
 using namespace std;

 int main()
{
    //declaration of map
    map<string, const char*, less<string>> Mp;
    //intialising maps
    Mp = { { "Banana", "yellow" },
      {  "Apple", "red" },
      { "Orange", "orange" } };
    //comparing the values
    bool bl = Mp.key_comp()("Apple", "Orange");

    cout << bl << endl;

    return 0;
}

OUTPUT-

1

This is important to create custom comparison function which is the basis of sorting.

Sorting of Map by value

Below are some various method to achieve this-

1.Using the vector of pairs-

Copy all contents from the map to the corresponding vector of pairs and sort the vector of pairs according to second value using the lambda function.

Code-

   #include <bits/stdc++.h>
   using namespace std;
   bool compare(pair<string, int>& n,pair<string, int>& m)
    {
      return n.second < m.second;
    }
   void sort(map<string, int>& M)
   {

    // Declare vector of pairs
   vector<pair<string, int> > Ans;

    // Copy key-value pair from Map
   // to vector of pairs
      for (auto& i : M) 
      {
       Ans.push_back(i);
      }

   // Sort using function
   sort(Ans.begin(), Ans.end(), compare);

   // Print the sorted value
     for (auto& i : Ans) {

        cout << i.first << ' '
          << i.second << endl;
         }
   }
  int main()
  {
    //declaration of map
    map<string, int> Mp;
    //intialising maps
    Mp = { { "Banana", 1 },
      {  "Apple", 3 },
      { "Orange", 2 } };
     //sorting
     sort(Mp);

    return 0;
  }

Output-

Banana 1
Orange 2
Apple 3

2.Using Multimap-

Multimap is a map with an addition that multiple elements can have the same keys. Rather than each element is unique, the key-value and mapped value pair have to be unique in this case.

Code-

   #include <bits/stdc++.h>
   using namespace std;
   void sort(map<string, int>& M)
   {

    // Declare a multimap
      multimap<int, string> MM;

     // Insert every (key-value) pairs from
     // map M to multimap MM as (value-key)
     // pairs
      for (auto& it : M) {
      MM.insert({ it.second, it.first });
      }

     // Print the multimap
      for (auto& it : MM) {
         cout << it.second << ' '
         << it.first << endl;
      }
   }
 int main()
   {
    //declaration of map
    map<string, int> Mp;
    //intialising maps
    Mp = { { "Banana", 1 },
      {  "Apple", 3 },
      { "Orange", 2 } };
    //sorting
    sort(Mp);

    return 0;
   } 

Output-

  Banana 1
  Orange 2
  Apple 3

With this article at OpenGenus, you must have the complete idea to sort a Map in C++.

Sort Map in C++ STL
Share this