If you have ever tried to use a custom class as a key of std::map, most probably you got a compilation error. This article explains why this happens and shows how to make custom classes work as keys of std::map by providing a sorting rule. The article demonstrates three different ways in which you can provide the sorting rule, namely via operator overloading, a comparator (C++98) or with help of a lambda expression (C++11 only).
The reason why we have to provide a sorting rule for user-defined classes as keys is because std::map is a binary search tree data structure. This video shows how binary search trees work in general . Binary search trees store their data in sorted order, thus we have to provide a sorting rule. Once we provided the sorting rule, the map can make use of binary search for all its operations. A binary tree structure for a map of size 6 can be seen below:
A basic example of a binary search can be a guessing game in which one of the players thinks of a number in a certain range (e.g. 0 - 24) and the other player tries to guess it. In binary search, the second player always guesses the middle element (i.e. 12) and the first player informs him whether this is larger, smaller or equal to the value that he thought of. Every time, the player makes a guess, one half of the array gets eliminated. The search is repeated until the second player guesses the correct number. The number of times we need to do this is log2(N) because each comparison throws out half of the possibilities.
Problem definition
Imagine we have a class called Color represented by three private attributes red, green and blue and we would like to use this class as a key of std::map. The class can be seen below. Notice that I also overloaded operator<<, this has nothing to do with our problem, it is there just so that we can print the Color directly with std::cout.
class Color{
public:
Color();
Color(int r, int g, int b);
int red() const {return m_red;}
int green() const {return m_green;}
int blue() const {return m_blue;}
bool areValid() const;
private:
int m_red;
int m_green;
int m_blue;
};
std::ostream& operator<<(std::ostream &output, const Color &c);
Let's look at the main.cpp below. We construct a map in which we use our class Color as a key and an int as a value. We insert
a couple of pairs (Color, int) and try to print the elements of the map.
If we try to compile the code above, it won't compile and produces the following error: no match for 'operator<' in '__x < __y'. This is because we did not provide a rule to sort the elements which are needed by the binary search tree. How do we solve this? The following lines show how to solve the problem.
Overloading the operator< (C++98)
The first possible solution to our problem is overloading operator<. This is highlighted in the code below. The overloaded operator< takes references to two color instances as arguments and returns true or false based on our sorting rule which will appear in the body of the method. Notice that the only thing we need to do is to provide a rule according to which to compare two color objects. This is sufficient for the std::map to achieve sorted order.
class Color{
public:
Color();
Color(int r, int g, int b);
int red() const {return m_red;}
int green() const {return m_green;}
int blue() const {return m_blue;}
bool areValid() const;
private:
int m_red;
int m_green;
int m_blue;
};
std::ostream& operator<<(std::ostream &output, const Color &c);
bool operator<(const Color &c1, const Color &c2);
Now let's look at the body of the overloaded operator from color.cpp (the entire source files can be found above). How do we decide which color is "smaller"? This depends on our intentions. If we only require that our custom class works with std::map, we should provide something simple and logical. We might choose to sort colors according to their lightness which is in its simplest case an average of red, green and blue. Thus, the operator< will return true if the average of R, G, and B of the left-hand color is smaller than the average of R, G, and B of the right-hand color. This can be seen below
bool operator<(const Color &c1, const Color &c2){
return c1.red() + c1.green() + c1.blue() <
c2.red() + c2.green() + c2.blue();
}
Note: The basic formula for color lightness is an average of R, G and B, i.e. (R + G + B) / 3. Notice that we omitted the division by 3 in the code above, that is because when comparing two colors the division by 3 simply disappears from the equation.
Note: The code compiles and produces the following output: You can see that the colors are sorted in ascending order according to the sum of their R,G and B values.
only because we also overloaded the output operator<<. The details of this can be found in the source files above.
User-defined comparator (C++98)
Another way of providing the sorting rule is with the help of a custom comparator. A custom comparator is a function object and a function object is simply a class that defines operator() and as a result, can be called as if it was a function. You can see our version of the class below. Notice that the parameters, return type as well as the body of the function are the same as in the first solution.
class Color{
public:
Color();
Color(int r, int g, int b);
int red() const {return m_red;}
int green() const {return m_green;}
int blue() const {return m_blue;}
bool areValid() const;
private:
int m_red;
int m_green;
int m_blue;
};
std::ostream& operator<<(std::ostream &output, const Color &c);
class Comparator {
public:
bool operator()(const Color& c1, const Color& c2){
return c1.red() + c1.green() + c1.blue() <
c2.red() + c2.green() + c2.blue();
}
};
To use the comparator, notice that we passed an extra argument to the map. The rest of the code remains the same.
C++11 provides another solution to the same problem, namely a lambda expression.
A lambda expression is a syntactic shortcut for a function object, i.e. an object that can be called as if it was a function. The basic syntax of the lambda expression can be seen below:
The lambda expression for our problem can be seen below. Our lambda expression has no captures, takes two parameters and returns a bool. The body of the expression also remains the same as in the previous solutions.
Notice that to use the lambda expression with our map we have to use decltype. The decltype() is here because we cannot use lambda in unevaluated context. We firstly have to define lambda with 'auto' elsewhere and then only use it in the map's parameters with decltype(). If we did not do this, we would get a compilation error that would look like this: type/value mismatch at argument 3 in template parameter list for 'template<class _Key, class _Tp, class _Compare, class _Alloc> class std::map'.
