[Bug libstdc++/62045] [5/6/7 Regression] __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> is too slow

[redi at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045

--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Wed Mar 15 20:11:48 2017
New Revision: 246173

URL: https://gcc.gnu.org/viewcvs?rev=246173&root=gcc&view=rev
Log:
PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap

2017-03-15  Xi Ruoyao  <ryxi@stu.xidian.edu.cn>

        PR libstdc++/62045
        * include/ext/pb_ds/qdetail/binary_heap_/binary_heap_.hpp
        (is_heap): Remove.
        (push_heap): Remove the wrong checking using is_heap.
        (make_heap): Remove the assertion using is_heap.
        * include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
        (modify): Ditto.
        (resize_for_insert_if_needed): Add PB_DS_ASSERT_VALID after
        calling make_heap.

2017-03-15  Jonathan Wakely  <jwakely@redhat.com>

        PR libstdc++/62045
        * testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc:
        New test.
        * testsuite/ext/pb_ds/regression/priority_queues.cc: Fix copy&paste
        error in comment.

Added:
   
trunk/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc
Modified:
    trunk/libstdc++-v3/ChangeLog
    trunk/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
    trunk/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
    trunk/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc