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;
  throw InsufficientInput();


return limit && x < *limit;


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.

This entry was posted in programming and tagged , , , , . Bookmark the permalink.

17 Responses to On operator<

  1. TemplateRex says:

    Your example of `std::complex` is an exception. The reason is not that `std::complex` does not have a natural order. It’s far worse: there is no strict weak order that is consistent with complex multiplication. E.g. using lexicographical ordering on {re, im}, we have 0 < `i`. But multiplying that equation on both sides with `i`, you get 0 < -1, which is a contradiction. In other words, a `std::set` would not be compatible with `std::transform` with a lambda that multiplies with `i`. You would get undefined behavior because it breaks the set class invariants. You can imagine the cottage industry on StackOverflow trying to explain that🙂 So it’s inevitable that `std::complex` does not have an `operator<`.

    However, I think all types should *by default* have the full spectrum of relational operators defined using `std::lexicographical_compare` and `std::equal` in terms of their `std::tuple` representation. There is some tricky business with mutable members, but that should be the default. Any type T for which there would be severe confusion or errors (such as `std::complex`) should epxlicitly declare `operator<(T const&, T const&)=delete;`

    • I am not sure I am buying your argument with `complex` and `transform`. It equally well applies to `map<int>`. You just cannot perform an arbitrary transformation on elements in an ordered container, because this could change the order.

    • How is this different from multiplying real numbers by a negative?
      multiply both sides by -1
      -3<-4 (no it isn't, and that's why there's special rules for dealing with inequalities)

    • viboes says:

      I agree completely. Having a *natural* total order for product types and sum types *when* the types have a natural total order is always possible.

      However, satisfying a natural total order needs to satisfy more order constraints (see http://en.wikipedia.org/wiki/Ordered_field). This is why we don’t have a natural total order for complex.

      I don’t understood your transform argument.

      The question now is if we can define a *natural* total order for types that don’t define +,*, so that we all understand always the same what a *natural* total order mean.

      I find very pragmatic to have default natural order for all the types (as far as the conditions meet), and just use =delete for those that have problems🙂

  2. peterchen says:

    While “exceeds” is an intuitive definition of operator<, it isn't superior – there are other, competing definitions that would be equally valid. Indeed, in math this operator is commonly used for different types of order (http://en.wikipedia.org/wiki/Outline_of_order_theory), the "default" depending on the type of elements it's applied to.,So at least the dual use is not without precedent. Indeed, C++ models that use quite well: < denotes the "typical" relation appropriate in the current context, for other uses you define your own relation symbols / names.

    Yet it is right that "typical" is subjective; in math, the '<' of a complex number is usually comparing their magnitude – which does not fulfil the strict weak ordering requirement of std::map. (Which is a great reason to either not define it for std::complex, or to use the std::ordered you discuss)

    • As a side note, the comparison of magnitudes for complex numbers does implement a strict weak order. It is just that too many values would be treated as equivalent. — this is legal for a strict weak order, but undesirable in maps.

  3. Sean Parent says:

    I would recommend reading Elements of Programming along with Stepanov’s original paper, Fundamentals of Generic Programming, where the notion of a regular type is first defined. Operator < () should be used for the natural total order of a type. For a string, using the lexicographical ordering is a good choice for a natural total order. Note that operator<() must be a total ordering, not just strict-weak, because of the trichotomy law and equality. We do not define operator<() for complex as being lexicographical because it is not a _natural_ total order. Specifically it would violate the relationships with the arithmetic operators i.e. a < b => (1 / b) < (1 / a). This is what is meant by complex numbers have no natural total ordering.

    I've recommended for years that for types without a natural total order that std::less be specialized to provide a representational total order (such as a lexicographical ordering on complex numbers). There is some precedent in the standard, std::less() is defined for pointer that do not point into the same object and can be used with void*, where operator<() is not defined for such cases.

    You are allowed to specialize the standard templates with user defined types – so even if the standard doesn't do this where it should (complex and type_info to name two cases) users are free to. This means you can use your types with the standard containers and algorithms without specifying the ordering.

    • So, if we pointed out the differences between your advice an mine ‘vision’ above it would be:

      1. Specialise std::less rather than an invented std::order.
      2. operator< for string, optional should stay.

      Your advice does mitigate the problems I observe, however I am still left uncomfortable for two reasons.

      Regarding (1), I am not sure if the intention was for it to be specialized in the cases where there exists no natural total order. I am not sure if a specialization for pointers is a good illustration. After all operator< does exist for pointers (and may render an UB). My impression is that std::less (as the name suggests) is used to describe the semantics of operator< in the contexts where you expect a type rather than expression. I.e., it is map<T, less<T>> not because we want a customization point, but because there is no way to put sign “<” in there.

      Regarding (2), I agree that string’s operator< is rather “harmless”, although I would argue that it also violates the rule a < b => (1 / b) < (1 / a) in the sense that it doesn’t even compile. But for type optional, as I tried to show in the post, the natural (in some sense) order does exist and it is “unwanted” for reasons other that being compatible with the axiomatic systems. The reason is because “it is likely to cause bugs” — and this reason is outside of the mathematical abstractions. It is just something particular in C++.

      But going back to string’s operator<; except for the cases where it is used in STL (always via std::less) does anyone has a need to call it directly in a custom expression? Did you ever have to type:

      bool compute(std::string s, std::string t)
        return s < t;


      • Sean Parent says:

        Regarding (1): The reason why std::less is defined for pointers when operator < () is not, is because there is value in falling back to a representational order (which always exists) even no no natural total order does. Yes, std::less wasn't really intended as a customization point, but I'd rather see people reuse it then invent a third ordering as another way to specify a representational order.

        Regarding (2): String operator <() is very useful. String searching and sorting is central to many systems and not (nearly) all algorithms for doing such are contained in STL. Operator < doesn't violate the rule with multiplication because in the absence of multiplication no such rule exists.

      • Sean Parent says:

        ‘The reason is because “it is likely to cause bugs”’

        I did want to call that comment out. First, such a comment needs to be justified with actual statistics. One good way to avoid bugs is to associate strong semantics with names, teach those semantics, and use them consistently.

    • Indeed, I confused just any strict weak order with a total order. Thanks.

  4. We can not define strict ordering function for complex type. We also can not define it for double type. Consider following sample:

    #include <iostream>
    #include <set>
    using namespace std;
    int main(int, char**)
    	std::set<double> vals;
    	for (int i = 0; i<10; ++i)
    	double sum = 0.0;
    	for (auto item : vals)
    		sum += item;
    	cout << vals.count(1.0) << endl;

    This sample contains an error. We must not use double as a key. In order to detect similar issues we can use following specialization:

    template<> class std::less<double>{
    	public: bool operator() (double, double) = delete; // not defined

    It should give compile time error for std::set.

    • Sorry, multiset must be used in the example above.

    • Sean Parent says:

      The fact that 0.1 is not precisely representable as a double has no bearing. You could have chosen a better example with NaN’s which are unordered values. But dealing with partial functions is a fact of life in mathematics and especially on discrete machines (in fact NaN is an attempt at glossing over the fact that some operations, like division, are partial in mathematics).

      Using associative containers, sorting, searching, as well as operations like nth_element() with floating point numbers are critical for many systems, removing std::less for double only makes such operations considerably more difficult to call.

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

    I guess this code must use
    bool operator(double, double) but not any of: bool operator(double, optional) or bool operator(optional, optional).

    In this case we must get exception while casting optional to double.
    Is not it?

  6. viboes says:

    I don’t think the problem is with

    bool operator <(optional<T>, optional<T>);

    The problem is more with the example itself

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

    I guess that the intent of the user was to mean that when limit is nullopt, there is no limit, and so there is no need to do the comparison. But this is not what he wrote, as operator <(optional, optional) is not defined this way. The same problem occurs even if read_x returned optional.

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

    In order to get the intended behavior, the user should instead do

    return limit ? x < limit.get() : true;


    return x < limit.value_or(max);

    or even

    variant<double, nullopt> limit = read_limit(); // no limit is GT any double
    double x = read_x();
    return x < limit;

    The question is, can the type system prevents from such semantic errors? I don't think so. The user must know what he wants and how to get it.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s