[Bug libstdc++/70898] New: Stateful Compare objects are very slow

[gccbugs at jbapple dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=70898

            Bug ID: 70898
           Summary: Stateful Compare objects are very slow
           Product: gcc
           Version: 4.8.4
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: libstdc++
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gccbugs at jbapple dot com
  Target Milestone: ---

/*

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;
}