https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #3 from Xi Ruoyao <ryxi at stu dot xidian.edu.cn> ---
Both Tobias' and my thought was wrong. In the entry of
__gnu_pbds::detail::binary_heap::push_heap, the array
m_a_entries[0..m_size-2] contains a heap, and
m_a_entries[m_size-1] contains the element being pushed
into the heap. So is_heap would return false most likely.
Then make_heap would be call and std::push_heap *won't* be
call.
It's easy to find out using gcov.
~~~
-: 272: void
100: 273: push_heap()
-: 274: {
100: 275: if (!is_heap())
99: 276: make_heap();
-: 277: else
-: 278: {
1: 279: const entry_cmp& m_cmp =
static_cast<entry_cmp&>(*this);
1: 280: entry_pointer end = m_a_entries + m_size;
1: 281: std::push_heap(m_a_entries, end, m_cmp);
-: 282: }
100: 283: }
~~~
This is certainly a bug making priority_queue::push O(n^2).
Since it works correctly in GCC 4.6, it's a regression.
Making a patch...
