C++ : Map Tutorial -Part 2: Map and External Sorting Criteria / Comparator

In this article we will discuss how to use external sorting criteria for keys in std::map and points that we need to take care with external sorting criteria.

Default sorting criteria for keys in std::map is operator “<” i.e. std::less<T>. So, while creating std::map if we don’t specify the external sorting criteria then default criteria will be used.
For example,

    std::map<std::string, int > mapOfWords;

    mapOfWords.insert(std::make_pair("earth", 1));
    mapOfWords.insert(std::make_pair("moon", 2));
    mapOfWords.insert(std::make_pair("sun", 3));

    std::map<std::string, int>::iterator it = mapOfWords.begin();
    for( ; it != mapOfWords.end(); it++)
        std::cout<<it->first<<" :: "<<it->second<<std::endl;

will output the elements in lexicographical order.

Output:

earth :: 1
moon :: 2
sun :: 3

But suppose we want that elements in map to be stored in reverse lexicographical order of keys, then how to do it?
Obviously we cannot change the definition of opeartor < for std::string. Then in such scenario we should use external sorting criteria i.e. a function object opposite that behaves opposite to default operator <.

External sorting criteria i.e. Comparator,

struct WordGreaterComparator
{
    bool operator()(const std::string & left, const std::string & right) const
    {
        return (left > right);
    }
};

std::map with external sorting criteria i.e. Comparator

std::map<std::string, int, WordGreaterComparator > mapOfWords_2;
mapOfWords_2.insert(std::make_pair("earth", 1));
mapOfWords_2.insert(std::make_pair("moon", 2));
mapOfWords_2.insert(std::make_pair("sun", 3));
for(std::map<std::string, int>::iterator it = mapOfWords_2.begin(); it != mapOfWords_2.end(); it++)
   std::cout<<it->first<<" :: "<<it->second<<std::endl;

Output:

sun :: 3
moon :: 2
earth :: 1

Comparing std::map objects with different external key sorting criteria

We can compare two std::map objects using operator ==, < , > etc but with same type of key sorting criteria only.

[showads ad=inside_post]

 

For example,

In  below two std::map objects, sorting criteria for keys is of different types and hence comparison of these std::map objects will result in compile time error.

std::map<std::string, int > mapOfWords;
std::map<std::string, int, WordGreaterComparator > mapOfWords_2;
// Compile Error as 2 std::map objects have different sorting criteria
if(mapOfWords == mapOfWords_2)
    std::cout<<"Maps are same"<<std::endl;

For Comparison of two std::map objects only type of sorting criteria of keys should be same, it doesn’t matter of they are using the same object of that or not.

For example,

If Our Sorting Criteria is,

struct WordComparator;

Then there will be no compile error for below code because here type of sorting criteria is same i.e.WordComparator for both the std::map objects even if both are using different objects of WordComparator .

std::map<std::string, int, WordGreaterComparator > mapOfWords_1(WordGreaterComparator(1));
std::map<std::string, int, WordGreaterComparator > mapOfWords_2(WordGreaterComparator(2));//No Compile time error as type of comparator is same
if(mapOfWords_1 == mapOfWords_2)
   std::cout<<"Maps are same"<<std::endl;

Complete executable code is as follows,

#include <iostream>
#include <map>
#include <string>
#include <iterator>

struct WordGreaterComparator
{
    bool operator()(const std::string & left, const std::string & right) const
    {
        return (left > right);
    }
};

int main()
{

    std::cout<<"Default sorting criteria for keys i.e. operator < for std::string"<<std::endl;
    // Default sorting criteria for keys i.e. operator < for std::string
    std::map<std::string, int > mapOfWords;

    mapOfWords.insert(std::make_pair("earth", 1));
    mapOfWords.insert(std::make_pair("moon", 2));
    mapOfWords.insert(std::make_pair("sun", 3));

    std::map<std::string, int>::iterator it = mapOfWords.begin();
    for( ; it != mapOfWords.end(); it++)
        std::cout<<it->first<<" :: "<<it->second<<std::endl;

    std::cout<<"External sorting criteria for keys "<<std::endl;
    std::map<std::string, int, WordGreaterComparator > mapOfWords_2;

    mapOfWords_2.insert(std::make_pair("earth", 1));
    mapOfWords_2.insert(std::make_pair("moon", 2));
    mapOfWords_2.insert(std::make_pair("sun", 3));
    for(std::map<std::string, int>::iterator it = mapOfWords_2.begin(); it != mapOfWords_2.end(); it++)
        std::cout<<it->first<<" :: "<<it->second<<std::endl;

    // Compile Error as 2 std::map objects have different sorting criteria0
    //if(mapOfWords == mapOfWords_2)
    //    std::cout<<"Maps are same"<<std::endl;

    return 0;
}

 

Scroll to Top