Determining if std::sort(begin, end) modified the range

What is the most elegant way to determine if a call to std::sort(begin, end) actually modified the range?

Here are my two ideas:

(a) check if already sorted O(n):

if (already_sorted(begin, end)) { return false; }
std::sort(begin, end);
return true;

(b) track changes in comparator (is this safe?):

bool modified = false;
std:开发者_运维知识库:sort(begin, end, [&modified](T a, T b){ modified |= a<b; return a<b; });
return modified;

Is there a better way?

Unless you iterate through the structure from "begin" to "end", you can't know if it is already sorted, so the best you can do it is in O(n).

I would go for the first choice, the already_sorted one.

I don't think you can do this any better than O(n) checking if the array came back in a different order than which it started. Hijacking the comparator to see if things are out if order isn't guaranteed to work, since in theory the sort function can do whatever comparisons it likes without necessarily moving anything. Moreover, tracking whether any swaps were performed doesn't necessarily tell you if the order changed, since the sort could also move things around and restore them to the same order at the end of the sort (think heapsort, for example).

Do you consider a range modified if two equal values were exchanged? In that case the already_sorted variant won't work.

Otherwise it should be the fastest way.

If the objects being sorted are of class type, you could introduce a subobject with an operator = overload that would be called by std::swap. However, that could in theory still allow false positives, if objects were swapped and then swapped back.

Probably you should stick with already_sorted until you're sure that it is taking a significant amount of the total execution time.