¿Cómo clasifico un vector de pares basado en el segundo elemento del par?

Question

Si tengo un vector de pares:

std::vector<std::pair<int, int> > vec;

¿Existe una manera fácil de ordenar la lista en orden creciente según el segundo elemento del par?

Sé que puedo escribir un pequeño objeto de función que hará el trabajo, pero ¿hay alguna manera de usar partes existentes de STL y std :: less para hacer el trabajo directamente?

EDITAR: Entiendo que puedo escribir una función o clase separada para pasar al tercer argumento para ordenar. La pregunta es si puedo o no construirlo a partir de material estándar. Realmente tengo algo que se ve así:

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

Answer 1

EDITAR : usando c ++ 14, la mejor solución es muy fácil de escribir gracias a lambdas que ahora puede tener parámetros de tipo auto . Esta es mi solución favorita actual

std::sort(v.begin(), v.end(), [](auto &left, auto &right) {
    return left.second < right.second;
});

---

Simplemente use un comparador personalizado (es un tercer argumento opcional para std :: sort )

struct sort_pred {
    bool operator()(const std::pair<int,int> &left, const std::pair<int,int> &right) {
        return left.second < right.second;
    }
};

std::sort(v.begin(), v.end(), sort_pred());

Si está utilizando un compilador de C ++ 11, puede escribir lo mismo con lambdas:

std::sort(v.begin(), v.end(), [](const std::pair<int,int> &left, const std::pair<int,int> &right) {
    return left.second < right.second;
});

EDITAR : en respuesta a sus ediciones a su pregunta, aquí hay algunas ideas ... si realmente quieres ser creativo y poder reutilizar mucho este concepto, solo crea una plantilla:

template <class T1, class T2, class Pred = std::less<T2> >
struct sort_pair_second {
    bool operator()(const std::pair<T1,T2>&left, const std::pair<T1,T2>&right) {
        Pred p;
        return p(left.second, right.second);
    }
};

entonces también puedes hacer esto:

std::sort(v.begin(), v.end(), sort_pair_second<int, int>());

o incluso

std::sort(v.begin(), v.end(), sort_pair_second<int, int, std::greater<int> >());

Aunque para ser honesto, todo esto es un poco exagerado, simplemente escriba la función de 3 líneas y termine con ella :-P

Answer 2

Puedes usar boost así:

std::sort(a.begin(), a.end(), 
          boost::bind(&std::pair<int, int>::second, _1) <
          boost::bind(&std::pair<int, int>::second, _2));

No conozco una forma estándar de hacer esto igualmente breve y conciso, pero puedes tomar boost :: bind todo consiste en encabezados.

Answer 3

Con C ++ 0x podemos usar funciones lambda:

using namespace std;
vector<pair<int, int>> v;
        .
        .
sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) {
             return lhs.second < rhs.second; } );

En este ejemplo, el tipo de retorno bool se deduce implícitamente.

Tipos de retorno de Lambda

Cuando una función lambda tiene una sola declaración, y esta es una declaración de retorno, el compilador puede deducir el tipo de retorno. De C ++ 11, §5.1.2 / 4:

  

...

     

  
• Si la declaración compuesta tiene la forma {return expression; } el tipo de la expresión devuelta después de la conversión lvalue-to-rvalue (4.1), conversión de matriz a puntero (4.2) y conversión de función a puntero (4.3);
  
• de lo contrario, void .
  

Para especificar explícitamente el tipo de retorno, utilice el formulario [] () - > Escriba {} , como en:

sort(v.begin(), v.end(),
     [](const pair<int, int>& lhs, const pair<int, int>& rhs) -> bool {
             if (lhs.second == 0)
                 return true;
             return lhs.second < rhs.second; } );

Answer 4

Es bastante simple usa la función de clasificación del algoritmo y agrega su propia función de comparación

vector< pair<int,int > > v;
sort(v.begin(),v.end(),myComparison);

Ahora tienes que hacer la comparación basada en la segunda selección así que declara usted "myComparison" como

bool myComparison(const pair<int,int> &a,const pair<int,int> &b)
{
       return a.second<b.second;
}

Answer 5

Para algo reutilizable:

template<template <typename> class P = std::less >
struct compare_pair_second {
    template<class T1, class T2> bool operator()(const std::pair<T1, T2>& left, const std::pair<T1, T2>& right) {
        return P<T2>()(left.second, right.second);
    }
};

Puedes usarlo como

std::sort(foo.begin(), foo.end(), compare_pair_second<>());

o

std::sort(foo.begin(), foo.end(), compare_pair_second<std::less>());

Answer 6

Tendrías que confiar en un select2nd

Answer 7

Intente intercambiar los elementos de los pares para que pueda usar std :: sort () de manera normal.