How can pointers be totally ordered?

Is it possible to implement the standard library on targets where pointers do not form a global, total order?

Yes. Given any finite set you can always define an arbitrary total order over it.

Consider a simple example where you have only five possible distinct pointer values. Let's call these O (for nullptr), γ, ζ, χ, ψ¹.

Let's say that no pair of two distinct pointers from the four non-null pointers can be compared with <. We can simply arbitrarily say that std::less gives us this order: O ζ γ ψ χ, even if < doesn't.

Of course, implementing this arbitrary ordering in an efficient manner is a matter of quality of implementation.

---

¹ I am using Greek letters to remove subconscious notion of order that would arise due to familiarity with the latin alphabet; my apologies to readers that know the Greek alphabet order

Can pointers be totally ordered? Not in portable, standard C++. That's why the standard requires the implementation to solve the problem, not you. For any given representation of a pointer, it should be possible to define an arbitrary total ordering, but how you do it will depend on the the representation of a pointer.

For machines with a flat address space and byte addressing, just treating the pointer as if it were a similarly sized integer or unsigned integer is usually enough; this is how most compilers will handle comparison within an object as well, so on such machines, there's no need for the library to specialize std::less et al. The "unspecified" behavior just happens to do the right thing.

For word addressed machines (and there is at least one still in production), it may be necessary to convert the pointers to void* before the compiler native comparison will work.

For machines with segmented architectures, more work may be necessary. It's typical on such machines to require an array to be entirely in one segment, and just compare the offset in the segment; this means that if a and b are two arbitrary pointers, you may end up with !(a < b) && !(b < a) but not a == b. In this case, the compiler must provide specializations of std::less<> et al for pointers, which (probably) extract the segment and the offset from the pointer, and do some sort of manipulation of them.

EDIT:

On other thing worth mentionning, perhaps: the guarantees in the C++ standard only apply to standard C++, or in this case, pointers obtained from standard C++. On most modern systems, it's rather easy to mmap the same file to two different address ranges, and have two pointers p and q which compare unequal, but which point to the same object.