How does `std::less` work?

Question

Pointer relational operators do not define a total order (§ 5.9 of the C++11 standard):

If two pointers p and q of the same type point to different objects that are not members of the same object or elements of the same array or to different functions, or if only one of them is null, the results of p<q, p>q, p<=q, and p>=q are unspecified.

std::less documentation says:

The partial specialization of std::less for any pointer type yields a total order, even if the built-in operator< does not.

How does it yield this total order from a partial order?

---

I am unable to answer to this question by looking at /usr/include/c++/4.9/bits/stl_function.h for struct less definitions:

  template<typename _Tp = void>
    struct less;

  template<typename _Tp>
    struct less : public binary_function<_Tp, _Tp, bool>
    {
      bool
      operator()(const _Tp& __x, const _Tp& __y) const
      { return __x < __y; }
    };

  template<>
    struct less<void>
    {
      template <typename _Tp, typename _Up>
        auto
        operator()(_Tp&& __t, _Up&& __u) const
        noexcept(noexcept(std::forward<_Tp>(__t) < std::forward<_Up>(__u)))
        -> decltype(std::forward<_Tp>(__t) < std::forward<_Up>(__u))
        { return std::forward<_Tp>(__t) < std::forward<_Up>(__u); }

      typedef __is_transparent is_transparent;
    };

Electrode

Answer 1

How does it yield this total order from a partial order?

The standard rarely says how something should be accomplished. Instead, it says what is required. And this is exactly the case. The standard is requiring std::less to provide a total order, in §20.9.6/14:

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.

while operator<'s behaviour in this regard is unspecified according to §5.9/4 (the quote you have in your question).

Unspecified behaviour is defined in §1.3.25 to mean:

behavior, for a well-formed program construct and correct data, that depends on the implementation [...]

In your specific implementation, operator< already provides a total order (probably because your pointer type is implemented as a 32 bits or 64 bits address, which can be easily interpreted as something similar to an unsigned integer, yielding a total order), therefore std::less simply forwards its arguments to that operator.

Hessney

Thank you, your answer is perfect. However, are you aware of any implementation of operator< that does not provide a total order? How does the std::less implementation yield a total order out of it? – Electrode

@Electrode I'm not aware of the existence of such implementation. I'm pretty sure it exists, considering how carefully the standard committee decides what goes as a requirement and what goes as unspecified behaviour. – Hessney

I'm not sure it still exists. Much of this came from the days of near and far pointers. – Esemplastic

Might be to accommodate segmented memory for x86 processors running in the old "real" mode (see en.wikipedia.org/wiki/X86_memory_segmentation ) – Blubber