Determinism in C++ standard library

Question

std::sort is not guaranteed to be stable.

Is it guaranteed to be deterministic though?

For example, will this code always print 1?

struct S
{
    int a, b;
};

bool cmp(const S& lhs, const S& rhs)
{
    return lhs.a < rhs.a;
}

int main()
{
    std::vector<S> seq1 = {{1, 2}, {1, 3}};
    std::vector<S> seq2 = seq1;
    std::sort(seq1.begin(), seq1.end(), cmp);
    std::sort(seq2.begin(), seq2.end(), cmp);
    std::cout << (seq1.back().b == seq2.back().b) << '\n';
}

Also, is C++ standard library deterministic in general (apart from obviously indeterministic elements, like RNG and clocks)?

Answer 1

The only requirement on a range once it has been sorted with std::sort is that the the elements are ordered according to the provided predicate. So if there are multiple valid orderings that are possible, then an implementation is conforming so long as it generates any one of them.

An implementation is allowed to generate different orderings each time std::sort is called on the same range. It can also generate a different ordering each time the program is executed.

Here are the requirements on std::sort. Note that there is no mention of any requirement that the resulting ranges be the same every time, so there is no guarantee that the results will be deterministic.