3

Imagine the following scenario:

std::atomic<int>  values[10];
std::size_t      indices[10];

void sort() {
    std::iota(indices, indices+10, 0);

    std::sort(indices, indices+10,
        [&](size_t lhs, size_t rhs) { return values[lhs] < values[rhs]; });
}

While running the sort(), another thread is changing values. Will this merely result in indices not being correctly ordered afterwards, or is it actually undefined behaviour?

Benno
  • 5,288
  • 5
  • 42
  • 60
  • Quicksort may rely on the fact that there are elements smaller and higher than the pivot during the scans. If you break this property, the algorithm can go nuts. –  Feb 19 '16 at 10:29
  • 1
    I don't know for sure. Instinctively, I would place such an action in the 'batshit crazy' category. – Martin James Feb 19 '16 at 11:34
  • Martin James: It looks glaring in this example, because all irrelevant details are removed. A more subtle use case where the same question arises would be sorting a vector of shared_ptr by their use count. – Benno Feb 19 '16 at 12:11

2 Answers2

3

Probably (see below) it's undefined behavior; in practice, I've seen plain crashes (for out of container boundary access) even just for incorrect (=not inducing a total ordering) comparators, and < with indexes changed while sorting surely fails to induce a total ordering

Interestingly, the standard doesn't explicitly mention undefined behavior regarding this issue; C++11 §5.4 ¶3 just states that

For algorithms other than those described in 25.4.3 to work correctly, comp has to induce a strict weak ordering on the values.

and I fail to see a formal definition of "work correctly" looking around there; even just the word "undefined" isn't ever uttered in the whole chapter 25 (which describes <algorithm>).

Matteo Italia
  • 123,740
  • 17
  • 206
  • 299
  • Just to play the devil's advocate, couldnt the crashes also be caused by the standard library implementing the c++ standard incorrectly? – Benno Feb 19 '16 at 10:27
  • @Benno: in facts I'm looking up a quotation in the standard. – Matteo Italia Feb 19 '16 at 10:29
  • 2
    This may not be an explicit mandate, but I believe that since the Standard does not define what should happen, that therefore that makes it undefined behaviour. – Puppy Feb 19 '16 at 11:29
  • 1
    That wording was fixed by a recent-ish LWG issue to be a "shall" requirement, and I'm fairly sure there's global wording in the library introduction making violating such requirements UB. – T.C. Feb 19 '16 at 11:38
2

std::sort requires a sorter which satisfies the strict weak ordering rule. (Explained in this answer)

If you change the contents simultaneously, this ordering may not maintain and thus results in undefined behaviour. (Can cause infinite loop in sorter, a crash, indices not being correctly ordered afterwards(as you mentioned), indices correctly sorted, 2 moons or something else)

Community
  • 1
  • 1
Mohit Jain
  • 30,259
  • 8
  • 73
  • 100