14

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?

11
  • 3
    This does look like a compiler bug. Oct 3 at 17:23
  • 1
    @SamVarshavchik happens only if array is a local variable, hmm. An odd optimization? Oct 3 at 17:27
  • 6
    Congratulations, I think you found a bona fide compiler bug! Please file a bug report. In the meantime, here's an alternative cmp that will get the job done: auto cmp = [](auto&&, auto&&) { return false; };
    – Eljay
    Oct 3 at 18:03
  • 2
    There are timsong-cpp.github.io/cppwp/n4868/algorithms#parallel.exec-3 and timsong-cpp.github.io/cppwp/n4868/algorithms#parallel.user-1 which would make such a comparator UB, but it seems to me that both should apply to the parallel versions of the algorithms only, although that isn't obvious in the first case. Oct 3 at 18:31
  • 3
    I think the problem is that, when using that comparator, your elements aren't swappable. If you swap them, the swapped elements don't appear to have each other's previous value from the perspective of the comparator. Oct 3 at 19:43

3 Answers 3

5

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.

13
  • Ah. Couldn't one then just cast the addresses to (e.g.) unsigned long longs and then compare the integers? Incidentally, I still get the segfault if I do that. (Yes, I realize this is icky, I'm just trying to understand where the illegal behavior creeps in.) Oct 3 at 21:27
  • 1
    "The problem is that std::sort isn't restricted to calling the comparator with references to elements of the specified range": But where in the standard does it say that? std::sort is specified in terms of the postcondition + certain requirements. In OP's case the postcondition can be satisfied and it isn't obvious which of the requirements would be violated. If all requirements are satisfied, then an implementation ought to satisfy the postcondition and if using a temporary object makes this impossible, it shouldn't use one. Oct 3 at 22:35
  • 1
    @BenVoigt "which are not part of the contract": Where is that specified? Oct 3 at 22:45
  • 1
    @BenVoigt That's not a reasonable interpretation. With the same reasoning comp would also be required to provide a strict weak ordering for any possible values that aren't part of the range. Oct 4 at 17:44
  • 1
    @BenVoigt Compare isn't required to satisfy any concept anywhere, hence it also can't be required to model any. Oct 5 at 21:40
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).

5
  • libstd++ issue gcc.gnu.org/bugzilla/show_bug.cgi?id=111685 is currently closed as Invalid
    – Fedor
    Oct 6 at 10:15
  • Closed by the issue submitter, so that doesn't mean GCC maintainers have closed it. Oct 7 at 11:41
  • @JonathanWakely, does it mean that if for example I submit the same issue again, it will be fixed in libstdc++?
    – Fedor
    Nov 18 at 19:39
  • 1
    Please don't resubmit the same thing again, it will be closed as a duplicate. If you want something to be reconsidered, use the existing report. Nov 19 at 20:22
  • 1
    @Fedor (Notifying you about the comment above.) Nov 19 at 21:05
1

Since you comparator doesn't describe a strict weak ordering, it is invalid for use with std::sort. Passing such a comparator to std::sort is undefined behavior as far as I understand, meaning that both a crash and it working perfectly fine are valid outcomes.

Elements are moved inside the array during sorting, and thus can change address. std::sort assumes that a < b still holds even after a and b have been moved around, which is not the case when using your comparator.

I believe that what is happening here is that the invalid comparator is causing std::sort to run outside of the provided range. When using vector it just stomps over the heap without causing much damage, but when using array it trashes the stack, causing the crash. Moving the array to the heap prevents the crash

2
  • Long ago, I remember reading one of the programming magazines (probably Dr. Dobbs Journal, although it might even have been before that) talking about making loops run faster, and it pointed out that most loops have two stopping conditions (finding what it searches for, and reaching the end of the data), but that checking for the end of the data is not actually essential. If one can add a "bookend" item that always matches the other exit condition, then one saves a comparison and conditional branch on every iteration, which might have been as much as 20-30% of the loop body.
    – Ben Voigt
    Oct 5 at 20:02
  • I believe that this optimization technique is in play in the particular standard library implementation encountered by OP.
    – Ben Voigt
    Oct 5 at 20:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.