Ordenar un vector de objetos personalizados
¿Cómo se puede ordenar un vector que contiene objetos personalizados (es decir, definidos por el usuario)?
Probablemente, se debería utilizar el algoritmo STL estándar 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.
¿Estoy en el camino correcto?
Un ejemplo simple usandostd::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 operator<for 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 puedes simplemente 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 un poco la llamada de ordenación:
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>());
En aras de la cobertura. Propongo 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ías usar functor como tercer argumento de std::sorto podrías definirlo 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() );
}
La clasificación de tal vectoro cualquier otro rango aplicable (iterador de entrada mutable) de objetos personalizados de tipo Xse puede lograr utilizando varios métodos, incluido especialmente el uso de algoritmos de biblioteca estándar como
sort,stable_sort,partial_sortopartial_sort_copy.
Dado que la mayoría de las técnicas para obtener el orden relativo de Xlos elementos ya se han publicado, comenzaré con algunas notas sobre "por qué" y "cuándo" utilizar los distintos enfoques.
El "mejor" enfoque dependerá de diferentes factores:
- ¿Es la clasificación de rangos de
Xobjetos una tarea común o poco común (se ordenarán dichos rangos en varios lugares diferentes del programa o por parte de los usuarios de la biblioteca)? - ¿La clasificación requerida es "natural" (esperada) o hay varias formas en que se puede comparar el tipo consigo mismo?
- ¿Es el rendimiento un problema o la clasificación de rangos de
Xobjetos debería ser infalible?
Si ordenar rangos de Xes una tarea común y se espera la clasificación lograda (es decir, Xsimplemente envuelve un único valor fundamental), entonces probablemente se sobrecargaría, operator<ya que permite la clasificación sin ninguna confusión (como pasar correctamente los comparadores adecuados) y repetidamente produce los resultados esperados. resultados.
Si ordenar es una tarea común o es probable que sea necesaria en diferentes contextos, pero existen múltiples criterios que se pueden usar para ordenar Xobjetos, elegiría Functores ( operator()funciones sobrecargadas de clases personalizadas) o punteros de función (es decir, un functor/función para el orden léxico y otro para el orden natural).
Si ordenar rangos de tipos Xes 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 orden al observar una lambda que se aplica en el lugar, aunque operator<es opaca a primera vista y tendría que buscar la definición para saber qué lógica de orden se aplicará.
Sin embargo, tenga en cuenta que una única operator<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 incorporar la lógica de clasificación, lo que podría ser un grave inconveniente (al menos cuando no se aplica la optimización del tiempo de enlace/generación de código).
Formas de lograr la 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)utilice plantillas de biblioteca estándar que no esperan 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 pueda pasarse 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 de forma un poco más genérica 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 isoporte de miembro <.
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 sencilla:
// 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::sortse utilizará operator<como función de comparación de forma predeterminada. Entonces, para ordenar tus objetos, tendrás que sobrecargar bool operator<( const T&, const T& )o proporcionar 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.
