On Jul 15, 2014, at 12:18 PM, David Majnemer <[email protected]> wrote:
> Ping. > > On Wed, Jul 9, 2014 at 3:14 AM, David Majnemer <[email protected]> > wrote: >> std::make_heap is currently implemented by iteratively applying a >> sift_up-type algorithm. >> Since sift-up is O(ln n), this gives std::make_heap a worst case time >> complexity of O(n ln n). Since the C++ standard mandates that >> std::make_heap make no more than O(3n) comparisons, this makes our >> std::make_heap out of spec. >> >> Fix this by introducing an implementation of __sift_down and switch >> std::make_heap to create the heap using it. This gives std::make_heap >> linear time complexity in the worst case. >> >> This fixes PR20161. I added some more bits to the tests. Your change to “make_heap.pass.cpp” is not right because: 1) It passes a comparison function to make_heap, but that test is testing the version that does not take a comparison predicate. 2) It uses a lambda, which fails when the tests are run with -std=c++03 Revised test attached. — Marshall
PR20161-test.patch
Description: Binary data
_______________________________________________ cfe-commits mailing list [email protected] http://lists.cs.uiuc.edu/mailman/listinfo/cfe-commits
