CODEWITHSUNDEEP
c++sortingstlpredicate
daljinder singh
daljinder singh

Reputation: 187

Using a predicate to sort according to size

I understood that a predicate takes argument from an input range of iterators and does operations as intended, but when we supply a binary predicate and a pair of iterators, how does it work? How are the elements of a container passed to the predicate?

E.g. std::sort sorts a vector of strings alphabetically by default, but to sort them according to sizes we can pass a predicate like:

sort(vec.begin(), vec.end(), [](const string &a, const string &b) {
    return a.size() < b.size();
});

So, this is supposed to sort the vector of strings vec by size and not alphabetically, but I can't understand how this is happening, i.e. how is the predicate taking elements of the vector as arguments and how is it sorting?

Upvotes: 2

Views: 1534

Answers (2)

Antoine Morrier
Antoine Morrier

Reputation: 4078

When std sort is called, the "normal" version of this function will perform some comparison using operator<. Like you understood, the comparison between two string is lexicographic (like a dictionary). However, people that developed the std::sort function think about cases like :

  1. There is no operator<
  2. User may want another way to sort it

Here it is where the predicate is useful. The predicate (like Igor Tandetnik says) is called inside the std::sortfunction.

So, with the normal version, std::sort will do something like that :

if(*a < *b) {
...
}

In the predicate version, it will do almost the same :

if(predicate(*a, *b)) {
...
}

Going that way, your predicate replace the operator< function.

Upvotes: 2

King Thrushbeard
King Thrushbeard

Reputation: 899

A binary predicate is nothing else than a callable object (including a function or lambda) that expects two parameters of the type of the dereferenced iterators of the container. Its "role" is to provide a comparison criteria for the sort algorithm.

The std::sort algorithm expects that this function or function object returns a value that is convertible to bool and which yields true, if and only if the first argument is before the second argument in the sort order (so-called strict weak order). The std::sort algorithm then operates (sorts) on the given range of objects (begin to end of container) by applying the predicate to elements when comparing the elements individually.

In your case, if the container is a vector of strings, the dereferenced iterators yield std:string and thus your lambda works fine.

Here is some example code showing how it works with a lambda that is independent of the concrete type, but requires at least the size() operation to be defined on the objects in the container. It also shows, how the binary predicate could be provided as a function object (in which case I reverted the sort order by inverting the predicate):

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>

using Words = std::vector<std::string>;

struct CompareReverse
{
    bool operator() (auto lhs, auto rhs)
    {
        return rhs.size() < lhs.size(); // less-than reversed!
    }
};

int main()
{
    Words words { "red", "green", "blue", "wizard", "a", "letter", "very-long-word" };

    std::sort(words.begin(), words.end(), [](auto a, auto b) { return a.size() < b.size(); });

    for (auto w : words)
        std::cout << w << std::endl;

    std::sort(words.begin(), words.end(), CompareReverse());

    for (auto w : words)
        std::cout << w << std::endl;

    return 0;
}

Upvotes: 1

Related Questions