Use custom objects as keys to std::map in C++
This post will discuss how to use custom objects as keys to std::map in C++.
1. Defining less-than operator<
To use any object as a key in std::map, we have to tell the map how to compare the two objects using a comparison function in the third parameter of the std::map template. The default value of the third parameter is std::less, which delegates the comparison to operator< defined for the key type of the map.
So, we just need to define the less-than operator for the object to enable comparisons. To demonstrate, consider the following code which uses a Node object as key to std::map by defining operator<() as a member function for Node type.
|
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 32 33 34 35 36 37 38 39 |
#include <iostream> #include <map> template<typename T1, typename T2> struct Node { T1 x; T2 y; // constructor Node(T1 x, T2 y): x(x), y(y) {} // overload `<` operator to use a `Node` object as a key in a `std::map` // It returns true if the current object appears before the specified object bool operator<(const Node &ob) const { return x < ob.x || (x == ob.x && y < ob.y); } }; int main() { std::map<Node<std::string, std::string>, int> map = { {{"C", "C99"}, 1999}, {{"C", "C11"}, 2011}, {{"C++", "C++14"}, 2014}, {{"C++", "C++17"}, 2017}, {{"Java", "Java SE 8"}, 2014}, {{"Java", "Java SE 9"}, 2017} }; for (const auto &entry: map) { auto key = entry.first; std::cout << "{" << key.x << "," << key.y << "}, " << entry.second << std::endl; } return 0; } |
Output:
{C,C11}, 2011
{C,C99}, 1999
{C++,C++14}, 2014
{C++,C++17}, 2017
{Java,Java SE 8}, 2014
{Java,Java SE 9}, 2017
Note that the ordered associative containers only use a strict weak order to identify their keys. Two keys x and y are equivalent if !(x < y) && !(y < x) returns true, i.e., neither x is smaller than y nor y is smaller than x. So operator< is used to detect equality, and there is no need to overload the operator==.
2. Using a comparison object
We can even avoid defining the operator< for an object type by passing a comparator function object as a third template parameter to std::map, as shown below:
|
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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <iostream> #include <map> template<typename T1, typename T2> struct Node { T1 x; T2 y; Node(T1 x, T2 y): x(x), y(y) {} }; struct comp { template<typename T> bool operator()(const T &lhs, const T &rhs) const { if (lhs.x == rhs.x) { return lhs.y > rhs.y; } return lhs.x < rhs.x; } }; int main() { std::map<Node<std::string, std::string>, int, comp> map = { {{"C", "C99"}, 1999}, {{"C", "C11"}, 2011}, {{"C++", "C++14"}, 2014}, {{"C++", "C++17"}, 2017}, {{"Java", "Java SE 8"}, 2014}, {{"Java", "Java SE 9"}, 2017} }; for (const auto &entry: map) { auto key = entry.first; std::cout << "{" << key.x << "," << key.y << "}, " << entry.second << std::endl; } return 0; } |
Output:
{C,C99}, 1999
{C,C11}, 2011
{C++,C++17}, 2017
{C++,C++14}, 2014
{Java,Java SE 9}, 2017
{Java,Java SE 8}, 2014
3. By specializing std::less function
Instead of passing the comparator function object to std::map, we can specialize std::less in the std namespace to override the ordering.
|
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 32 33 34 35 36 37 38 39 40 41 42 43 |
#include <iostream> #include <map> template<typename T1, typename T2> struct Node { T1 x; T2 y; Node(T1 x, T2 y): x(x), y(y) {} }; namespace std { template<typename T1, typename T2> struct less<Node<T1, T2>> { bool operator()(const Node<T1, T2> &lhs, const Node<T1, T2> &rhs) const { return lhs.x < rhs.x || (lhs.x == rhs.x && lhs.y > rhs.y); } }; } int main() { std::map<Node<std::string, std::string>, int> map = { {{"C", "C99"}, 1999}, {{"C", "C11"}, 2011}, {{"C++", "C++14"}, 2014}, {{"C++", "C++17"}, 2017}, {{"Java", "Java SE 8"}, 2014}, {{"Java", "Java SE 9"}, 2017} }; for (const auto &entry: map) { auto key = entry.first; std::cout << "{" << key.x << "," << key.y << "}, " << entry.second << std::endl; } return 0; } |
Output:
{C,C99}, 1999
{C,C11}, 2011
{C++,C++17}, 2017
{C++,C++14}, 2014
{Java,Java SE 9}, 2017
{Java,Java SE 8}, 2014
That’s all about using custom objects as keys to std::map in C++.
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 :)