CODEWITHSUNDEEP
c++multithreadingc++11
Benno
Benno

Reputation: 5456

Is it undefined behaviour to change sort order while sorting?

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?

Upvotes: 3

Views: 281

Answers (2)

Matteo Italia
Matteo Italia

Reputation: 126777

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>).

Upvotes: 3

Mohit Jain
Mohit Jain

Reputation: 30489

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)

Upvotes: 2

Related Questions