Strict weak ordering on pointer values

Question

Consider the following struct:

struct Foo {
  const Bar* x;
  const Bar* y;

  Foo(const Bar* _x, const Bar* _y = nullptr) : x(_x), y(_y) { assert(x); }
}

How do we define a strict weak ordering on x and y so that the object can be used within a std::set? Note that y can be a null pointer. As mentioned in Using std::less with nullptr the behavior of std::less on null pointers is ~~undefined~~ unspecified. Will the following solution be sufficient?

bool operator<(const Foo& rhs) const {
  uintptr_t numX = reinterpret_cast<uintptr_t>(x);
  uintptr_t numY = reinterpret_cast<uintptr_t>(y);

  uintptr_t numRhsX = reinterpret_cast<uintptr_t>(rhs.x);
  uintptr_t numRhsY = reinterpret_cast<uintptr_t>(rhs.y);

  return std::tie(numX, numY) < std::tie(numRhsX, numRhsY);
}

EDIT: If not what is the proper way (e.g. how to combine std::less with std::tie)?

I would guess that this would have the same issue as `std::less` since they both might compare `nullptr` with `operator<` which the linked question says is unspecified. — François Andrieux, Jan 15 '19 at 15:23
The linked answer does _not_ assert that `std::less` on `nullptr` is "undefined". It specifically says "unspecified", which is different. — You, Jan 15 '19 at 15:23
[This question](https://stackoverflow.com/questions/2397984/undefined-unspecified-and-implementation-defined-behavior) goes into the difference between unspecified and undefined behavior. — François Andrieux, Jan 15 '19 at 15:24
On most implementations nullptr is a value equivalent to zero. — najayaz, Jan 15 '19 at 15:29
Being unspecified is different from being undefined. As long as you know that platform you are coding it for has nullptr as 0, and this is OK for your set, using `std::less` is perfectly fine. — SergeyA, Jan 15 '19 at 15:32

You · Accepted Answer · 2019-01-15T16:13:06.910

Using std::less<Bar*> is sufficient (but using operator< is not). The pointer specializations of std::less (as the accepted answer to "Using std::less with nullptr" points out) guarantee a total ordering. Comparison with nullptr is unspecified, meaning the standard does not impose a particular ordering, but std::less must still produce a total ordering (and for a given pointer p, p < nullptr necessarily produces the same value every time).

Since a total ordering is stronger than a weak ordering, using std::less is sufficient in your case.

EDIT: If not what is the proper way (e.g. how to combine std::less with std::tie)?

There is no neat way, unfortunately. Since std::tie returns an std::tuple, and comparison on tuples is defined in terms of operator< on their values (rather than std::less), you can't really use std::tie here. To use std::less, you'd have to do it manually:

bool operator<(const Foo& rhs) const {
  if (std::less<>{}(x, rhs.x))
    return true;
  if (std::less<>{}(rhs.x, x))
    return false;
  return std::less<>{}(y, rhs.y);
}

As an aside, your current implementation (reinterpreting the pointers as integers) also produces a total ordering (obviously, since you're comparing integers) but instead of unspecified behavior you'll have implementation-defined behavior (from the reinterpret_cast).

std::less only takes 2 parameters. How do I combine them then? — fliX, Jan 15 '19 at 15:55
@fliX: There's no good way using `std::tie` since `std::tuple` is specified to use the built-in `operator<`. — You, Jan 15 '19 at 16:13

Strict weak ordering on pointer values

1 Answers1