[LLVMbugs] [Bug 22427] New: inplace_merge should not apply more than (last - first) - 1 comparisons if enough additional memory is available

[bugzilla-daemon at llvm.org]

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

            Bug ID: 22427
           Summary: inplace_merge should not apply more than (last -
                    first) - 1 comparisons if enough additional memory is
                    available
           Product: libc++
           Version: unspecified
          Hardware: All
                OS: All
            Status: NEW
          Severity: normal
          Priority: P
         Component: All Bugs
          Assignee: unassignedclangbugs at nondot.org
          Reporter: kariya_mitsuru at hotmail.com
                CC: llvmbugs at cs.uiuc.edu, mclow.lists at gmail.com
    Classification: Unclassified

Created attachment 13787
  --> http://llvm.org/bugs/attachment.cgi?id=13787&action=edit
clang++ -v

Please see the sample code below.

================================= sample code =================================
#include <algorithm>
#include <iostream>
#include <vector>

int main()
{
    std::vector<int> v = { 1, 3, 5, 2, 4, 6 };

    int count = 0;
    std::inplace_merge(v.begin(), v.end() - 3, v.end(),
        [&count](int lhs, int rhs) -> bool { ++count; return lhs < rhs; });

    std::for_each(v.begin(), v.end(), [](int x) { std::cout << x << ", "; });
    std::cout << std::endl << count << " comparisons" << std::endl;
}
================================= sample code =================================

================================= output =================================
1, 2, 3, 4, 5, 6, 
8 comparisons
================================= output =================================

cf. http://melpon.org/wandbox/permlink/u0NiYiwQ1fNUk7je


The C++11 standard 25.4.4[alg.merge]/p.8 says, "When enough additional memory
is available, (last - first) - 1 comparisons."

I believe that enough additional memory is available in the sample code above,
so it should apply at most 5 comparisons.

-- 
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/20150201/9482aed0/attachment.html>