Use std::pair as a key in std::set in C++
This post will discuss how to use std::pair as a key in a std::set in C++ with and without the comparison object.
1. Using default order
We can use std::pair as a key in std::set, which is defined in the <utility> header. The pair class couples together a pair of values of the same or different types, and the individual values can be accessed through its public members first and second.
We can use initializer list in C++11 to initialize a std::set with std::pair as the key. The idea is to use the std::make_pair() or {} to construct a pair object.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
#include <iostream> #include <set> #include <utility> int main() { std::set<std::pair<std::string, int>> set = { {"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3} }; for (auto const &p: set) { std::cout << p.first << " " << p.second << std::endl; } return 0; } |
Output:
{A:0}
{A:4}
{B:3}
{B:4}
{C:1}
Since operator< is defined for pairs, std::set performs a lexicographical comparison on two pair objects to define an ordering, i.e., It will compare based on the first element. If the values of the first elements are equal, it will then compare based on the second element. They behave as if defined as:
|
1 2 3 4 |
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); } |
2. Using comparison object
We can also pass a comparison object to std::set to override the default order. The comparison object is a binary predicate which can take two pair objects and defines the custom order by comparing the first and second element of both pairs. If the predicate returns true, the first pair appears before the second pair, and if the predicate returns false, the first pair appears after the second pair.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
#include <iostream> #include <set> #include <utility> struct comp { template<typename T> bool operator()(const T &l, const T &r) const { if (l.first == r.first) { return l.second > r.second; } return l.first < r.first; } }; int main() { std::set<std::pair<std::string, int>, comp> set = { {"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3} }; for (auto const &p: set) { std::cout << "{" << p.first << ":" << p.second << "}\n"; } return 0; } |
Output:
{A:4}
{A:0}
{B:4}
{B:3}
{C:1}
3. Specializing std::less function
If you do not want to pass the comparison object but still want to override the default order, we can do that by specializing std::less in the std namespace. This works as the default for the second template parameter of std::set is std::less, which will delegate to operator<.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <iostream> #include <set> #include <utility> namespace std { template<typename T1, typename T2> struct less<std::pair<T1, T2>> { bool operator()(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) const { if (l.first == r.first) { return l.second > r.second; } return l.first < r.first; } }; } int main() { std::set<std::pair<std::string, int>> set = { {"A", 4}, {"B", 4}, {"C", 1}, {"A", 0}, {"B", 3} }; for (auto const &p: set) { std::cout << "{" << p.first << ":" << p.second << "}\n"; } return 0; } |
Output:
{A:4}
{A:0}
{B:4}
{B:3}
{C:1}
That’s all about using std::pair as a key in std::set in C++.
Also See:
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)