Ordenar un vector de objetos personalizados

10 minutos de lectura

¿Cómo se ordena un vector que contiene objetos personalizados (es decir, definidos por el usuario)?
Probablemente, algoritmo STL estándar clasificar 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 ordenar) en el objeto personalizado debe usarse.
¿Estoy en el camino correcto?

  • Posible duplicado de clasificación de biblioteca estándar y tipos definidos por el usuario

    – MCCCS

    9 de junio de 2018 a las 13:18

Ordenar un vector de objetos personalizados
Alan

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

Usar 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 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 a ordenar como:

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

  • ¿Podría explicar por qué hizo la función de comparación en la estructura less_than_key (en el primer) ejemplo en línea?

    – kluka

    15 mayo 2013 a las 18:10

  • y otra pregunta/nota: si a uno le gustaría tener múltiples métodos de clasificación (para diferentes atributos) en una clase, la forma de sobrecargar el operador < probablemente no sea una opción, ¿verdad?

    – kluka

    15 mayo 2013 a las 18:28

  • Una cosa genial es proporcionar también el método operator>. Esto nos permitirá ordenar en orden inverso como: std::sort(vec.begin(), vec.end(), greater<MyStruct>())que es limpio y elegante.

    – kappa

    30 mayo 2014 a las 23:21

  • @Bovaz Tienes que #include <functional> para usar “std::mayor”.

    –Nick Hartung

    31 de agosto de 2015 a las 15:21


  • @kappa: Donde podrías simplemente tener operator< y usa cualquiera std::sort(vec.begin(), vec.end()); o std::sort(vec.rbegin(), vec.rend()); dependiendo de si desea tener un orden ascendente o descendente.

    – Pixelquímico

    19 mayo 2016 a las 22:24


Ordenar un vector de objetos personalizados
Ben Crowhurst

En interés de la cobertura. Presenté 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;
});

  • +1 adicional por incluir el #incluye

    – Ana

    3 mayo 2016 a las 17:35

  • Para ser claros, esto resulta en orden ascendente; utilizar > en lugar de < para obtener un orden descendente.

    – bhaller

    27 de abril de 2017 a las 4:53

1647626116 546 Ordenar un vector de objetos personalizados
Kirill V. Lyadvinsky

Podrías usar funtor como tercer argumento de std::sorto podrías definir operator< en tu 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() );
}

  • ¿Por qué tenemos que agregar const al final de la firma de la función?

    – puntas

    14/06/2013 a las 11:40

  • La función no cambia el objeto por lo que es const.

    – Kirill V. Lyadvinsky

    2 de julio de 2013 a las 8:35

  • Si ese es el caso, entonces por qué pasamos “const X& val”, asumo que pasar el valor como const a una función hace que la función piense que su valor no va a cambiar.

    -Prashant Bhanarkar

    22 de agosto de 2016 a las 6:47

  • @PrashantBhanarkar El const La palabra clave al final de la firma especifica que el operator() La función no cambia la instancia de la Xgreater struct (que en general podría tener variables miembro), mientras que indicar const para los valores de entrada solo especifica que esos valores de entrada son inmutables.

    – schester

    28 de diciembre de 2017 a las 19:35


1647626117 772 Ordenar un vector de objetos personalizados
Pixelquímico

ordenar tal 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

Dado que la mayoría de las técnicas, para obtener un ordenamiento relativo de X 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. Está ordenando rangos de X objetos una tarea común o rara (dichos rangos se ordenarán en varios lugares diferentes en el 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 consigo mismo?
  3. ¿Es el rendimiento un problema o debería ordenar los rangos de X los objetos sean infalibles?

Si ordena rangos de X es una tarea común y la clasificación lograda es de esperar (es decir, X simplemente envuelve un solo valor fundamental) entonces probablemente iría por sobrecarga operator< ya que permite la clasificación sin ningún tipo de confusión (como pasar correctamente los comparadores adecuados) y produce repetidamente los resultados esperados.

Si la clasificación es una tarea común o es probable que se requiera en diferentes contextos, pero hay varios criterios que se pueden usar para clasificar X objetos, iría por Functors (sobrecargado operator() funciones 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 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 al mirar una lambda que se aplica en el lugar mientras que operator< es opaco a primera vista y tendría que buscar la definición para saber qué lógica de ordenación se aplicará.

Tenga en cuenta, sin embargo, que un solo operator< La 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 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 (al menos cuando la optimización del tiempo de enlace/ no se aplica la generación de código).

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

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

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

Cualquier 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 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. Crea un bool operator()(T, T) sobrecarga para un tipo personalizado que se puede pasar como funtor 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 utilizar para ordenar cualquier tipo con miembro i secundario <.

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 habilita 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 del comparador ordinario 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));

1647626117 966 Ordenar un vector de objetos personalizados
xtofl

Estás en el camino correcto. std::sort utilizará operator< como función de comparación por defecto. Entonces, para ordenar sus objetos, tendrá que sobrecargar bool operator<( const T&, const T& ) o proporcione un objeto de función 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<C> values;

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

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

  • Perdí ese: proporcione un operador de función miembro <.

    – xtofl

    4 de septiembre de 2009 a las 17:13

  • es mejor hacer operator< un miembro de clase (o estructura), porque uno global podría usar miembros protegidos o privados. O deberías convertirlo en un amigo de la estructura C.

    – Kirill V. Lyadvinsky

    4 de septiembre de 2009 a las 17:25

1647626118 758 Ordenar un vector de objetos personalizados
chris reid

Tenía curiosidad por saber si hay algún impacto medible en el rendimiento entre las diversas formas en que uno puede llamar a std::sort, así que creé 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 ordenar la copia (y calcular una suma de verificación para evitar una eliminación demasiado vigorosa del código muerto).

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 genera una penalización de +30%.

También parece que la versión operator< 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- salida de temperatura).

  • Perdí ese: proporcione un operador de función miembro <.

    – xtofl

    4 de septiembre de 2009 a las 17:13

  • es mejor hacer operator< un miembro de clase (o estructura), porque uno global podría usar miembros protegidos o privados. O deberías convertirlo en un amigo de la estructura C.

    – Kirill V. Lyadvinsky

    4 de septiembre de 2009 a las 17:25

Ordenar un vector de objetos personalizados
mateusz budzisz

A continuación se muestra el código usando lambdas

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

¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad