diff options
| author | Jonathan Wakely <redi@gcc.gnu.org> | 2017-03-15 20:11:48 +0000 |
|---|---|---|
| committer | Jonathan Wakely <redi@gcc.gnu.org> | 2017-03-15 20:11:48 +0000 |
| commit | 75d359f75944354ab1e7fcbf9afafd46e868fb37 (patch) | |
| tree | 378a37f9de23aceafda17406a7f093e8bfdf74d5 /libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp | |
| parent | 7fb22ebe018682ebcddc069c0ba39d82c3e91eb8 (diff) | |
| download | gcc-75d359f75944354ab1e7fcbf9afafd46e868fb37.zip gcc-75d359f75944354ab1e7fcbf9afafd46e868fb37.tar.gz gcc-75d359f75944354ab1e7fcbf9afafd46e868fb37.tar.bz2 | |
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.
From-SVN: r246173
Diffstat (limited to 'libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp')
| -rw-r--r-- | libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp | 21 |
1 files changed, 3 insertions, 18 deletions
diff --git a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp index 2755f06..f653a1e 100644 --- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp +++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp @@ -266,20 +266,14 @@ namespace __gnu_pbds const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); entry_pointer end = m_a_entries + m_size; std::make_heap(m_a_entries, end, m_cmp); - _GLIBCXX_DEBUG_ASSERT(is_heap()); } void push_heap() { - if (!is_heap()) - make_heap(); - else - { - const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); - entry_pointer end = m_a_entries + m_size; - std::push_heap(m_a_entries, end, m_cmp); - } + const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); + entry_pointer end = m_a_entries + m_size; + std::push_heap(m_a_entries, end, m_cmp); } void @@ -290,15 +284,6 @@ namespace __gnu_pbds std::pop_heap(m_a_entries, end, m_cmp); } - bool - is_heap() - { - const entry_cmp& m_cmp = static_cast<entry_cmp&>(*this); - entry_pointer end = m_a_entries + m_size; - bool p = std::__is_heap(m_a_entries, end, m_cmp); - return p; - } - #ifdef _GLIBCXX_DEBUG void assert_valid(const char*, int) const; |