How to use comparison function on a Std::Sort

Question

In the code below the program must order the vector campanha based on the number of votes of each councilor:

#include <iostream>
#include <vector>


using namespace std;

struct Vereador
{
    string nome;
    int votos;
};


int main()
{
    vector<Vereador> campanha
    {
        { "Angelo Orlando", 6580 },
        { "Paulo Furini",   3985 },
        { "Augusto Jacob",  9025 },
        { "Chico Sardelli", 5900 }
    };
    
    sort( campanha.begin(), campanha.end(),
        []( Vereador x, Vereador y ){ return x.votos > y.votos; } );
    
    
    for( auto i: campanha )
        cout << "Candidato: " << i.nome << "\tVotos: " << i.votos << endl;
    
    
    return 0;
}

I’m wondering how this comparison function works which is used on the line Sort:

sort( campanha.begin(), campanha.end(),
                []( Vereador x, Vereador y ){ return x.votos > y.votos; } );

What arguments would be receiving the parameters x and y? and how Sort would use the return value to sort the vector?

Answer 1

I’m not a C++11 expert, but this code has some assumptions that are easy to understand.

The first point here is regarding syntax, []( Vereador x, Vereador y ){ return x.votos > y.votos; }. That’s a lambda expression. It is an anonymous function created solely to be discarded, as if it were an unimportant variable, such as the variable auto i that you created in your code.

In the documentation of the C++ on sort, you are using the overload template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp );, where you pass the iterator that marks the beginning, the iterator that marks the end and a comparison function. In the documentation, he explains that comp is a function that takes two values to compare and returns truth if and only if the first argument should be left (it is considered "smaller" according to the comparison criterion).

For example:

auto comparador = [](Vereador x, Vereador y) { return x.votos > y.votos; };

Vereador angelo = { "Angelo Orlando", 6580 };
Vereador paulo = { "Paulo Furini",   3985 }

auto resultado = comparador(angelo, paulo);

The value storing as a result will be true, precisely because, in ordering, angelo should stand to the left of paulo.

---

With the lambda question out of the way and I understand what is expected of the third argument, the question remains as to what arguments were actually passed to the comparator. Really? It doesn’t matter much like, that’s the fun.

To make an absolute ordering, you only need to be able to compare two values at a time. Take, for example, a insertionsort written with a generic comparator and a generic iterator:

template<class RandomIt, class Comparador>
void insertionsort(RandomIt comeco, RandomIt fim, Comparador cmp) {
    for (RandomIt it = comeco + 1; it != fim ; it++) {
        for (RandomIt it2 = it; it2 != comeco; it2--) {
            RandomIt prev = it2 - 1;
            if (cmp(*it2, *prev)) {
              auto e = *it2;
              *it2 = *prev;
              *prev = e;
            }
        }
    }
}

What would be called this? An example:

int main() {
    std::vector<int> v = {3, 3, 2, 1};

    insertionsort(v.begin(), v.end(), [](int a, int b) { return a < b;});
    my_for_each(v.begin(), v.end(), [](int a) { std::cout << a << std::endl;}); // saída, cada número em sua própria linha: 1 2 3 3
    return 0;
}

Note that when calling my sort function, I didn’t care what the sort algorithm looked like. Internally it could work anyway. Common sorting implementations usually include (but are not limited to):

• Timsort
• Quicksort
• Mergesort

I chose insertionsort simple ease of implementation. Could use a bubblesort:

template<class RandomIt, class Comparador>
void bubblesort(RandomIt comeco, RandomIt fim, Comparador cmp) {
    for (RandomIt it = fim - 1; it != comeco ; it--) {
        for (RandomIt it2 = comeco; it2 != it; it2++) {
            RandomIt next = it2 + 1;
            if (!cmp(*it2, *next)) {
              auto e = *it2;
              *it2 = *next;
              *next = e;
            }
        }
    }
}

That anyway the way of calling would be exactly the same (setting, of course, to the name of the function):

int main() {
    std::vector<int> v = {3, 3, 2, 1};

    bubblesort(v.begin(), v.end(), [](int a, int b) { return a < b;});
    my_for_each(v.begin(), v.end(), [](int a) { std::cout << a << std::endl;}); // saída, cada número em sua própria linha: 1 2 3 3
    return 0;
}

---

About specific things like how C++ does magic:

how arguments are passed to the function?

C++ accesses the iterator’s content. I can take the contents of a std::vector::iterator it using the derreferencing operator *it. This may be one of the strategies used.

I have the suspicion that, in lambda function, declare it as []( Vereador& x, Vereador& y ){ return x.votos > y.votos; } may be better at dealing with large objects, but is more suspicious than by consolidated knowledge or practice.

how the returned value is used to sort the values?

If you compare an element a with the element b and return true, you know that a should come before b. If you took a closer to the beginning of the vector, you don’t need to do anything; otherwise, b is the closest element to the vector, so you need to do the swap of these values.

The return false is analogous, always trying to maintain order.

the exchange of positions, such as swap?

Probably I think if I use the function std::swap, but it also works by doing a more traditional exchange of values. This is something that can be done according to the implementation.

Answer 2

Question 1

What arguments would be receiving parameters x and y?

x and y will be 2 instances of Vereador and the function will be called whenever the sort() need to compare two Vereador, with their values in x and y

in

 sort( campanha.begin(), campanha.end(),
        []( Vereador x, Vereador y ){ return x.votos > y.votos; } );

See the prototype of Sort() in CPP Reference

campanha is a vector of Vereador then that’s what the iterators will return

    vector<Vereador> campanha
    {
        { "Angelo Orlando", 6580 },
        { "Paulo Furini",   3985 },
        { "Augusto Jacob",  9025 },
        { "Chico Sardelli", 5900 }
    };

Question 2

how Sort would use the return value to sort the vector?

To be able to classify a group of anything you need to be able to compare two of them. That’s the notion of order. And that’s what you’re looking for. That’s why sort(), as qsort() in C, needs the notion of <, minor. Whatever way you will use to rank you need to compare councilors to know which comes before which in the final order.

Thus sort() you don’t need to know what you’re sorting, because you say how to compare two elements.

If your class is trivially comparable, ie if you can use the operator < to compare two of them, you can omit the sort function and use only

 sort( campanha.begin(), campanha.end() );

If I may use ranges::sort() in C++20 you can write only sort(campanha) if the class has the operator < and omit iterators, classifying the whole vector using the notion of < for whatever is inside the vector. Imagine a vector of int for example.

Examples in C++

1. Implementing < to not need the third parameter

struct Vereador
{
    string nome;
    int votos;

    friend bool operator< (const Vereador& um, const Vereador& outro)
    { return um.nome < outro.nome; };

};

Note that from this one Vereador will be smaller than another Vereador if the name in alphabetical order by minor. It could be the CPF if it had this in the record, or um have more votes than outro, or less.

Once you have implemented this for the class you no longer need the third parameter in the sort() and can write

    sort(campanha.begin(), campanha.end());

So why is there such a parameter? Because it is more dynamic to be able to compare on time and you can use a different criterion for each call.

2. Using functor to set the other parameter

This defines the operator () for the class Vereador. And the result of that function is to sort the guys in ascending order of votes.

 struct Vereador
{
    string nome;
    int    votos;

    bool operator()(const Vereador& um, const Vereador& outro)
    { return um.votos < outro.votos; };

    friend bool operator<(const Vereador& um, const Vereador& outro)
    { return um.nome < outro.nome; };
};

And you can write

    sort(campanha.begin(), campanha.end(), Vereador());

3. using any function to compare Vereador

In C++ you can use free_functions, functions that are not within any class, to make comparisons that the sort() accurate.

struct Vereador
{
    string nome;
    int    votos;

    bool operator()(const Vereador& um, const Vereador& outro)
    { return um.votos < outro.votos; };

    friend bool operator<(const Vereador& um, const Vereador& outro)
    { return um.nome < outro.nome; };
};

const bool free_function( const Vereador& A, const Vereador& B)
{    return A.nome.length() < B.nome.length();};

And you can write as in C

    sort(campanha.begin(), campanha.end(), free_function);

4. Using a lambda function as parameter

In the command line itself, as in your example, you can place the function code. Less than one simple function, one-Liner, use the mixed code in the middle of the call to sort() can be bad to read, style javascript.

        []( Vereador x, Vereador y ){ return x.votos > y.votos; } );

And then write

    sort(campanha.begin(), campanha.end(),
        []( Vereador x, Vereador y ){ return x.votos > y.votos; } );

A complete program with all the above examples

To get shorter by implementing the operator left bit shift << for Vereador

    friend ostream& operator<<(ostream& saida, const Vereador& V)
    {
        saida << V.nome << "\tVotos: " << V.votos << "\n";
        return saida;
    }

Thus centralizes the formatting of Councilman and the text is more readable:

    sort(campanha.begin(), campanha.end()); // operador < da classe
    cout << "\n\n==>\tdepois do sort, em ordem de nome\n";
    for (auto i : campanha) cout << i;

Separating the lambda function to stay together with the other example criteria

Using auto one can take the comparison setting to the beginning of the program, where are the others:

struct Vereador
{
    string nome;
    int    votos;

    bool operator()(const Vereador& um, const Vereador& outro)
    { return um.votos < outro.votos; };

    friend bool operator<(const Vereador& um, const Vereador& outro)
    { return um.nome < outro.nome; };

    friend ostream& operator<<(ostream& saida, const Vereador& V)
    {
        saida << V.nome << "\tVotos: " << V.votos << "\n";
        return saida;
    }
};

const bool free_function( const Vereador& A, const Vereador& B)
{    return A.nome.length() < B.nome.length();};

auto uma = []( Vereador x, Vereador y )
{    return x.votos > y.votos; };

main() testing these cases

Using these changes the code is possibly easier to read:

int main(void)
{
    vector<Vereador> campanha
    {
        { "Angelo Orlando III", 6580 },
        { "Paulo  Furini Jr.",   3985 },
        { "Augusto Jacob",  9025 },
        { "Chico Sardelli Senior", 5900 }
    };

    cout << "==>\tOrdem original:\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), uma ); // lambda
    cout << "\n\n==>\tdepois do sort, em ordem decrescente de votos\n";   
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end()); // operador < da classe
    cout << "\n\n==>\tdepois do sort, em ordem de nome\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), Vereador()); // functor
    cout << "\n\n==>\tdepois do sort, em ordem crescente de votos\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), free_function); // free function
    cout << "\n\n==>\tdepois do sort, em ordem crescente de tamanho no nome\n";
    for (auto i : campanha) cout << i;

    return 0;
}

Exit from the complete example

==>     Ordem original:
Angelo Orlando III      Votos: 6580
Paulo  Furini Jr.       Votos: 3985
Augusto Jacob   Votos: 9025
Chico Sardelli Senior   Votos: 5900


==>     depois do sort, em ordem decrescente de votos
Augusto Jacob   Votos: 9025
Angelo Orlando III      Votos: 6580
Chico Sardelli Senior   Votos: 5900
Paulo  Furini Jr.       Votos: 3985


==>     depois do sort, em ordem de nome
Angelo Orlando III      Votos: 6580
Augusto Jacob   Votos: 9025
Chico Sardelli Senior   Votos: 5900
Paulo  Furini Jr.       Votos: 3985


==>     depois do sort, em ordem crescente de votos
Paulo  Furini Jr.       Votos: 3985
Chico Sardelli Senior   Votos: 5900
Angelo Orlando III      Votos: 6580
Augusto Jacob   Votos: 9025


==>     depois do sort, em ordem crescente de tamanho no nome
Augusto Jacob   Votos: 9025
Paulo  Furini Jr.       Votos: 3985
Angelo Orlando III      Votos: 6580
Chico Sardelli Senior   Votos: 5900

Using your code, I just increased the size of some names and tested with the comparison functions described above.

I hope you understand the mechanics of this.

The complete program

#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>


using namespace std;

struct Vereador
{
    string nome;
    int    votos;

    bool operator()(const Vereador& um, const Vereador& outro)
    { return um.votos < outro.votos; };

    friend bool operator<(const Vereador& um, const Vereador& outro)
    { return um.nome < outro.nome; };

    friend ostream& operator<<(ostream& saida, const Vereador& V)
    {
        saida << V.nome << "\tVotos: " << V.votos << "\n";
        return saida;
    }
};

const bool free_function( const Vereador& A, const Vereador& B)
{    return A.nome.length() < B.nome.length();};

auto uma = []( Vereador x, Vereador y )
{    return x.votos > y.votos; };


int main(void)
{
    vector<Vereador> campanha
    {
        { "Angelo Orlando III", 6580 },
        { "Paulo  Furini Jr.",   3985 },
        { "Augusto Jacob",  9025 },
        { "Chico Sardelli Senior", 5900 }
    };
  
    cout << "==>\tOrdem original:\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), uma ); // lambda
    cout << "\n\n==>\tdepois do sort, em ordem decrescente de votos\n";   
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end()); // operador < da classe
    cout << "\n\n==>\tdepois do sort, em ordem de nome\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), Vereador()); // functor
    cout << "\n\n==>\tdepois do sort, em ordem crescente de votos\n";
    for (auto i : campanha) cout << i;

    sort(campanha.begin(), campanha.end(), free_function); // free function
    cout << "\n\n==>\tdepois do sort, em ordem crescente de tamanho no nome\n";
    for (auto i : campanha) cout << i;

    return 0;
}