https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
Bug ID: 62045
Summary: __gnu_pbds::priority_queue<int, less<int>,
binary_heap_tag> is too slow
Product: gcc
Version: 4.9.1
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: tobias.polzer+gcc at gmail dot com
The documentation calls binary heaps the '"best-in-kind" for primitive types'
however __gnu_pbds::priority_queue<int, less<int>, binary_heap_tag> seems to
perform abysmally slow. This is shown in the test suite, e.g. here:
https://gcc.gnu.org/onlinedocs/libstdc++/manual/policy_based_data_structures_test.html#performance.priority_queue.int_push
where all other heaps vanish in comparison.
I had a short look at it in gdb and found that in a push, it executes
277 if (!is_heap())
276 make_heap();
in ext/pb_ds/detail/binary_heap_/binary_heap_.hpp, where is_heap and make_heap
both come from the std namespace and need linear time in the size of the
container. Even more peculiar, is_heap returns false, while I think is_heap
should be an invariant of the data structure?
