Why is std::less better than "<" for pointers?

Question

C++ primer, 5th, 14.8.2, Using a Library Function Object with the Algorithms:

vector<string *> nameTable;  // vector of pointers
// error: the pointers in nameTable are unrelated, so < is undefined
sort(nameTable.begin(), nameTable.end(),
     [](string *a, string *b) { return a < b; });
// ok: library guarantees that less on pointer types is well defined
sort(nameTable.begin(), nameTable.end(), less<string*>());

Then I checked the std::less implementation in libc++ (code block modified for readability):

template <class _Tp>
struct less {
    constexpr bool operator()(const _Tp& __x, const _Tp& __y) const
        {return __x < __y;}
};

I have found out that std::less also uses < to do the work, so why is < undefined for pointers and std::less isn't? Why would I use std::less?

Answer 1

Why do we need std::less?

Comparison between pointers is only well-defined if both are part of the same array. Otherwise, the result is unspecified (see [expr.rel]). Note that this isn't the same as undefined behavior.

This is problematic when sorting an array of pointers, keeping a std::set<void*>, etc. because the algorithms and data structures require a [strict weak ordering]. If some pointers are unordered, this is only a partial ordering.

std::less guarantees a strict total order, which is even stronger than a strict weak order:

For templates less, greater, less_equal, and greater_equal, the specializations for any pointer type yield a result consistent with the implementation-defined strict total order over pointers.

[Note: If a < b is well-defined for pointers a and b of type P, then (a < b) == less<P>()(a, b), (a > b) == greater<P>()(a, b), and so forth. — end note]

- [comparisons.general]

On architectures with memory segmentation, this could make std::less more expensive because both the base pointer and the offset within a segment would need to be compared. It could be more efficient if < only provided a partial ordering, and the developer opted into std::less if they really need a total ordering.

Why is std::less simply delegated to < in libc++?

The quoted paragraph also hints at the reason why libc++ implements std::less using <: because < happens to be well-defined for Clang anyway, so its standard library doesn't have to do anything special.

However, this isn't guaranteed by the standard, and not every compiler gives such strong guarantees to the < operator. GCC doesn't provide a total order for <, and its standard library implements std::less using:

// for two pointers x, y
return (std::uintptr_t)x < (std::uintptr_t)y;

The total order is achieved by comparing the memory addresses that the pointers represent, rather than the pointers directly.

Implementations of std::less compared

Library	Header	Implementation for pointers p, q
GCC libstdc++	bits/stl_function.h	(std::uintptr_t)p < (std::uintptr_t)q (< is a partial order)
Clang libc++	__functional/operations.h	p < q (< is a total order)
MSVC STL	type_traits	p < q (< is a total order)

Answer 2

The first problem with < is that under the C++ standard, < on pointers can be utter nonsense on anything that doesn't point within the same "parent" object or array.

This is because of the existence of segmented memory models, like the 8086's. It is much faster to compare within segments by ignoring the segment number, and objects cannot span over segments; so < can just compare offsets within segments and ignore segment number.

There are going to be other cases like this on equally strange hardware; imagine hardware where const (ROM) and non-const (RAM) data exist in a separate memory space.

std::less<Pointer> meanwhile guarantees a strict weak ordering despite any quirks in the memory architecture. It will pay the price on every comparison.

The second reason we need std::less is to be able to pass the concept of "less than" around easiliy. Look at std::sort's 3 argument overload:

void sort( Iterator, Iterator, Comparator )

here we can pass how we want to sort in the 3rd parameter. If we pass std::greater<Foo>{} we get one sort, and if we pass std::less<Foo>{} we get the opposite.

By default the 2 argument version sorts like std::less, but once you have greater, greater equal, less equal, adding less just makes sense.

And once you have defined less, using it to describe the behavior of default std sort and std map and the like is easier than repeating all of the wording about how it uses < except if it is on pointers then it generates a strict weak ordering that agrees with < where < has fully specied behavior in the standard.

Answer 3

The purpose of std::less and friends is it allows you to generalize your code. Lets say we are writing a sorting function. We start with

void sort(int * begin, int * end) { /* sort here using < /* }

So now we can sort a container we can get int*'s to. Now lets make it a template so it will work with all type

template<typename Iterator>
void sort(Iterator begin, Iterator end) { /* sort here using < /* }

Now we can sort any type and we are using an "Iterator" as our way of saying we need something that points to the element. This is all well and good but this means we require any type passed to provide a operator < for it to work. It also doesn't let use change the sort order.

Now we could use a function pointer but that won't work for built in types as there is no function you can point to. If we instead make an additional template parameter, lets call it Cmp, then we can add another parameter to the function of type Cmp. This will be the comparison function. We would like to provide a default value for that so using std::less makes that very easy and gives us a good "default" behavior.

So with something like

template<typename Iterator, typename Cmp>
void sort(Iterator begin, Iterator end, 
          Cmp c = std::less<typename std::iterator_traits<Iterator>::value_type>) 
          { /* sort here using c /* } 

It allows you to sort all built in types, any type that has a operator <, and lets you specify any other way you want to compare elements in the data to sort them.

This is why we need std::less and friends. It lets us make the code generic and flexible without having to write a lot of boiler plate.

---

Using a function object also gives us some performance benefits. It is easier for the compiler to inline a call to the function call operator then it if it was using a function pointer. It also allows the comparator to have state, like a counter for the number of times it was called. For a more in-depth look at this, see C++ Functors - and their uses.

Answer 4

std::less is just a default policy that takes the natural sorting order of an object (i.e., its comparison operators).

The good thing about using std::less as a default template parameter is that you can tune your sorting algorithm (or your ordered data structure), so that you can decide whether to use the natural sorting order (e.g. minor to major in natural numbers) or a different sorting order for your particular problem (e.g. first odd and then even numbers) without modifying the actual object operators or the algorithm itself.

struct natural {
   unsigned value;

   natural( unsigned v ) :
     value(v)
   {
   }

   bool operator< ( natural other ) const {
      return value < other.value;
   }
};

struct first_the_odds {
   bool operator()( natural left, natural right ) const {
      bool left_odd  = left.value % 2 != 0;
      bool right_odd = right.value % 2 != 0;

      if( left_odd == right_odd ) {
         return left < right;
      } else {
         return left_odd;
      }
   }
};

// Sort me some numbers
std::vector<natural> numbers = { 0, 1, 2, 3, 4 };
std::sort( numbers.begin(), numbers.end(), first_the_odds() );
for( natural n : numbers )
   std::cout << n.value << ",";

Output:

1, 3, 0, 2, 4,

Answer 5

Because < isn't always operator<(). Only classes have operator functions, so your suggestion would not work for the built-in types.

Furthermore, < on pointers doesn't necessarily implement a strict-weak ordering, whereas std::less (via specialisation — what you posted isn't "all" of std::less!) is required to:

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

In short: std::less works for anything that supports a less-than comparison.