Ordenar un vector de objetos personalizados

¿Cómo se ordena un vector que contiene objetos personalizados (es decir, definidos por el usuario)?
Probablemente, el algoritmo estándar STL especie junto con un predicado (una función o un objeto función) que operaría en uno de los campos (como una clave para la clasificación) en el objeto personalizado se debe utilizar.
¿Estoy en el camino correcto?

Un ejemplo simple 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());

Editar: como señaló Kirill V. Lyadvinsky, en lugar de proporcionar un predicado de clasificación, puede implementar el 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);
    }
};

El uso de este método significa que simplemente puede ordenar el vector de la siguiente manera:

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

Edit2: como sugiere Kappa, también puede ordenar el vector en orden descendente sobrecargando un >operador y cambiando la llamada de ordenar un poco:

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

Y deberías llamar ordenar como:

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

En interés de la cobertura. Presento una implementación usando expresiones 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;
});

Podría usar functor como tercer argumento de std::sort, o podría definir operator<en su clase.

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

La clasificación de tal vectoro cualquier otro rango aplicable (iterador de entrada mutable) de objetos de tipo personalizados Xse puede lograr usando varios métodos, especialmente incluyendo el uso de algoritmos de biblioteca estándar como

• sort,
• stable_sort,
• partial_sort o
• partial_sort_copy.

Como la mayoría de las técnicas, para obtener un orden relativo de X elementos, ya se han publicado, comenzaré con algunas notas sobre "por qué" y "cuándo" usar los diversos enfoques.

El "mejor" enfoque dependerá de diferentes factores:

1. ¿La clasificación de rangos de Xobjetos es una tarea común o rara (se ordenarán dichos rangos en diferentes lugares del programa o por los usuarios de la biblioteca)?
2. ¿La clasificación requerida es "natural" (esperada) o hay varias formas en que el tipo podría compararse a sí mismo?
3. ¿El rendimiento es un problema o la clasificación de los rangos de Xobjetos debe ser infalible?

Si la ordenación de los rangos de Xes una tarea común y es de esperar la ordenación lograda (es decir, Xsimplemente envuelve un único valor fundamental), entonces probablemente iría por sobrecargaoperator< ya que permite la clasificación sin ninguna confusión (como pasar correctamente los comparadores adecuados) y produce repetidamente los resultados esperados resultados.

Si ordenar es una tarea común o es probable que se requiera en diferentes contextos, pero hay varios criterios que se pueden usar para ordenar Xobjetos, elegiría Functors ( operator()funciones sobrecargadas de clases personalizadas) o punteros de función (es decir, un functor / función para ordenamiento léxico y otro para ordenamiento natural).

Si ordena rangos de tipo X es poco común o poco probable en otros contextos, tiendo a usar lambdas en lugar de saturar cualquier espacio de nombres con más funciones o tipos.

Esto es especialmente cierto si la clasificación no es "clara" o "natural" de alguna manera. Puede obtener fácilmente la lógica detrás del pedido cuando mira una lambda que se aplica en el lugar, mientras que operator<es opaca a primera vista y tendría que buscar la definición para saber qué lógica de pedido se aplicará.

Sin embargo, operator<tenga en cuenta que una sola definición es un único punto de falla, mientras que múltiples lambas son múltiples puntos de falla y requieren más precaución.

Si la definición de operator< no está disponible donde se realiza la ordenación / se compila la plantilla de ordenación, el compilador podría verse obligado a realizar una llamada a la función al comparar objetos, en lugar de incluir la lógica de ordenación que podría ser un inconveniente grave (al menos cuando La optimización del tiempo de enlace / generación de código no se aplica).

Formas de lograr comparabilidad class Xpara utilizar algoritmos de clasificación de bibliotecas estándar

Dejar std::vector<X> vec_X;ystd::vector<Y> vec_Y;

1. Sobrecargue T::operator<(T)o operator<(T, T)use plantillas de biblioteca estándar que no esperen una función de comparación.

Cualquiera de los miembros 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());

o gratis 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. Utilice un puntero de función con una función de comparación personalizada como parámetro de función de clasificación.

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. Cree una bool operator()(T, T)sobrecarga para un tipo personalizado que se puede pasar como functor de comparación.

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

Esas definiciones de objetos de función se pueden escribir un poco más genéricas usando C ++ 11 y plantillas:

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 se puede usar para ordenar cualquier tipo con isoporte de miembros <.

4. Pase un cierre anónimo (lambda) como parámetro de comparación a las funciones de clasificación.

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

Donde C ++ 14 permite una expresión lambda aún más genérica:

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

que podría estar envuelto en una macro

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

haciendo que la creación de comparadores ordinarios sea bastante fluida:

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

Estás en el camino correcto. std::sortutilizará operator<como función de comparación por defecto. Entonces, para ordenar sus objetos, tendrá que sobrecargar bool operator<( const T&, const T& )o proporcionar un functor que haga la comparación, de esta manera:

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

La ventaja del uso de un functor es que puede usar una función con acceso a los miembros privados de la clase.

Tenía curiosidad por saber si hay algún impacto medible en el rendimiento entre las diversas formas en que se puede llamar std :: sort, así que he creado esta prueba simple:

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

Lo que hace es crear un vector aleatorio, y luego mide cuánto tiempo se requiere para copiarlo y clasificar la copia (y calcular alguna suma de comprobación para evitar una eliminación de código muerto demasiado vigorosa).

Estaba compilando con g ++ (GCC) 7.2.1 20170829 (Red Hat 7.2.1-1)

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

Aquí están los 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 las opciones, excepto pasar el puntero de función, son muy similares, y pasar un puntero de función causa una penalización de + 30%.

También parece que la versión del operador <es ~ 1% más lenta (repetí la prueba varias veces y el efecto persiste), lo cual es un poco extraño, ya que sugiere que el código generado es diferente (me falta habilidad para analizar, guardar) temperatura de salida).

Sí, std::sort()con el tercer parámetro (función u objeto) sería más fácil. Un ejemplo: http://www.cplusplus.com/reference/algorithm/sort/

En su clase, puede sobrecargar el operador "<".

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

Debajo está el 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;
    }

Puede usar la clase de comparación definida por el usuario.

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

Para ordenar un vector, puede usar el algoritmo sort ().

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

El tercer parámetro usado puede ser mayor o menor o también se puede usar cualquier función u objeto. Sin embargo, el operador predeterminado es <si deja el tercer parámetro vacío.

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

si comparar es falso, hará "intercambio".