Customized comparison in C++ part 1

This article is a general introduction about all kinds of customized comparison in C++.

vector

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
    vector<int> a = {1, 3, 4, 5, 8, 10, 0};
    sort(a.begin(), a.end(), greater<int>());
    for(auto& c: a)cout << c<< " " << endl;
return 0;
}

map

https://stackoverflow.com/questions/5733254/how-can-i-create-my-own-comparator-for-a-map

std::map takes up to four template type arguments, the third one being a comparator. E.g.:
struct cmpByStringLength {
    bool operator()(const std::string& a, const std::string& b) const {
        return a.length() < b.length();
    }
};

// ...
std::map<std::string, std::string, cmpByStringLength> myMap;
class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end(), [](vector<int>&a, vector<int>&b){
            return a[1]<b[1];
        });
        int res = 0, ending = INT_MIN;
        for(auto&p:pairs)
            if(p[0] > ending)ending=p[1], res++;
        return res;
    }
};

Priority queue

detail see here

https://medium.com/@jim.morris.shen/c-priority-queue-3c458f26e853?source=friends_link&sk=53ba18d32a295791ce9918b7c3995b1a

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string, int> freq;
        for(auto &w : words)freq[w]++;
        
        auto comp = [&](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        };
        typedef priority_queue< pair<string,int>, vector<pair<string,int>>, decltype(comp) > my_priority_queue;
        my_priority_queue  pq(comp);
        
        for(auto &w : freq ){
            pq.emplace(w.first, w.second);
            if(pq.size()>k) pq.pop();
        }
        
        vector<string> output;
        while(!pq.empty())output.push_back(pq.top().first),pq.pop();
        //while(!output.empty()){res.push_back(output.back()); output.pop_back();}
        reverse(output.begin(), output.end());
        return output;
    }
};

set

Using custom std::set comparator

1. Modern C++20 solution

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s;

We use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines.

Online demo

2. Modern C++11 solution

auto cmp = [](int a, int b) { return ... };
std::set<int, decltype(cmp)> s(cmp);

Before C++20 we need to pass lambda as argument to set constructor

Online demo

3. Similar to first solution, but with function instead of lambda

Make comparator as usual boolean function

bool cmp(int a, int b) {
    return ...;
}

Then use it, either this way:

std::set<int, decltype(cmp)*> s(cmp);

Online demo

or this way:

std::set<int, decltype(&cmp)> s(&cmp);

Online demo

4. Old solution using struct with () operator

struct cmp {
    bool operator() (int a, int b) const {
        return ...
    }
};
// ...
// later
std::set<int, cmp> s;

Online demo

5. Alternative solution: create struct from boolean function

Take boolean function

bool cmp(int a, int b) {
    return ...;
}

And make struct from it using std::integral_constant

#include <type_traits>
using Cmp = std::integral_constant<decltype(&cmp), &cmp>;

Finally, use the struct as comparator

std::set<X, Cmp> set;

In part 2, I am adding more examples. Part 2 can be seen from here.

Thanks for reading.