Sorting by element address

Question

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?

Answer 1

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.

Answer 2

I think your use is valid according to the current standard draft.

std::sort is specified in [alg.sort]/3 via its effects on the passed iterator sequence (not copies). The state required as postcondition is achievable and already satisfied when std::sort is entered.

The only potentially relevant requirement I see is that in [alg.sorting.general]/3 sentence 3, which vaguely requires comp to be a strict weak order on "the values". It doesn't specify what values are meant (or what qualifies as the value in relation to the iterators). But given that the binary predicate properties as well as the sorting postcondition are established only on iterators, the only reasonable interpretation I have is that it also considers only passing dereferenced iterators (into the iterator sequence passed to the sorting algorithm).

Then the implementation would not be allowed to use a local copy of elements to apply comp to. std::sort can be implemented without that.

Furthermore, [algorithms.parallel.user]/1 and [algorithms.parallel.exec]/3 specifically add requirements that would allow implementations to work on object copies instead, but only for parallel algorithms (i.e. the overloads with ExecutionPolicy template parameters). These wouldn't be necessary if the Compare requirements would permit this generally.

(In case of [algorithms.parallel.user]/1 it doesn't specifically say that it applies only to parallel algorithms, but I am inferring that from the context. I might be mistaken here and this is intended to always apply. But then I would expect it to be moved to a different part of the standard.)

The paper P0518 that made these additions based on a NB comment also seems to consider only parallel algorithms. I am not sure whether denying the use of local copies in the non-parallel variants of the algorithms is reasonable, but given that the paper didn't consider them as well, it seems to me that the committee members intentionally put more restrictions on the implementation for the non-parallel cases (or this specific use was overlooked).