2

No código abaixo o programa deve ordenar o vector campanha se baseando na quantidade de votos de cada vereador:

#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;
}

Eu estou com dúvida de como funciona essa função de comparação que é usada no sort na linha:

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

Quais argumentos estariam recebendo os parâmetros x e y? e como o sort iria usar o valor do retorno para ordenar o vector?

2
  • O sorting algorithm utilizado pela função sort basicamente vai chamar a função que você passou. Se retornar true, considera-se o primeiro parâmetro menor que o segundo (ele virá antes no vetor). Se retornar false, considera-se o primeiro parâmetro maior que o segundo. É uma função genérica de comparação. Agora perguntar quando essa função é chamada varia de algoritmo para algoritmo. Veja um pseudo-código do quick sort: onde é feita uma comparação é provavelmente o local onde a sua lambda seria chamada. Commented 4/08/2021 às 3:21
  • Devo salientar que não há garantia que a implementação de sort de fato utiliza o algoritmo quick sort. A especificação da linguagem (desde C++ 11) só postula a complexidade que sort deve assumir, O(N * log(N)). Commented 4/08/2021 às 3:23

2 Respostas 2

4

Não sou um especialista em C++11, mas esse código tem algumas premissas que são tranquilas de entender.

O primeiro ponto aqui é em relação à sintaxe, []( Vereador x, Vereador y ){ return x.votos > y.votos; }. Isso é uma expressão lambda. Ela é uma função anônima criada unicamente para ser descartada, como se fosse uma variável sem maior importância, como a variável auto i que você criou no seu código.

Na documentação do próprio C++ sobre sort, você está usando a sobrecarga template< class RandomIt, class Compare > void sort( RandomIt first, RandomIt last, Compare comp );, onde você passa o iterador que marca o começo, o iterador que marca o fim e uma função de comparação. Na documentação, ele explica que comp é uma função que pega dois valores para comparar e retorna verdade se e somente se o primeiro argumento deve ficar a esquerda (ele é considerado "menor" segundo o critério de comparação).

Por exemplo:

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);

O valor armazendo em resultado será true, justamente porque, ao ordenar, angelo deveria ficar a esquerda de paulo.


Com a questão do lambda fora do caminho e entendo o que é esperado do terceiro argumento, fica a questão de quais seriam os argumentos de fato passados para o comparador. Na real? Não importa muito o como, essa é a graça.

Para fazer uma ordenação absoluta, você só precisa ser capaz de comparar dois valores por vez. Tome, por exemplo, um insertionsort escrito com um comparador genérico e um iterador também genérico:


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;
            }
        }
    }
}

Como seria chamado isso? Um exemplo:

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 que, ao chamar a minha função de ordenação, eu não me preocupei em como era o algoritmo de ordenação. Internamente ele poderia funcionar de qualquer jeito. Implementações comuns de ordenação normalmente incluem (mas não se limitam a):

Eu escolhi insertionsort pela simples facilidade de implementação. Poderia usar um 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;
            }
        }
    }
}

Que de todo jeito a maneira de chamar seria exatamente a mesma (ajeitando, claro, para o nome da função):

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;
}

Sobre coisas específicas do como o C++ faz as mágicas:

como os argumentos são passados para a função?

O C++ acessa o conteúdo do iterador. Eu posso pegar o conteúdo de um std::vector::iterator it usando o operador de derreferenciamento *it. Essa pode ser uma das estratégias usadas.

Eu tenho a suspeita que, na função lambda, declará-la como []( Vereador& x, Vereador& y ){ return x.votos > y.votos; } possa ser melhor na lida de objetos grandes, mas é mais suspeita do que por conhecimento consolidado ou prática.

como é usado o valor retornado para ordenar os valores?

Se você comparar um elemento a com o elemento b e retornar true, você sabe que a deveria vir antes de b. Se você pegou a mais próximo do começo do vetor, não precisa fazer nada; caso contrário, b é o elemento mais próximo do vetor, então precisa fazer o swap desses valores.

O retorno false é análogo, sempre tentando manter a ordem.

como ocorre a troca de posições, esse tal de swap?

Provavelmente eu creio que se use a função std::swap, mas funciona também fazendo uma troca de valores de modo mais tradicional. Isso é algo que pode ser feito de acordo com a implementação.

1

Questão 1

Quais argumentos estariam recebendo os parâmetros x e y?

x e y serão 2 instâncias de Vereador e a função será chamada sempre que o sort() precisar comparar dois Vereador, com os valores deles em x e y

em

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

Veja o protótipo de sort() em CPP Reference

sort() em cppReference

campanha é um vetor de Vereador então é isso que os iteradores vão retornar

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

Questão 2

como o sort iria usar o valor do retorno para ordenar o vector?

Para poder classificar um grupo de qualquer coisa é preciso poder comparar duas delas. Essa é a noção de ordem. E é isso que você está procurando. Por isso sort(), como qsort() em C, precisa da noção de <, de menor. Seja qual for a maneira que vai usar para classificar você precisa comparar os vereadores para saber qual vem antes de qual na ordem final.

Assim sort() não precisa saber o que está classificando, porque você diz como comparar dois elementos.

Se sua classe for trivialmente comparável, ou seja, se puder usar o operador < para comparar dois deles, pode omitir a função de classificação e usar apenas

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

Se puder usar ranges::sort() em C++20 pode escrever apenas sort(campanha) se a classe tiver o operador < e omitir os iteradores, classificando o vetor todo usando a noção de < para o que quer que tenha dentro do vetor. Imagine um vetor de int por exemplo.

Exemplos em C++

1. Implementando < para não precisar do terceiro parâmetro

struct Vereador
{
    string nome;
    int votos;

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

};

Note que a partir disso um Vereador será menor que outro Vereador se o nome em ordem alfabética por menor. Podia ser o CPF se tivesse isso no registro, ou um ter mais votos que outro, ou menos.

Uma vez que implementou isso para a classe não precisa mais do terceiro parâmetro no sort() e pode escrever

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

Então porque existe o tal parâmetro? Porque é mais dinâmico poder comparar na hora e se pode usar um critério diferente a cada chamada.

2. Usando functor para definir o outro parâmetro

Aqui se define o operador () para a classe Vereador. E o resultado dessa função é classificar os caras em ordem crescente de votos.

 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; };
};

E se pode escrever

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

3. usando uma função qualquer para comparar Vereador

Em C++ pode usar free_functions, funções que não estão dentro de nenhuma classe, para fazer as comparações de que o sort() precisa.

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();};

E se pode escrever como em C

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

4. Usando uma função lambda como parâmetro

Na própria linha do comando, como no seu exemplo, se pode colocar o código da função. A menos de uma função simples, one-liner, usar o código misturado no meio da chamada a sort() pode ser ruim de ler, estilo javascript.

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

E escrever então

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

Um programa completo com todos os exemplos acima

Para ficar mais curto, implementando o operador left bit shift << para Vereador


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

Assim centraliza a formatação de Vereador e o texto fica mais legível:

    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;

Separando a função lambda para ficar junto com os outros critérios de exemplo

Usando auto se pode levar a definição da comparação para o início do programa, onde estão as outras:

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() testando esses casos

Usando essas mudanças o código fica possívelmente mais fácil de ler:

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;
}

Saida do exemplo completo

==>     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

Usando seu código, apenas aumentei o tamanho de alguns nomes e testei com as funções de comparação descritas acima.

Espero que tenha entendido a mecânica disso.

O programa completo

#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;
}

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .