C++ Named Requirements: Compare
Introduction
Given two values $a$ and $b$, by comparing their values, there could be one of the three ordering relationships between them, equal, i.e., the order of $a$ and $b$ cannot be determined from their values, $a$ strictly appears before $b$, and $b$ strictly appears before $a$. It appears that we would have to define two functions, $\text{equal}(x, y)$ which tells us whether $x$ is equal to $y$ and $\text{comp}(x, y)$ which tells us whether $x$ strictly appears before $y$, in order to explicitly determine which of the three ordering relationship the two values $a$ and $b$ belong to.
Close examination reveals that we can define $\text{equal}(x, y)$ using $\text{comp}(x, y)$ and boolean relationships $\text{and}$ and $\text{not}$, since the three ordering relationships are mutually exclusive. Concretely,
$$
\text{equal}(x, y) \triangleq \left(\text{not} \ \text{comp}\left(x, y\right)\right) \ \text{and} \ \left(\text{not} \ \text{comp}\left(y, x\right)\right)
$$
In fact, in C++ STL, most containers take one single compare function that can be used for determining the ordering relationship. In this blog post, I would like to quickly discuss the caveats of compare functions in C++.
Caveats
The compare in C++ really means whether the first argument of the call appears before the second in the strict weak ordering relation induced by this type.
Many C++ STL containers are ordered containers, such as std::set, std::map, std::multiset, std::multimap. They take one compare function in the constructors. For example, the default compare function is std::less, which means by default, when we iterate from the beginning to the end of the sequence, the values in the sequence are in ascending order.
Now, what if we want to reverse the order of the values in the sequence? In our case, we want to have a descending-ordered sequence for those STL containers. Should we use std::greater_equal for the compare function in the constructor? The answer is no. std::greater_equal is not a compare function, because it does not follow the strict weak ordering relationship property. The consequence of using non-compare functions for ordered STL containers is that determining whether the two values are equal will not work as expected. For example, testing equivalence in the STL container using std::greater_equal will be
$$
\begin{align}
\text{equal}(8, 8) &= \left(\text{not} \ \text{geq}\left(8, 8\right)\right) \ \text{and} \ \left(\text{not} \ \text{geq}\left(8, 8\right)\right) \\
&= \left(\text{not} \ \text{true} \right) \ \text{and} \ \left(\text{not} \ \text{true} \right) \\
&= \text{false} \ \text{and} \ \text{false} \\
&= \text{false} \\
\end{align}
$$
which is incorrect.
The correct compare function to use to reverse the order of the values in the sequence will be using std::greater instead of std::greater_equal.
Conclusions
Always have compare functions return false for equal values.
References
C++ Named Requirements: Compare