Sorting by element address

I stumbled across a situation where a library sorts a container (e.g. std::vector<T>) with a user-provided comparison object. For one particular case, the user actually doesn't want to sort the container, but the sorting happens unconditionally.

So, to try to avoid this situation, I thought to try using a comparison object that sorts based on element address. Equivalently, we have:

std::vector nums{1, 5, 4};
auto cmp = [](auto& a, auto& b) { return &a < &b; };
std::sort(nums.begin(), nums.end(), cmp);

This "works" because std::vector<T> elements are stored in (contiguous) memory locations in the same order as the elements in the vector. The end result is that the nums vector appears to have been left untouched even after sorting.

However, once I replace std::vector<T> with std::array<T, N>, I get a segmentation violation (see https://gcc.godbolt.org/z/9srehdbhG).

My first thought is that I'm violating the type requirements as listed at https://en.cppreference.com/w/cpp/algorithm/sort:

RandomIt must meet the requirements of ValueSwappable and LegacyRandomAccessIterator.

The type of dereferenced RandomIt must meet the requirements of MoveAssignable and MoveConstructible.

Compare must meet the requirements of Compare.

My assumption was that the addresses of the elements would remain stable throughout the sort - this is almost certainly wrong.

So, which requirements/preconditions of std::sort() am I violating?

Solution

The problem is that std::sort isn't restricted to calling the comparator with references to elements of the specified range, it is also calling a comparison between a helper variable and an element of the range.

It's legal to take the address of that helper variable, but it's not legal to do a pointer comparison.

If you switch to std::less()(&a, &b) ~~the segmentation fault goes away~~ but it still is going to act really weird -- your comparator isn't invariant under copies.

This is a violation of the concept required for sort compare functions:

For algorithms other than those described in [alg.binary.search], comp shall induce a strict weak ordering on the values.

Note "ordering on the values", not "ordering on the objects". That means you cannot rely on any properties of the objects being sorted (such as memory address) other than the value alone.