Sort a vector of pairs in C++

This post will discuss how to sort a vector of pairs in C++.

1. Default comparator of pair

The recommended approach uses the standard algorithm std::sort defined in the <algorithm> header. It takes the iterators to the initial and final positions of the vector, and sorts pairs in increasing order of their first value using std::less<> which will delegate the call to operator< or in decreasing order of their first value using std::greater<> which will delegate the call to operator>.

#include <iostream>

#include <utility>

#include <vector>

#include <algorithm>

typedef std::pair<int, int> pair;

int main()

{

std::vector<pair> v = { { 1, 2 }, { 6, 4 }, { 3, 4 }, { 6, 1 } };

// sorts pairs in increasing order of their first value

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

// sorts pairs in decreasing order of their first value

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

for (const pair &p: v) {

std::cout << '{' << p.first << ',' << p.second << '}' << std::endl;

}

return 0;

}

Download Run Code

Output:

{1,2}
{3,4}
{6,1}
{6,4}

This works as less-than, and greater-than operators are already defined for the pair class. Notice that if the first value of two pairs is equal, they will be compared based on their second value.

template <class T1, class T2>

bool operator<(const pair<T1, T2> &x, const pair<T1, T2> &y) {

return x.first < y.first || (!(y.first < x.first) && x.second < y.second);

}

template <class T1, class T2>

bool operator>(const pair<T1, T2> &x, const pair<T1, T2> &y) {

return y < x;

}

2. Using Custom Comparator

If you don’t want to use the default order, you can write your own comparator and pass it to the std::sort function. A comparator takes two pair objects and returns a bool indicating whether to put the first value before the second value. A comparator can be a binary function, an instance of a class with operator() overload (a functor), or even an anonymous closure (lambda). Lets demonstrates these:

1. Lambda expressions (C++11 and above)

#include <iostream>

#include <utility>

#include <vector>

#include <algorithm>

typedef std::pair<int, int> pair;

int main()

{

std::vector<pair> v = { { 1, 2 }, { 6, 4 }, { 3, 4 }, { 4, 1 } };

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

[](const pair &x, const pair &y) {

// compare the second value

if (x.second != y.second) {

return x.second < y.second;

}

// compare first only if the second value is equal

return x.first < y.first;

});

for (const pair &p: v) {

std::cout << '{' << p.first << ',' << p.second << '}' << std::endl;

}

return 0;

}

Download Run Code

Output:

{4,1}
{1,2}
{3,4}
{6,4}

2. Passing object of a class implementing `()` operator

#include <iostream>

#include <utility>

#include <vector>

#include <algorithm>

typedef std::pair<int, int> pair;

struct comp {

bool operator()(const pair &x, const pair &y) const {

if (x.second != y.second) {

return x.second < y.second;

}

return x.first < y.first;

}

};

int main()

{

std::vector<pair> v = { { 1, 2 }, { 6, 4 }, { 3, 4 }, { 4, 1 } };

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

for (const pair &p: v) {

std::cout << '{' << p.first << ',' << p.second << '}' << std::endl;

}

return 0;

}

Download Run Code

Output:

{4,1}
{1,2}
{3,4}
{6,4}

3. Using binary function

#include <iostream>

#include <utility>

#include <vector>

#include <algorithm>

typedef std::pair<int, int> pair;

bool fn(const pair &x, const pair &y)

{

if (x.second != y.second) {

return x.second < y.second;

}

return x.first < y.first;

}

int main()

{

std::vector<pair> v = { { 1, 2 }, { 6, 4 }, { 3, 4 }, { 4, 1 } };

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

for (const pair &p: v) {

std::cout << '{' << p.first << ',' << p.second << '}' << std::endl;

}

return 0;

}

Download Run Code

Output:

{4,1}
{1,2}
{3,4}
{6,4}

That’s all about sorting a vector of pairs in C++.

Sort a vector of pairs in C++

1. Default comparator of pair

2. Using Custom Comparator

1. Lambda expressions (C++11 and above)

2. Passing object of a class implementing () operator

3. Using binary function

Share this:

2. Passing object of a class implementing `()` operator