Hi,
The ill-formed checking in binary_heap::push_heap has made it
O(n). Remove this checking.
Since assert_valid also checks if (*this) is a legal heap, we can
remove is_heap and the assertions using it completely.
Bootstrapped and tested on x86_64-linux-gnu.
2017-03-09 Xi Ruoyao <r...@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.
---
.../ext/pb_ds/detail/binary_heap_/binary_heap_.hpp | 21 +++------------------
.../pb_ds/detail/binary_heap_/insert_fn_imps.hpp | 2 +-
2 files changed, 4 insertions(+), 19 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;
diff --git
a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
b/libstdc++-
v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
index f82dd52..3b63515 100644
--- a/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
+++ b/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp
@@ -92,6 +92,7 @@ resize_for_insert_if_needed()
m_actual_size = new_size;
m_a_entries = new_entries;
make_heap();
+ PB_DS_ASSERT_VALID((*this))
}
PB_DS_CLASS_T_DEC
@@ -103,7 +104,6 @@ modify(point_iterator it, const_reference r_new_val)
swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);
fix(it.m_p_e);
PB_DS_ASSERT_VALID((*this))
- _GLIBCXX_DEBUG_ASSERT(is_heap());
}
PB_DS_CLASS_T_DEC
--
Xi Ruoyao <r...@stu.xidian.edu.cn>
School of Aerospace Science and Technology, Xidian University
