How to Sort a Vector of Pairs Based on the Second Element of the Pair

How do I sort a vector of pairs based on the second element of the pair?

EDIT: using c++14, the best solution is very easy to write thanks to lambdas that can now have parameters of type auto. This is my current favorite solution

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

---

ORIGINAL ANSWER:

Just use a custom comparator (it's an optional 3rd argument to 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());

If you're using a C++11 compiler, you can write the same using lambdas:

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

EDIT: in response to your edits to your question, here's some thoughts ...
if you really wanna be creative and be able to reuse this concept a lot, just make a template:

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

then you can do this too:

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

or even

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

Though to be honest, this is all a bit overkill, just write the 3 line function and be done with it :-P

How do I sort a vector of pairs based on both first and second element in a pair?

You can simply use the std::sort to sort it in ascending order

std::vector<std::pair<int, int>> arr;
arr.push_back({ 4, 5 });
arr.push_back({ 3, 7 });
arr.push_back({ 10, 5 });
arr.push_back({ 5, 7 });
arr.push_back({ 1, 5 });
std::sort(arr.begin(), arr.end());

In addition you can sort in descending order using std::greater<>()

std::sort(arr.begin(), arr.end(), std::greater<>());

After Edit: If your question is to sort by second element than if the second element are equal to sort by the first element than this might a solution

(it in ascending order)

bool sortBySecondElement(const std::pair<int, int>& p1, const std::pair<int, int> & p2)
{
    return p1.second < p2.second;
}

bool sortByFirstElement(const std::pair<int, int>& p1, const std::pair<int, int>& p2)
{
    return p1.second == p2.second && p1.first < p2.first;
}

int main()
{
    std::vector<std::pair<int, int>> arr;
    arr.push_back({ 4, 5 });
    arr.push_back({ 3, 7 });
    arr.push_back({ 10, 5 });
    arr.push_back({ 5, 7 });
    arr.push_back({ 1, 5 });
    std::sort(arr.begin(), arr.end(), sortBySecondElement);
    std::sort(arr.begin(), arr.end(), sortByFirstElement);
}

How do I sort a vector of pairs by both of the values rather than just the second one?

The simplest way is to use the standard functions std::sort() and std::tie().

Here is a demonstration program:

#include <iostream>
#include <utility>
#include <vector>
#include <iterator>
#include <algorithm>

int main()
{
    std::vector<std::pair<int, double>> v =
    {
        {  2, 2.4 },
        {  9, 3.0 },
        { 10, 3.1 },
        {  1, 2.4 },
        {  5, 3.1 }
    };

    std::sort( std::begin( v ), std::end( v ),
               []( const auto &p1, const auto &p2 )
               {
                   return std::tie( p2.second, p1.first ) < std::tie( p1.second, p2.first );
               } );

    for (const auto &p : v)
    {
        std::cout << p.first << ' ' << p.second << '\n';
    }
}

The program output is:

5 3.1
10 3.1
9 3
1 2.4
2 2.4

How can I sort a pair of vector in some given range?

What you need is something like the following

#include <tuple>
#include <vector>
#include <iterator>
#include <algorithm>

//...

std::sort( std::begin( v ), std::end( v ),
           []( const auto &p1, const auto &p2 )
           {
               return std::tie( p2.second, p1.first ) < std::tie( p1.second, p2.first );
           } ); 

Here is a demonstration program.

#include <iostream>
#include <tuple>
#include <vector>
#include <iterator>
#include <algorithm>

int main() 
{
    std::vector<std::pair<long long, long long>> v =
    {
        {1,6} , {4,5}, {3,5}, {8,5}, {1,1}
    };
    
    std::sort( std::begin( v ), std::end( v ),
               []( const auto &p1, const auto &p2 )
               {
                    return std::tie( p2.second, p1.first ) <
                           std::tie( p1.second, p2.first );
               } );
               
    for ( const auto &p : v )
    {
        std::cout << "{ " << p.first << ", " << p.second << " } ";
    }
    
    std::cout << '\n';
    
               
    return 0;
}

The program output is

{ 1, 6 } { 3, 5 } { 4, 5 } { 8, 5 } { 1, 1 }  

How can i sort a pair of array of vectors v[ ]by second element

You will need to pass the comparing function as the third parameter to the sort function. Like you mentioned your vector is something of the form:

 {V[x].push_back(make_pair(y,w));}

Then the comparing function will look like:

bool greaterThan( pair<int,int> lx, pair<int,int> rx ){
    return lx.second < rx.second; //change here for different criterias
}

//used as
sort(V[x].begin(), V[x].end(), greaterThan);

Sort a vector of pairs by first element then by second element of the pair in C

There are several answers already, but their implementation seems to be too complicated ;)

struct pair
{
    int x;
    int y;
};

static inline int safe_cmp(int x, int y)
{
    return (x > y) - (x < y);
}

int lex_cmp_pairs(const void *left, const void *right)
{
    const struct pair *l = left;
    const struct pair *r = right;
    const int cmp_x = safe_cmp(l->x, r->x);
    const int cmp_y = safe_cmp(l->y, r->y);
    return (cmp_x == 0) ? cmp_y : cmp_x;
}

/* example usage: */
struct pair ps[] = { {3, 3}, {2, 5}, {1, 1}, {2, 2}, {1, 2}, {3, 1} };
qsort(ps, 6, sizeof(struct pair), lex_cmp_pairs);

Please note, that you probably want to use qsort_r (GNU extension) if you're intending to sort in threaded environment.

STXXL: How to sort Vector of pairs on second element?

Got the following example in STXXL:Sorter Section which addresses the same problem.

Code:

#include <stxxl/sorter>
#include <stxxl/stats>
#include <stxxl/timer>
#include <stxxl/random>
#include <limits>
struct TwoInteger
{
    int i, j;
    TwoInteger()
    { }
    TwoInteger(int _i, int _j)
        : i(_i), j(_j)
    { }
};
struct TwoIntegerComparator
{
    bool operator () (const TwoInteger& a, const TwoInteger& b) const
    {
        return a.i < b.i;
    }
    TwoInteger min_value() const
    {
        return TwoInteger(std::numeric_limits<int>::min(), std::numeric_limits<int>::min());
    }
    TwoInteger max_value() const
    {
        return TwoInteger(std::numeric_limits<int>::max(), std::numeric_limits<int>::max());
    }
};
int main()
{
    // template parameter <ValueType, CompareType, BlockSize(optional), AllocStr(optional)>
    typedef stxxl::sorter<TwoInteger, TwoIntegerComparator, 1*1024*1024> sorter_type;
    // create sorter object (CompareType(), MainMemoryLimit)
    sorter_type int_sorter(TwoIntegerComparator(), 64 * 1024 * 1024);
    stxxl::random_number32 rand32;
    stxxl::timer Timer1;
    Timer1.start();
    // insert random numbers from [0,100000)
    for (size_t i = 0; i < 1000; ++i)
    {
        int_sorter.push(TwoInteger(rand32() % 100000, (int)i));    // fill sorter container
    }
    Timer1.stop();
    STXXL_MSG("push time: " << (Timer1.mseconds() / 1000));
    stxxl::timer Timer2;
    Timer2.start();
    int_sorter.sort();  // switch to output state and sort
    Timer2.stop();
    STXXL_MSG("sort time: " << (Timer2.mseconds() / 1000));
    // echo sorted elements
    while (!int_sorter.empty())
    {
        std::cout << int_sorter->i << " ";  // access value
        ++int_sorter;
    }
    return 0;
}

Sort a vector of pairs by first element then by second element of the pair in C++?

pairs by default compare by first element, then second. So, if you don't care about preserving the order when the first elements compare equal, then you can just use std::sort:

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

---

Related Topics