How to Efficiently Sort a Vector of Pairs by Pair's Second Element

This article addresses the question of sorting a vector of pairs based on the second element of each pair in ascending order. While creating a custom function object for this task is a viable solution, there are alternative methods that utilize existing STL components and std::less.

Using std::sort with a Custom Comparator

One approach is to employ a custom comparator as an optional third argument to std::sort. This custom comparator, called sort_pred, is defined as follows:

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

To utilize this comparator, simply pass it to std::sort:

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

Using C 11 Lambdas

If using a C 11 compiler, you can leverage lambdas in place of a custom comparator:

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

Using a Generic Template for Pair Sorting

For greater flexibility and reusability, you can create a generic template called 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);
    }
};

With this template, you can achieve the desired sorting as follows:

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