In this article we will be discussing how to implement custom comparator functions in C++ Sort STL and custom priority functions in C++ priority queues. To facilitate easier understanding, I have picked up a problem from LeetCode which could be solved uses both the approaches mentioned above.

Let us go through the problem statement.

Given a sentence text (A sentence is a string of space-separated words) in the following format:

First letter is in upper case. Each word in text are separated by a single space. Our task is to rearrange the words in text such that all words are arranged in an increasing order of their lengths. If two words have the same length, arrange them in their original order.

Example 1:

Input: text = "Leetcode is cool"

Output: "Is cool leetcode"

Explanation: There are 3 words, "Leetcode" of length 8, "is" of length 2 and "cool" of length 4.

Note: Output is ordered by length and the new first word starts with capital letter.

Link to the Problem: LeetCode-1451

If we carefully observe the question, we need to maintain the original order of the elements if they are of the same length. To accomplish this goal, we are going to make use of stable sort, an inbuilt sort function present in C++ STL.

However we wish to sort the words based on the custom conditions given in the question, hence we will be providing our implementation of the custom compare function to the sort STL function.

If you are unaware of the term stable sort, refer this article for more information.

1. Sorting strings via custom comparator

class Solution {
public:
    string arrangeWords(string text) {
        vector<string> words;
        stringstream ss(text);
        string word;

        while(ss >> word) 
            words.push_back(word);

        stable_sort(words.begin(), words.end(), [&](const string s1, const string s2)->bool {
            return s1.size() < s2.size();
        });

        string result;
        for(string &s : words) {
            s[0] = tolower(s[0]);
            result += s + " ";
        }
        // remove the last space
        result.pop_back();
        // capitalize the first letter
        result[0] = toupper(result[0]);
        return result;
    }
};

A stringstream is used to extract the words as if we are using cin. Since cin uses space as a delimeter, hence we are able to extract words separated by space using stringstream.

If you wish to know more about stringstream, have a read at this article

Note: There are two ways to write a function. A normal approach would be to define a function.

     static bool compare(const string &s1, const string &s2) {
         return s1.size() < s2.size();
    }

    stable_sort(words.begin(), words.end(), compare);

However, the entire motive of creating functions is to promote reusability of a particular piece of code. Since we are not going to use this function for other purposes in this program, an efficient alternative is to use Lambda functions.

stable_sort(words.begin(), words.end(), [&](const string s1, const string s2)->bool {
            return s1.size() < s2.size();
        });

Lambda functions are anonymous functions which are defined without defining it. Sounds confusing right ?

Read this article to unravel the true power of lambda functions.

This was the approach to solve the problem easily using sort STL with custom compare function.

Another approach would be to use priority_queue where will be defining our own priority. The priority is a Heap data structure which is essentially a complete Binary Tree which maintains the top / least priority element at the top of the tree (root node). By creating custom priority function via operator overloading, we make make the priority elements store the elements based on our preference of priority as stated in the problem statement.

2. Using priority queue and custom priority function

class Solution {
public:

    class compare {
        public:
        bool operator()(const pair<int,string> &p1, const pair<int,string> &p2){
            if(p1.second.size() == p2.second.size()){   
                return p1.first > p2.first;            // arrange smaller index one first 
            }
            return p1.second.size() > p2.second.size();   // greater size settles down
        }
    };

    string arrangeWords(string text) {
        text[0]=tolower(text[0]);
        priority_queue<pair<int,string>,vector<pair<int,string>>,compare> pq;

        stringstream s(text);
        string temp;

        int i=1;            // for index 
        while(s>>temp)
            pq.push(make_pair(i++,temp));  

        string ans="";

        while(pq.size()!=0){
            ans+=pq.top().second+" ";
            pq.pop();
        }

        ans.pop_back();   // removing last space
        ans[0]=toupper(ans[0]);

        return ans;
    }
};

We are storing {index, element} pairs in the priority queue. This enables us to decide the order when two strings have the same size, wherein higher priority is given to the string with lesser index value.

class compare {
        public:
        bool operator()(const pair<int,string> &p1, const pair<int,string> &p2){
            if(p1.second.size() == p2.second.size()){   
                return p1.first > p2.first;            // arrange smaller index one first 
            }
            return p1.second.size() > p2.second.size();   // greater size settles down
        }
    };

If you carefully observe the above custom priority function, the conditions written are the exact opposite of the conditions mentioned in the problem statement.

In C++ STL, the top priority element is stored at the end of the underlying container. To remember in short, we try to mention the conditions which enables the element to settle down in the priority queue, when the element is added.

Here, we want strings with higher lengths to settle down in the priority queue, enabling the lesser length strings to stay on the top (higher priority).

That's all for this article. Custom functions in conjunction with STL functions and data structures enable developers to create efficient programs and is a powerful yet simple way to simplify things.

My next article would be an extension of this article and would be based on Functors in C++.

PS. There is no spelling mistake in Functors. Hope you liked this article. Feel free to connect with me on LinkedIn and GitHub for discussions and collaborations.