c++ - sort - Ordenar un vector de objetos personalizados

ordenar un array java

Question

¿Cómo se puede ordenar un vector que contiene objetos personalizados (es decir, definidos por el usuario)?
Probablemente, se debe usar la clasificación del algoritmo STL 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 la clasificación) en el objeto personalizado.
¿Estoy en el camino correcto?

Answer 1

A continuación se muestra el código utilizando 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;
}

Answer 2

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

Answer 3

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

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

Answer 4

Estás en el camino correcto. std::sort utilizará el operator< como función de comparación de forma predeterminada. Entonces, para ordenar sus objetos, tendrá que sobrecargar el 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.

Answer 5

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

• std::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 distintos enfoques.

El "mejor" enfoque dependerá de diferentes factores:

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

Si los rangos de clasificación de X son una tarea común y se espera que se logre la clasificación (es decir, X simplemente envuelve un único valor fundamental) entonces probablemente irá a sobrecargar al operator< ya que permite la clasificación sin ningún problema (como pasar correctamente los comparadores adecuados) y repetidamente produce los resultados esperados.

Si la ordenación es una tarea común o es probable que se requiera en diferentes contextos, pero hay varios criterios que se pueden usar para ordenar los objetos X , optaría por Functors (funciones del operator() sobrecargado operator() de clases personalizadas) o punteros de función (es decir, Un funtor / función para el ordenamiento léxico y otro para el ordenamiento natural.

Si los rangos de clasificación del tipo X son infrecuentes o improbables en otros contextos, tiendo a usar lambdas en lugar de abarrotar 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 ver fácilmente la lógica detrás de la ordenación al mirar un 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 ordenación se aplicará.

Sin embargo, tenga en cuenta que la definición de un solo operator< es un único punto de falla, mientras que las 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 clasificación / se compila la plantilla de clasificación, el compilador podría verse obligado a realizar una llamada de función al comparar objetos, en lugar de alinear la lógica de ordenación, lo que podría ser un inconveniente grave (en menos cuando no se aplica la optimización de tiempo de enlace / generación de código).

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

Deje std::vector<X> vec_X; y std::vector<Y> 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.

operator< miembro 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 operator< libre 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 sobrecarga del bool operator()(T, T) para un tipo personalizado que se pueda 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 objeto de función se pueden escribir un poco más genéricas utilizando 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 el miembro i compatible con < .

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 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(l.i < r.i));
// sort by j
std::sort(v.begin(), v.end(), COMPARATOR(l.j < r.j));

Answer 6

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

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

El tercer parámetro utilizado puede ser mayor o menor o también puede usarse 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);

Answer 7

Podría usar funtor 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() );
}

Answer 8

Puede utilizar la clase comparadora definida por el usuario.

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

Answer 9

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

Answer 10

Tenía curiosidad por saber si existe un impacto medible en el rendimiento entre las distintas 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 necesita para copiarlo y ordenar su copia (y calcular una suma de comprobación para evitar la 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 el puntero de la función de paso, son muy similares, y pasar el puntero de la función provoca 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 --save- temps de salida).

Answer 11

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

Edición: 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 a un operador y cambiando la llamada de tipo 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>());

Answer 12

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

Answer 13

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á "swap".