This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/62045] [5 Regression] __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> is too slow
- From: "redi at gcc dot gnu.org" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Wed, 17 May 2017 17:18:53 +0000
- Subject: [Bug libstdc++/62045] [5 Regression] __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> is too slow
- Auto-submitted: auto-generated
- References: <bug-62045-4@http.gcc.gnu.org/bugzilla/>
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> ---
Author: redi
Date: Wed May 17 17:18:14 2017
New Revision: 248164
URL: https://gcc.gnu.org/viewcvs?rev=248164&root=gcc&view=rev
Log:
PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap
Backport from mainline
2017-03-15 Xi Ruoyao <ryxi@stu.xidian.edu.cn>
PR libstdc++/62045
* include/ext/pb_ds/detail/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.
Backport from mainline
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:
branches/gcc-5-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc
Modified:
branches/gcc-5-branch/libstdc++-v3/ChangeLog
branches/gcc-5-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
branches/gcc-5-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
branches/gcc-5-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc