On operator<

Today I want to share with you a more philosophical issue I face with how the meaning of operator< is overloaded in C++. This could cause subtle bugs in programs.

What do you need operator< for? One thing you can do with it is to compare if a number exceeds some threshold:

bool exceeds(double x, double threshold)
{
  return threshold < x;
}

In addition to this obvious goal, STL decided to use operator< for a default order in ordered containers and binary search algorithms. This makes types with natural total ordering — like int, double, my::BigInt, my::Decimal — work out of the box. But now, if we want std::string to work out of the box with STL components that require a default total order, you have to define operator< for strings. And so it is the case. It was possible to come up with the fairly uncontroversial default total order for strings: the lexicographical order; but using operator< to indicate a lexicographical order is a bit of an abuse, and might confuse some. You cannot use such operator< to check if a string exceeds a threshold:

bool exceeds(string x, string threshold)
{
  return threshold < x;
}

What does it mean that "cat" exceeds "baby"?

Do you agree with my concern? You do not have to. You can say that the right way to look at it is to accept that in C++ operator< indicates a default total ordering which in case of scalar types can be the ordering of quantities in the mathematical sense, and for the other types, where applicable, it uses the lexicographical order. This is the case for std::tuple. In this view, the goal of operator< is for its type to be usable in STL ordered containers and binary search algorithms. It just has to be any well-defined total order.

But if it were to be the case, STL should also define operator< for complex<double>. In mathematics you cannot say that one complex number is less than another complex number; but in C++ you could use lexicographical comparison: first by real part, second by imaginary part. It would work with std::map. Yet, STL does not do it. Hardly surprising; trying to compare two complex numbers ‘manually’ is likely an error — you probably meant something else.

bool exceeds(complex<double> x, complex<double> threshold)
{
  return threshold < x;
}

What does it mean for a complex number to exceed a complex threshold?

We have a similar issue with boost::optional<T> and std::experimental::optional<T>: they have defined operator< with semantics similar to a lexicographical ordering: the null state is treated as a value less than any other value of T. This makes optional usable with ordered containers, but adds some confusion:

bool exceeds(optional<double> x, optional<double> threshold)
{
  return threshold < x;
}

What does it mean for a potentially non-existent number to exceed a potentially non-existent threshold. If x is non-existent, does it exceed the threshold? Worse still, in the case of optional a mixed comparison is possible:

optional<double> limit = read_limit();
double x = read_x();
return x < limit;

Do you know what the intent of the above code is? Does it contain a bug? Was it supposed to mean:

if (limit)
  return x < *limit;
else
  throw InsufficientInput();

or

return limit && x < *limit;

or

return !limit || x < *limit;

Who knows? Did the author know how the mixed comparison behaves, or was it an overlook? Does even the author know what his code is really doing?

An alternative solution

So, let’s try to see if we could remove the potential pitfalls as described above while still keeping the STL generic and simple.

This is how I see the situation. Some types, mostly representing mathematical numbers, have a relation “less than” whose intuitive meaning can be used in context like exceeding a threshold. There are lots of types that do not come with this “less than” relation, but which have a default total ordering relation. Relation “less than” if it exists for a given type is at the same time a good default total order relation. STL needs a total order relation for types, so that the end users can just type std::set<T> and should not be bothered with providing the relation manually.

If we were designing STL from scratch. This is what we could do. Define operator< only for types where its semantics are unambiguous and obvious: where term “exceeds threshold” makes sense — this is called a natyural total order. Do not define operator< for other types, like std::string, std::vector, str::tuple, boost::optional. Have std::set, std::map and binary-search algorithms use std::order instead of std::less. std::order does not exist today, but we could add it. For types with operator< (like int, double, BigInt), it would use the operator. For other types, that are not numbers, but for which a default total order can be defined (like std::string, std::vector, str::tuple, boost::optional, std::complex) it would use this order. std::order would be specialized for these types. If you are defining your own type and want it to be usable with std::set, you either have to define operator< (if it makes sense) or specialize std::order.

Requiring the users to specialize std::order is one option. Another would be to have them define a binary predicate called, say, ordered for their types. Then, the presence of this predicate could be checked when determining what default ordering to apply in std::set. This is how STL is using swap. But that’s not the point.

The point is, we could make being less-than comparable and having a default total order two different things. (Although less-than comparison is a good candidate for a total order.) This would avoid certain subtle bugs as described above. At the same time, it would make STL a bit harder to learn. Currently the advice is: “want your type be usable with maps? — do what int does: define operator<”. With the change I described above, the advice would become “want your type be usable with maps? — determine if your type qualifies for operator<; if so add it, otherwise if there exists a default total order, specialize some template, or define some special function…” — this would make the learning curve steeper.

Advertisement