cómo ordenar eficientemente un vector de pares por el segundo elemento de par

Este artículo aborda la cuestión de clasificar un vector de pares basados ​​en el Segundo elemento de cada par en orden ascendente. Si bien crear un objeto de función personalizado para esta tarea es una solución viable, existen métodos alternativos que utilizan componentes STL existentes y std :: menos.

usando std :: sorte con un comparador personalizado

Un enfoque es emplear un comparador personalizado como un tercer argumento opcional para std :: sort. Este comparador personalizado, llamado sort_pred, se define como sigue:

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

para utilizar este comparador, simplemente pasarlo a std :: sort:

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

usando C 11 lambdas

Si usa un compilador C 11, puede apalancamiento lambdas en lugar de un comparador personalizado:

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

usando una plantilla genérica para la clasificación de pares

para una mayor flexibilidad y reutilización, puede crear una plantilla genérica llamada sort_pair_second:

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

con esta plantilla, puede lograr la clasificación deseada de la siguiente manera:

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