[LLVMbugs] [Bug 20161] New: `std::make_heap` has worst case time complexity of O(n log n) rather than the standard mandate O(n)

[bugzilla-daemon at llvm.org]

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

            Bug ID: 20161
           Summary: `std::make_heap` has worst case time complexity of O(n
                    log n) rather than the standard mandate O(n)
           Product: libc++
           Version: 3.4
          Hardware: Macintosh
                OS: MacOS X
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: netheril96 at gmail.com
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

Created attachment 12718
  --> http://llvm.org/bugs/attachment.cgi?id=12718&action=edit
Test source code

The current `std::make_heap` in libc++ uses an algorithm equivalent to
successively pushing into the heap, which has a worse case time complexity of
O(n log n), while both GCC and MSVC's implementation uses an algorithm that
builds the heap from bottom up, with complexity O(n).

The standard specifies that no more than 3n comparisons can be made in
`std::make_heap`. The attach test file, however, prints 480 (greater than
3*100) with libc++, but 144 with libstdc++, confirming that it is indeed a bug
in libc++'s implementation.

A longer discussion can be seen at
http://stackoverflow.com/questions/24475056/is-libcs-implementation-of-stdmake-heap-nonconformant.

-- 
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/20140630/3419bab5/attachment.html>