How can pointers be totally ordered?

Pointers in C++ may in general only be compared for equality. By contrast, less-than comparison is only allowed for two pointers that point to subobjects of the same complete object (e.g. array elements).

So given T * p, * q, it is illegal in general to evaluate p < q.

The standard library contains functor class templates std::less<T> etc. which wrap the built-in operator <. However, the standard has this to say about pointer types (20.8.5/8):

For templates greater, less, greater_equal, and less_equal, the specializations for any pointer type yield a total order, even if the built-in operators <, >, <=, >= do not.

How can this be realised? Is it even possible to implement this?

I took a look at GCC 4.7.2 and Clang 3.2, which don't contain any specialization for pointer types at all. They seem to depend on < being valid unconditionally on all their supported platforms.

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.