Classificando um vetor de objetos personalizados

Como se classifica um vetor que contém objetos personalizados (isto é, definidos pelo usuário).
Provavelmente, padrão algoritmo STL tipo juntamente com um predicado (uma função ou um objeto de função), que operaria em um dos campos (como uma chave para a classificação) no objeto personalizado deve ser usado.
Estou no caminho certo?

Um exemplo simples usando std::sort

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

struct less_than_key
{
    inline bool operator() (const MyStruct& struct1, const MyStruct& struct2)
    {
        return (struct1.key < struct2.key);
    }
};

std::vector < MyStruct > vec;

vec.push_back(MyStruct(4, "test"));
vec.push_back(MyStruct(3, "a"));
vec.push_back(MyStruct(2, "is"));
vec.push_back(MyStruct(1, "this"));

std::sort(vec.begin(), vec.end(), less_than_key());

Edit: Como Kirill V. Lyadvinsky apontou, em vez de fornecer um predicado de classificação, você pode implementar o operator<para MyStruct:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator < (const MyStruct& str) const
    {
        return (key < str.key);
    }
};

O uso desse método significa que você pode simplesmente classificar o vetor da seguinte maneira:

std::sort(vec.begin(), vec.end());

Edit2: Como Kappa sugere, você também pode classificar o vetor na ordem decrescente sobrecarregando um >operador e alterando um pouco a chamada de classificação:

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}

    bool operator > (const MyStruct& str) const
    {
        return (key > str.key);
    }
};

E você deve chamar classificar como:

std::sort(vec.begin(), vec.end(),greater<MyStruct>());

No interesse da cobertura. Eu propus uma implementação usando expressões lambda .

C ++ 11

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const MyStruct& lhs, const MyStruct& rhs )
{
   return lhs.key < rhs.key;
});

C ++ 14

#include <vector>
#include <algorithm>

using namespace std;

vector< MyStruct > values;

sort( values.begin( ), values.end( ), [ ]( const auto& lhs, const auto& rhs )
{
   return lhs.key < rhs.key;
});

Você pode usar o functor como terceiro argumento de std::sortou definir operator<em sua classe.

struct X {
    int x;
    bool operator<( const X& val ) const { 
        return x < val.x; 
    }
};

struct Xgreater
{
    bool operator()( const X& lx, const X& rx ) const {
        return lx.x < rx.x;
    }
};

int main () {
    std::vector<X> my_vec;

    // use X::operator< by default
    std::sort( my_vec.begin(), my_vec.end() );

    // use functor
    std::sort( my_vec.begin(), my_vec.end(), Xgreater() );
}

A classificação de um vectorou qualquer outro intervalo aplicável (iterador de entrada mutável) de objetos personalizados do tipo Xpode ser alcançado usando vários métodos, especialmente incluindo o uso de algoritmos de biblioteca padrão, como

• sort,
• stable_sort,
• partial_sort ou
• partial_sort_copy.

Como a maioria das técnicas, para obter a ordenação relativa dos Xelementos, já foi publicada, começarei com algumas notas sobre "por que" e "quando" para usar as várias abordagens.

A abordagem "melhor" dependerá de diferentes fatores:

1. A classificação de intervalos de Xobjetos é uma tarefa comum ou rara (esses intervalos serão classificados em vários locais diferentes no programa ou pelos usuários da biblioteca)?
2. A classificação necessária é "natural" (esperada) ou existem várias maneiras pelas quais o tipo pode ser comparado a si mesmo?
3. O desempenho é um problema ou a classificação dos intervalos de Xobjetos deve ser infalível?

Se a classificação de intervalos Xfor uma tarefa comum e a classificação alcançada for esperada (ou seja, Xapenas agrupar um único valor fundamental), provavelmente a sobrecarga será necessária, operator<uma vez que permite a classificação sem distorção (como passar corretamente os comparadores adequados) e gera repetidamente os resultados esperados resultados.

Se a classificação é uma tarefa comum ou provavelmente requerida em contextos diferentes, mas existem vários critérios que podem ser usados ​​para classificar Xobjetos, eu usaria Functors ( operator()funções sobrecarregadas de classes personalizadas) ou ponteiros de função (ou seja, um functor / função para pedidos lexicais e outro para pedidos naturais).

Se os intervalos de classificação do tipo Xsão incomuns ou improváveis ​​em outros contextos, costumo usar lambdas em vez de sobrecarregar qualquer espaço de nome com mais funções ou tipos.

Isso é especialmente verdadeiro se a classificação não for "clara" ou "natural" de alguma forma. Você pode facilmente obter a lógica por trás da ordem ao olhar para um lambda que é aplicado no local, enquanto que operator<é ofensivo à primeira vista e você precisa procurar a definição para saber qual lógica de ordem será aplicada.

Observe, no entanto, que uma única operator<definição é um único ponto de falha, enquanto várias lambas são múltiplos pontos de falha e requerem mais cautela.

Se a definição de operator<não estiver disponível onde a classificação é feita / o modelo de classificação é compilado, o compilador pode ser forçado a fazer uma chamada de função ao comparar objetos, em vez de incluir a lógica de ordenação, o que pode ser uma desvantagem grave (pelo menos quando otimização do tempo do link / geração de código não é aplicada).

Maneiras de obter comparabilidade class Xpara usar algoritmos de classificação de biblioteca padrão

Deixe std::vector<X> vec_X;estd::vector<Y> vec_Y;

1. Sobrecarregue T::operator<(T)ou operator<(T, T)use modelos de biblioteca padrão que não esperam uma função de comparação.

Qualquer membro de sobrecarga operator<:

struct X {
  int i{}; 
  bool operator<(X const &r) const { return i < r.i; } 
};
// ...
std::sort(vec_X.begin(), vec_X.end());

ou grátis operator<:

struct Y {
  int j{}; 
};
bool operator<(Y const &l, Y const &r) { return l.j < r.j; }
// ...
std::sort(vec_Y.begin(), vec_Y.end());

2. Use um ponteiro de função com uma função de comparação personalizada como parâmetro da função de classificação.

struct X {
  int i{};  
};
bool X_less(X const &l, X const &r) { return l.i < r.i; }
// ...
std::sort(vec_X.begin(), vec_X.end(), &X_less);

3. Crie uma bool operator()(T, T)sobrecarga para um tipo personalizado que pode ser passado como função de comparação.

struct X {
  int i{};  
  int j{};
};
struct less_X_i
{
    bool operator()(X const &l, X const &r) const { return l.i < r.i; }
};
struct less_X_j
{
    bool operator()(X const &l, X const &r) const { return l.j < r.j; }
};
// sort by i
std::sort(vec_X.begin(), vec_X.end(), less_X_i{});
// or sort by j
std::sort(vec_X.begin(), vec_X.end(), less_X_j{});

Essas definições de objeto de função podem ser escritas um pouco mais genéricas usando C ++ 11 e modelos:

struct less_i
{ 
    template<class T, class U>
    bool operator()(T&& l, U&& r) const { return std::forward<T>(l).i < std::forward<U>(r).i; }
};

que pode ser usado para classificar qualquer tipo com isuporte de membro <.

4. Passe um fechamento anônimo (lambda) como parâmetro de comparação para as funções de classificação.

struct X {
  int i{}, j{};
};
std::sort(vec_X.begin(), vec_X.end(), [](X const &l, X const &r) { return l.i < r.i; });

Onde o C ++ 14 permite uma expressão lambda ainda mais genérica:

std::sort(a.begin(), a.end(), [](auto && l, auto && r) { return l.i < r.i; });

que pode ser envolvido em uma macro

#define COMPARATOR(code) [](auto && l, auto && r) -> bool { return code ; }

simplificando a criação de comparadores comuns:

// sort by i
std::sort(v.begin(), v.end(), COMPARATOR(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

Você está no caminho certo. std::sortusará operator<como função de comparação por padrão. Portanto, para classificar seus objetos, você precisará sobrecarregar bool operator<( const T&, const T& )ou fornecer um functor que faça a comparação, assim:

 struct C {
    int i;
    static bool before( const C& c1, const C& c2 ) { return c1.i < c2.i; }
 };

 bool operator<( const C& c1, const C& c2 ) { return c1.i > c2.i; }

 std::vector<C> values;

 std::sort( values.begin(), values.end() ); // uses operator<
 std::sort( values.begin(), values.end(), C::before );

A vantagem do uso de um functor é que você pode usar uma função com acesso aos membros privados da classe.

Fiquei curioso para saber se há algum impacto mensurável no desempenho entre as várias maneiras de chamar std :: sort, então criei este teste simples:

$ cat sort.cpp
#include<algorithm>
#include<iostream>
#include<vector>
#include<chrono>

#define COMPILER_BARRIER() asm volatile("" ::: "memory");

typedef unsigned long int ulint;

using namespace std;

struct S {
  int x;
  int y;
};

#define BODY { return s1.x*s2.y < s2.x*s1.y; }

bool operator<( const S& s1, const S& s2 ) BODY
bool Sgreater_func( const S& s1, const S& s2 ) BODY

struct Sgreater {
  bool operator()( const S& s1, const S& s2 ) const BODY
};

void sort_by_operator(vector<S> & v){
  sort(v.begin(), v.end());
}

void sort_by_lambda(vector<S> & v){
  sort(v.begin(), v.end(), []( const S& s1, const S& s2 ) BODY );
}

void sort_by_functor(vector<S> &v){
  sort(v.begin(), v.end(), Sgreater());
}

void sort_by_function(vector<S> &v){
  sort(v.begin(), v.end(), &Sgreater_func);
}

const int N = 10000000;
vector<S> random_vector;

ulint run(void foo(vector<S> &v)){
  vector<S> tmp(random_vector);
  foo(tmp);
  ulint checksum = 0;
  for(int i=0;i<tmp.size();++i){
     checksum += i *tmp[i].x ^ tmp[i].y;
  }
  return checksum;
}

void measure(void foo(vector<S> & v)){

ulint check_sum = 0;

  // warm up
  const int WARMUP_ROUNDS = 3;
  const int TEST_ROUNDS = 10;

  for(int t=WARMUP_ROUNDS;t--;){
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
  }

  for(int t=TEST_ROUNDS;t--;){
    COMPILER_BARRIER();
    auto start = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    check_sum += run(foo);
    COMPILER_BARRIER();
    auto end = std::chrono::high_resolution_clock::now();
    COMPILER_BARRIER();
    auto duration_ns = std::chrono::duration_cast<std::chrono::duration<double>>(end - start).count();

    cout << "Took " << duration_ns << "s to complete round" << endl;
  }

  cout << "Checksum: " << check_sum << endl;
}

#define M(x) \
  cout << "Measure " #x " on " << N << " items:" << endl;\
  measure(x);

int main(){
  random_vector.reserve(N);

  for(int i=0;i<N;++i){
    random_vector.push_back(S{rand(), rand()});
  }

  M(sort_by_operator);
  M(sort_by_lambda);
  M(sort_by_functor);
  M(sort_by_function);
  return 0;
}

O que ele faz é criar um vetor aleatório e, em seguida, mede quanto tempo é necessário para copiá-lo e classificá-lo (e calcular alguma soma de verificação para evitar a eliminação muito vigorosa de código morto).

Eu estava compilando com g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

$ g++ -O2 -o sort sort.cpp && ./sort

Aqui estão os resultados:

Measure sort_by_operator on 10000000 items:
Took 0.994285s to complete round
Took 0.990162s to complete round
Took 0.992103s to complete round
Took 0.989638s to complete round
Took 0.98105s to complete round
Took 0.991913s to complete round
Took 0.992176s to complete round
Took 0.981706s to complete round
Took 0.99021s to complete round
Took 0.988841s to complete round
Checksum: 18446656212269526361
Measure sort_by_lambda on 10000000 items:
Took 0.974274s to complete round
Took 0.97298s to complete round
Took 0.964506s to complete round
Took 0.96899s to complete round
Took 0.965773s to complete round
Took 0.96457s to complete round
Took 0.974286s to complete round
Took 0.975524s to complete round
Took 0.966238s to complete round
Took 0.964676s to complete round
Checksum: 18446656212269526361
Measure sort_by_functor on 10000000 items:
Took 0.964359s to complete round
Took 0.979619s to complete round
Took 0.974027s to complete round
Took 0.964671s to complete round
Took 0.964764s to complete round
Took 0.966491s to complete round
Took 0.964706s to complete round
Took 0.965115s to complete round
Took 0.964352s to complete round
Took 0.968954s to complete round
Checksum: 18446656212269526361
Measure sort_by_function on 10000000 items:
Took 1.29942s to complete round
Took 1.3029s to complete round
Took 1.29931s to complete round
Took 1.29946s to complete round
Took 1.29837s to complete round
Took 1.30132s to complete round
Took 1.3023s to complete round
Took 1.30997s to complete round
Took 1.30819s to complete round
Took 1.3003s to complete round
Checksum: 18446656212269526361

Parece que todas as opções, exceto a passagem do ponteiro de função, são muito semelhantes e a passagem de um ponteiro de função causa + 30% de penalidade.

Também parece que o operador <versão é ~ 1% mais lento (repeti o teste várias vezes e o efeito persiste), o que é um pouco estranho, pois sugere que o código gerado é diferente (não tenho habilidade para analisar --salvar- saída de temperatura).

Sim, std::sort()com o terceiro parâmetro (função ou objeto) seria mais fácil. Um exemplo: http://www.cplusplus.com/reference/algorithm/sort/

Na sua turma, você pode sobrecarregar o operador "<".

class MyClass
{
  bool operator <(const MyClass& rhs)
  {
    return this->key < rhs.key;
  }
}

Abaixo está o código usando lambdas

#include "stdafx.h"
#include <vector>
#include <algorithm>

using namespace std;

struct MyStruct
{
    int key;
    std::string stringValue;

    MyStruct(int k, const std::string& s) : key(k), stringValue(s) {}
};

int main()
{
    std::vector < MyStruct > vec;

    vec.push_back(MyStruct(4, "test"));
    vec.push_back(MyStruct(3, "a"));
    vec.push_back(MyStruct(2, "is"));
    vec.push_back(MyStruct(1, "this"));

    std::sort(vec.begin(), vec.end(), 
        [] (const MyStruct& struct1, const MyStruct& struct2)
        {
            return (struct1.key < struct2.key);
        }
    );
    return 0;
}

    // sort algorithm example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::sort
    #include <vector>       // std::vector
    using namespace std;
    int main () {
        char myints[] = {'F','C','E','G','A','H','B','D'};
        vector<char> myvector (myints, myints+8);               // 32 71 12 45 26 80 53 33
        // using default comparison (operator <):
        sort (myvector.begin(), myvector.end());           //(12 32 45 71)26 80 53 33
        // print out content:
        cout << "myvector contains:";
        for (int i=0; i!=8; i++)
            cout << ' ' <<myvector[i];
        cout << '\n';
        system("PAUSE");
    return 0;
    }

Você pode usar a classe comparadora definida pelo usuário.

class comparator
{
    int x;
    bool operator()( const comparator &m,  const comparator &n )
    { 
       return m.x<n.x;
    }
 }

Para classificar um vetor, você pode usar o algoritmo sort ().

sort(vec.begin(),vec.end(),less<int>());

O terceiro parâmetro usado pode ser maior ou menor ou qualquer função ou objeto também pode ser usado. No entanto, o operador padrão é <se você deixar o terceiro parâmetro vazio.

// using function as comp
std::sort (myvector.begin()+4, myvector.end(), myfunction);
bool myfunction (int i,int j) { return (i<j); }

// using object as comp
std::sort (myvector.begin(), myvector.end(), myobject);

typedef struct Freqamp{
    double freq;
    double amp;
}FREQAMP;

bool struct_cmp_by_freq(FREQAMP a, FREQAMP b)
{
    return a.freq < b.freq;
}

main()
{
    vector <FREQAMP> temp;
    FREQAMP freqAMP;

    freqAMP.freq = 330;
    freqAMP.amp = 117.56;
    temp.push_back(freqAMP);

    freqAMP.freq = 450;
    freqAMP.amp = 99.56;
    temp.push_back(freqAMP);

    freqAMP.freq = 110;
    freqAMP.amp = 106.56;
    temp.push_back(freqAMP);

    sort(temp.begin(),temp.end(), struct_cmp_by_freq);
}

se a comparação for falsa, fará "troca".