/* The following code is four times slower with libstdc++ than with libc++. I think the problem is partially too many copies in stl_heap.h. Instrumenting the code with a copy constructor and a destructor shows two copies of a Comp and two destructions for every call to push, while in libc++ it's only one call to a copy constructor and one call to the destructor. It seems like zero calls should be sufficient, as the Compare object could be kept around between push calls and reused. */ #include <queue> #include <vector> #include <iostream> using namespace std; struct Comp { vector<int> data; Comp(int n) : data(n,n) {} bool operator()(const double &x, const double &y) const { return x < y; } }; int main() { vector<double> data; Comp comp(150000); priority_queue<double, vector<double>, Comp> pq(comp, data); for (int i = 0; i < 100000; ++i) { pq.push(i); } cout << pq.top() << endl; }
*** Bug 70899 has been marked as a duplicate of this bug. ***
I think you are supposed to use std::reference_wrapper<Comp> as comparator if you don't want to copy it around. We did talk about reducing the number of copies (mostly in the context of sorting), but nobody has found the time / motivation to write patches.
This is being tracked as PR 51965 *** This bug has been marked as a duplicate of bug 51965 ***
(In reply to Jonathan Wakely from comment #3) > This is being tracked as PR 51965 PR 51965 seems to be about extra copies of the values, while this one is more about extra copies of compare objects (then there are also extra copies of iterators).
Ah, then it's a dup of PR 67085 (which I had incorrectly marked as a dup of 51965). *** This bug has been marked as a duplicate of bug 67085 ***
I'm not sure I agree that this is a duplicate. In particular, 67085 says that std::priority_queue operations "should not copy comparators". I suggested that as well in my initial report, but upon a closer reading of the standard, I'm not sure that would be conformant, since the standard requires priorityy_queue::push to call std::push_heap, and std::push_heap has to take its comparator by value. On the other hand, I do think that copying comparators *fewer* times that libstdc++ currently does is permitted, and I think it could have a big performance benefit in some cases. In particular, though push_heap seems like it must take the comparator by value, __push_heap is not required to do so. The constructor for __gnu_cxx::__ops::_Iter_comp_val and the function __gnu_cxx::__ops::__iter_comp_val also do not have to take their comparators by value.
Right, see https://gcc.gnu.org/bugzilla/show_bug.cgi?id=67085#c5 It's a dup. There's no point making two very similar changes to address very slightly different things. *** This bug has been marked as a duplicate of bug 67085 ***