How to create custom comparator for map in C++

The std::map sorts the elements based on the key value and this sorting is usually done in descending order for most fundamental datatypes. The key values are compared using the standard template library’s std::less<> functor template. However, C++ provides specific ways to override and change the function used for comparison, and thus, the sorting can be customized.

Using template argument

A functor is a class with an overloaded() operator so its objects can behave like a function. The std::map accepts a third template argument which is the comparator argument that can be used to customize the sorting of elements.

By default, strings are sorted lexicographically. The following program demonstrates the use of a custom comparator to sort string elements based on their length.

#include <iostream>
#include <string>
#include <string_view>
#include <map>
class comp  //custom comparator
{
public:
  bool operator()(std::string_view a, std::string_view b) const
  {
    return a.length() > b.length();
  }
};



int main()
{
  std::map<std::string, int, comp> m;  // map with custom comparator 
  m["abc"] = 3; m["a"]=1; m["ab"]=2;
  m["abcd"] = 4; m["abcde"] = 5;
  for (auto& [key, val] : m)
  {
    std::cout << key;
    std::cout<< " " << val << "\n";
  }
}
Output:
abcde 5
abcd 4
abc 3
ab 2
a 1

Using constructor argument

One of the constructors of the map accepts a comparator argument whose type can be a function pointer, functor, or lambda expression. But, this method is used for lambda expressions and function pointers. It is usually preferable to pass functors as template arguments.

The third argument must still be specified in this method and it can be of type function pointer(for functions ) or std::function<>(for both functions and lambda expression) from the functional header. But it is usually preferred to use std::function<> type.

The following code demonstrates the same example from the previous section, but by the use of function as a constructor argument.

#include <iostream>
#include <map>
#include <string>
#include<string_view>
#include <functional>
bool comp(std::string_view a, std::string_view b) //custom comparator
{
  return a.length() > b.length();
}

int main()
{
  std::function<bool(std::string_view, std::string_view)> a = comp;
  std::map<std::string, int, std::function<bool(std::string_view,std::string_view)>> m(a);  // map with custom comparator 
  m["abc"] = 3; m["a"]=1; m["ab"]=2;
  m["abcd"] = 4; m["abcde"] = 5;
  for (auto& [key, val] : m)
  {
    std::cout  << key;
    std::cout<< " " << val << "\n";
  }
}

The output of this example is exactly the same as above where elements are ordered in based on length in descending order.

 

Leave a Reply

Your email address will not be published. Required fields are marked *