How does `std::less` work?

2020-06-16 05:06发布

问题:

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;
    };

回答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.