[LLVMbugs] [Bug 16819] compare function with equal semantics cause std::sort function core dump

[bugzilla-daemon at llvm.org]

http://llvm.org/bugs/show_bug.cgi?id=16819

Howard Hinnant <hhinnant at apple.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|---                         |INVALID

--- Comment #1 from Howard Hinnant <hhinnant at apple.com> ---
There's two questions here:

1.  Why does >= cause sort to crash.

Section 25.4 [alg.sorting]/p3-p4 says:

... comp has to induce a strict weak ordering on the values.

The term strict refers to the requirement of an irreflexive relation (!comp(x,
x) for all x) ...

When comp is >=, it violates the "strict" requirement, for example 3 >= 3 is
true instead of the required false.

2.  Why does sort sometimes compare an element to itself?

This is done within two tight loops within this implementation of std::sort,
here is one of them:

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

Instead of doing this:

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

In general the extra self-compare done once in this loop will be far cheaper
than the iterator compare on each iteration of the loop.  The algorithm goes to
extra trouble just to set up this "unguarded loop" just because the
optimization is so compelling.

-- 
You are receiving this mail because:
You are on the CC list for the bug.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-bugs/attachments/20130807/99814beb/attachment.html>