How to Sort a Vector of Pairs in C++
-
Use the
std::sortAlgorithm to Sort Vector of Pairs by First Element Values in C++ -
Use the
std::sortAlgorithm With Lambda Expression to Sort Vector of Pairs by Second Element Values in C++ -
Use the
std::sortAlgorithm With a Custom Function to Sort Vector of Pairs in C++
This article will explain how to sort a vector of pairs in C++.
Use the std::sort Algorithm to Sort Vector of Pairs by First Element Values in C++
Pairs are provided as a separate class in the C++ standard template library. It implements a type for storing two heterogeneous objects as a single unit. The std::pair algorithm is essentially a tuple-like data structure with only two elements.
A pair object is declared with two template parameters that specify the type of each element. We can declare a vector of pair objects by placing the pair declaration as a vector template parameter. A vector of pairs can be initialized with an initializer list by passing each pair with separate braces, as demonstrated in the following code snippet.
We can sort the vector of pairs using the generic sorting algorithm provided by STL. The std::sort function takes two iterators of the range to be sorted, and it rearranges the elements in non-descending order by default. In the case of pairs, the vector is sorted by the first element of each pair.
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end());
cout << "vec1: ";
printVector(vec1);
return EXIT_SUCCESS;
}
Output:
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {6,six}; {12,eleven}; {32,thirty-two}; {43,forty-three};
Use the std::sort Algorithm With Lambda Expression to Sort Vector of Pairs by Second Element Values in C++
Alternatively, we can sort the given vector of pairs by the second element values if we pass an optional comparison function object to the std::sort algorithm. In this case, we utilize a lambda expression to form a function object and pass it as the third argument of the sort function call. Note that this essentially is the method to define any custom comparison routine for the elements of the pair.
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end(),
[](const auto &x, const auto &y) { return x.second < y.second; });
cout << "vec1: ";
printVector(vec1);
cout << endl;
return EXIT_SUCCESS;
}
Output:
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {12,eleven}; {43,forty-three}; {6,six}; {32,thirty-two};
Use the std::sort Algorithm With a Custom Function to Sort Vector of Pairs in C++
Another method to pass a comparison function to the std::sort algorithm is to define a separate function in the form of bool cmp(const Type1 &a, const Type2 &b). Generally, std::sort has O(nlogn) running time complexity.
The following example defines a sortPairs function that compares the first elements in each pair. Although, you may define a more complex comparison function for the pairs that store custom class objects or when multiple data members must be evaluated.
#include <iostream>
#include <vector>
using std::cin;
using std::cout;
using std::endl;
using std::pair;
using std::string;
using std::vector;
template <typename T>
void printVector(vector<T> &vec) {
for (const auto &item : vec) {
cout << "{" << item.first << "," << item.second << "}"
<< "; ";
}
cout << endl;
}
bool sortPairs(const pair<int, string> &x, const pair<int, string> &y) {
return x.first > y.first;
}
int main() {
vector<pair<int, string>> vec1 = {
{12, "eleven"}, {32, "thirty-two"}, {6, "six"}, {43, "forty-three"}};
cout << "vec1: ";
printVector(vec1);
std::sort(vec1.begin(), vec1.end(), sortPairs);
cout << "vec1: ";
printVector(vec1);
cout << endl;
return EXIT_SUCCESS;
}
Output:
vec1: {12,eleven}; {32,thirty-two}; {6,six}; {43,forty-three};
vec1: {43,forty-three}; {32,thirty-two}; {12,eleven}; {6,six};
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook