Examples of C++ STL sort comparator alternatives (static & non-static)

1012

A note on using static members for sort comparators:

In cases where static data is passed to the sort comparator, it can lead to ‘Wrong Answer’ submissions, even though the same test cases pass at ‘Run’. As all submission testcases use the same Solution instance, use of global or static methods needs to be handled carefully (see option #3 and option #4). Using static for the problem below is discouraged, but still shown for demonstration purposes.

Example problem

Input: [3,9,3,2,5,2,5,5]
Task: sort array in-place based on element frequency, in increasing order. In case of tie, choose smaller element.
Output: [9,2,2,3,3,5,5,5]

Option #1 (non-static): Lambda function comparator

class Solution {
public:
    vector<int> frequencySort(vector<int>& arr) {
        unordered_map<int, int> frequency;
        for(int elem: arr)
            frequency[elem]++;
            
       auto frequencySort = [&frequency] (const int& elem1, const int& elem2) -> bool
        {
            if(frequency[elem1] == frequency[elem2])
                return elem1 < elem2;
            return frequency[elem1] < frequency[elem2];
        };
    
        sort(arr.begin(), arr.end(), frequencySort);
        return arr;
    }
};

Option #2 (non-static): Structure comparator

struct comparator {
    unordered_map<int, int> _frequency;
    comparator(unordered_map<int, int>& frequency) : _frequency(frequency) {};
    
    bool operator()(const int& elem1, const int& elem2) {
       if(_frequency[elem1] == _frequency[elem2])
            return elem1 < elem2;
        return _frequency[elem1] < _frequency[elem2];
    }
};

class Solution {
public:
    vector<int> frequencySort(vector<int>& arr) {
        unordered_map<int, int> frequency;
        for(int elem: arr)
            frequency[elem]++;
    
        sort(arr.begin(), arr.end(), comparator(frequency));
        return arr;
    }
};

Option #3 (static): Static function comparator with static data

class Solution {
    static inline unordered_map<int, int> frequency;
public:
    Solution() { frequency.clear(); } // reset hash map between testcase runs during Submission
    
    static bool comparator(const int& elem1, const int& elem2) {
        if(frequency[elem1] == frequency[elem2])
            return elem1 < elem2;
        return frequency[elem1] < frequency[elem2];
    }
    
    vector<int> frequencySort(vector<int>& arr) {
        for(int elem: arr)
            frequency[elem]++;
    
        sort(arr.begin(), arr.end(), comparator);
        return arr;
    }
};

Option #4 (static): Static function comparator with non-static data

class Solution {
public:
    static bool comparator(const int& elem1, const int& elem2, unordered_map<int, int>& frequency) {
        if(frequency[elem1] == frequency[elem2])
            return elem1 < elem2;
        return frequency[elem1] < frequency[elem2];
    }
    
    vector<int> frequencySort(vector<int>& arr) {
        unordered_map<int, int> frequency;
        for(int elem: arr)
            frequency[elem]++;
    
        sort(arr.begin(), arr.end(), bind(comparator, placeholders::_1, placeholders::_2, frequency));
        return arr;
    }
};

For practice, sort comparators can be used on a similar problem in https://leetcode.com/problems/sort-array-by-increasing-frequency/

Comments (0)