c++ - resueltos - sumar las posiciones pares de un arreglo en java

¿Cómo ordeno 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 las partes existentes de STL y std::less para hacer el trabajo directamente?

EDITAR: entiendo que puedo escribir una función o clase por separado para pasar al tercer argumento para ordenar. La pregunta es si puedo construirlo fuera de lo estándar. Realmente tendría algo que se parece a:

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

Answer 1

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 Lambda

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

...

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

Para especificar explícitamente el tipo de devolución use el formulario []() -> Type { } , 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 2

Es bastante simple usar la función de ordenamiento del algoritmo y agregar su propia función de comparación

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

Ahora tiene que hacer la comparación basada en la segunda selección, así que declare "myComparison" como

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

Answer 3

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

Answer 4

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 5

Puede usar un impulso como este:

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 agarrar boost::bind , todo consiste en encabezados.

Answer 6

Tendría que confiar en un select2nd no estándar

Answer 7

EDITAR : utilizando 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;
});

Solo 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 C ++ 11, puede escribir lo mismo usando 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 modificaciones a su pregunta, he aquí algunos pensamientos ... si realmente quiere ser creativo y poder reutilizar mucho este concepto, solo haga 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 puedes hacer esto también:

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, esto es un poco exagerado, solo escribe la función de 3 líneas y termina con esto :-P