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
– François Andrieux, Commented Jan 15, 2019 at 15:23
The linked answer does not assert that std::less on nullptr is "undefined". It specifically says "unspecified", which is different. — You
– You, Commented Jan 15, 2019 at 15:23
This question goes into the difference between unspecified and undefined behavior. — François Andrieux
– François Andrieux, Commented Jan 15, 2019 at 15:24
On most implementations nullptr is a value equivalent to zero. — najayaz
– najayaz, Commented Jan 15, 2019 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
– SergeyA, Commented Jan 15, 2019 at 15:32

You · Accepted Answer · 2019-01-15 16:13:06Z

3

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).

edited Jan 15, 2019 at 16:13

answered Jan 15, 2019 at 15:36

You

24k3 gold badges55 silver badges67 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

fliX Over a year ago

std::less only takes 2 parameters. How do I combine them then?

You Over a year ago

@fliX: There's no good way using std::tie since std::tuple is specified to use the built-in operator<.

Collectives™ on Stack Overflow

Strict weak ordering on pointer values

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related