# 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