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?

Forearm

Pointer-types are the important part here; you're looking at the primary definition of less, but I'd bet it also has a specialization for pointers that is far more relevant to your question. Importantly: "A specialization of std::less for any pointer type yields a strict total order, even if the built-in operator< does not." – Morel

On your system the < operator might work the same as std::less, but it is not required to. – Phosphorite

Sort a vector of integers in descending order... now generalize.. now why omit the default operation? – Culpable

I believe it can be used for algorithms (ex: std::sort) without having to write a lambda doing the comparison. – Innsbruck

We cannot always overload operators. So rest of your question is meaningless. – Rarefied

Your edit doesn't actually cover why the other question's answer is not convincing. Are you not convinced that "< on pointers doesn't necessarily implement a strict-weak ordering", or that "std::less (...) is required to"? – Laroy

I am not convinced that "< on pointer does not necessarily implement a strict weak ordering" – Benighted

Answer 1

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.

Delmardelmer

Answer 2

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.

Hardigg

And why can't you simply use "<" in the comparison? The argument that std::less can be used as argument without having to write a lambda is far more convincing. – Spectrograph

@GoswinvonBrederlow If you use < then you require all types passed to it to have a operator < defined.Why make that a requirement when you can let the caller decide if they want to provide a operator < or just give the function something to work with? – Hardigg

I read "or just give the function something to work with" to passing an argument and for comfort the function would default it to std::less, just like you did above. That was my point. It's the argument passing and allowing overrides that makes it so useful. – Spectrograph

Compilers can also inline a call to a pointer to function if the function definition it refers to is available in the same compilation unit. The good thing about function objects is that you can store context information (some data) from one call to the following. The only thing that could be good is that if you can't inline (not defined yet), then the compiler raises an error. – Antung

Answer 3

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.

Finbar

Answer 4

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)

Glossology

I presume that implementation is only used by GCC for some architectures. For example it might be trouble for real-mode x86 segmented pointers, i.e. DS:DX – Cohby

@BenVoigt following the link to the libstdc++ code, I don't see any architectural switches. I don't think C++ is very friendly towards segmented architectures anyway, since == has to work for pointers and isn't allowed to spuriously succeed for completely different objects. The concept of near/far pointers doesn't exist in C++ (although it used to as an extension to ancient compilers), and I imagine that on segmented architectures, you would need to use a fat pointer to implement C++. Perhaps that's why GCC and Clang can get away with such simple implementations. – Glossology

Well, segmented architectures (or other "based pointers" like into memory-mapped files) are the reason that operator< is only required to compare pointers into the same complete object (no, not restricted to arrays). Because that guarantees to the compiler that the segment portion (or base of the pointer) are common between both operands. But std::less has to work even when the segment / base portion differs. – Cohby

@BenVoigt == comparison (see eel.is/c++draft/expr.eq#3) only allows unspecified behavior in the case of one-past-the-end pointers and object pointers. Given such a strict requirement (no spurious success for unrelated objects), I'm unsure how easily you could implement C++ pointers with segmented memory anyway. – Glossology

I think you're right that the original intent was to give implementations more freedom with <, but this freedom doesn't look to be utilized in any standard library, and it's unclear whether you could utilize it given strict requirements for pointers in other places. – Glossology

Gcc has some optimizations that assume that when p<q is executed, p and q must point into the same object. – Neuritis

Answer 5

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,

Antung