If the sorting algorithm passes the same element to the comparison function

Question

std :: sort libcxx (the llvm version of the C ++ standard library) calls the comparison predicate with the same element, that is, both arguments of the comparison functor refer to the same position in the sequence to be sorted. A smaller example to illustrate the point.

$ cat a.cc #include <algorithm> #include <vector> #include <cassert> int main(int argc, char** argv) { int size = 100; std::vector<int> v(size); // Elements in v are unique. for (int i = 0; i < size; ++i) v[i] = i; std::sort(v.begin(), v.end(), [&](int x, int y) { assert(x != y); return x < y; }); return 0; } $ clang++ -std=c++11 -stdlib=libc++ a.cc -o a.out $ ./a.out a.out: a.cc:14: auto main(int, char **)::(anonymous class)::operator()(int, int) const: Assertion `x != y' failed. ./go.sh: line 5: 19447 Aborted (core dumped) ./a.out 

Works well with libstdc ++.

 $ clang++ -std=c++11 -stdlib=libstdc++ a.cc -o a.out $ ./a.out 

Is it possible to call a comparison function with the same element. Isn't that redundant.

Answer 1

I can talk with some authorities on this, as I am the one who wrote this code.

Here is the comparison that is validated in your example:

https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm#L3994-L3995

As the link becomes obsolete over time (point to an invalid line), I will also quote the code here:

  // __m still guards upward moving __i while (__comp(*__i, *__m)) ++__i; 

This is called an “unguarded” loop because there is no verification that the __i iterator completes the end of the sequence as it __i . The reason for this is that the invariant of this algorithm is that at this point it is known that __i <= __m (which is also in the comment 3 lines above this quote).

If you look at the code above this quote, you will see the following comments:

  // The search going up is known to be guarded but the search coming down isn't. // Prime the downward search with a guard. 

So, before we get to this point, a secure search by sequence is performed. That is, this test:

 if (__i == --__j) 

After this test detects a lower guard, the algorithm then proceeds to insecure loops that have only one iteration test, whereas otherwise there would be two iteration tests (an iterator test and an iterated value dereferenced test).

The use of "unguarded loops" is the reason that the element is compared with itself. During development, I measured that the cost of one additional comparison in a loop was better than including two comparisons per iteration in a loop.

Of course, this is an engineering compromise. If the comparison function were terribly expensive compared to the cost of comparing the iterators themselves, one could come to a different conclusion.

This answer is fully consistent with rici answer , which is also correct (and I supported it). I added my voice, as I could discard "presumably" and point to certain lines of code in the algorithm.

Answer 2

Presumably, according to the authors of the standard library, it is faster to run a test that is guaranteed to return false than to constantly check equal indexes, as well as compare elements. This may be due to the fact that the support element is used as a control point of the cycle.

Of course, the comparison function is allowed to be called this way, and assert is not allowed in your code.