Ordenar un vector de objetos personalizados

¿Cómo se hace para ordenar un vector que contiene objetos personalizados (es decir, definidos por el usuario)?
Probablemente, el algoritmo STL estándar ordenado junto con un predicado (una función o un objeto de función) que operaría en uno de los campos (como una clave para clasificar) en el objeto personalizado debería ser utilizado.
¿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 puedes 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 debes llamar a sort como:

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

En interés de la cobertura. Presenté una implementación usando expresiones lambda .

C ++ 11

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

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

  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 values; std::sort( values.begin(), values.end() ); // uses operator< std::sort( values.begin(), values.end(), C::before ); 

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

La ordenación de dicho vector o cualquier otro rango aplicable (iterador de entrada mutable) de objetos personalizados de tipo X se puede lograr utilizando varios métodos, especialmente el uso de algoritmos de biblioteca estándar como

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

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

El “mejor” enfoque dependerá de diferentes factores:

  1. ¿Es la ordenación de rangos de objetos X una tarea común o rara (tales rangos se ordenarán en varios lugares diferentes en el progtwig o por usuarios de la biblioteca)?
  2. ¿La clasificación requerida es “natural” (esperada) o hay varias formas en que se puede comparar el tipo consigo mismo?
  3. ¿El rendimiento es un problema o los rangos de clasificación de los objetos X deben ser infalibles?

Si clasificar los rangos de X es una tarea común y la clasificación lograda es esperable (es decir, X simplemente envuelve un único valor fundamental), entonces probablemente se aplicará el operator< sobrecarga operator< ya que permite la clasificación sin pelusas (como pasar correctamente los comparadores adecuados) y arroja repetidamente los resultados esperados.

Si la clasificación es una tarea común o probable que se requiera en diferentes contextos, pero existen múltiples criterios que se pueden usar para ordenar objetos X , iría por Functors (funciones de operator() sobrecargadas de clases personalizadas) o punteros a funciones (es decir, un functor / función para ordenamiento léxico y otro para ordenamiento natural).

Si ordenar rangos de tipo X es poco común o improbable 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 de la ordenación cuando mira una lambda que se aplica en el lugar, mientras que el operator< es opaco a primera vista y tendría que buscar la definición para saber qué lógica de ordenamiento se aplicará.

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

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

Formas de lograr la comparabilidad de la class X para usar algoritmos de clasificación de bibliotecas estándar

Deje std::vector vec_X; y std::vector vec_Y;

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

Cualquiera de los operator< miembro de sobrecarga operator< :

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

o operator< libre operator< :

 struct Y { int j{}; }; bool operator<(Y const &l, Y const &r) { return lj < rj; } // ... 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 li < ri; } // ... std::sort(vec_X.begin(), vec_X.end(), &X_less); 

3. Cree una sobrecarga del bool operator()(T, T) para un tipo personalizado que se puede pasar como un functor de comparación.

 struct X { int i{}; int j{}; }; struct less_X_i { bool operator()(X const &l, X const &r) const { return li < ri; } }; struct less_X_j { bool operator()(X const &l, X const &r) const { return lj < rj; } }; // 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 objeto de función se pueden escribir un poco más genérico usando C ++ 11 y plantillas:

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

que se puede usar para ordenar cualquier tipo con el miembro que soporta < .

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

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

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

que podría ser envuelto en una macro

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

haciendo la creación del comparador ordinario bastante suave:

 // sort by i std::sort(v.begin(), v.end(), COMPARATOR(li < ri)); // sort by j std::sort(v.begin(), v.end(), COMPARATOR(lj < rj)); 

Sí, std::sort() con un 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 al operador “<".

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

A continuación está el código usando lambdas

 #include "stdafx.h" #include  #include  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  // std::cout #include  // std::sort #include  // std::vector using namespace std; int main () { char myints[] = {'F','C','E','G','A','H','B','D'}; vector 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 << ' ' < 

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

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

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

 sort(vec.begin(),vec.end(),less()); 

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

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

 typedef struct Freqamp{ double freq; double amp; }FREQAMP; bool struct_cmp_by_freq(FREQAMP a, FREQAMP b) { return a.freq < b.freq; } main() { vector  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 compare es falso, hará “swap”.

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

 $ cat sort.cpp #include #include #include #include #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 & v){ sort(v.begin(), v.end()); } void sort_by_lambda(vector & v){ sort(v.begin(), v.end(), []( const S& s1, const S& s2 ) BODY ); } void sort_by_functor(vector &v){ sort(v.begin(), v.end(), Sgreater()); } void sort_by_function(vector &v){ sort(v.begin(), v.end(), &Sgreater_func); } const int N = 10000000; vector random_vector; ulint run(void foo(vector &v)){ vector tmp(random_vector); foo(tmp); ulint checksum = 0; for(int i=0;i & 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>(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 

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

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

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

Aquí hay 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 a la función, son muy similares, y pasar un puntero a la función provoca una penalización de + 30%.

También parece que la