[Bug libstdc++/63706] stl_heap.h:make_heap()'s worst time complexity doesn't conform with C++ standard

[glisse at gcc dot gnu.org]

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

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-03-29
             Status|UNCONFIRMED                 |WAITING
     Ever confirmed|0                           |1

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Trying exactly the construction described here with g++-4.9:

#include <algorithm>
#include <vector>
#include <iostream>

int count=0;
bool cmp(int a, int b){++count;return a<b;}

int main(){
  std::vector<int> v;
  const int n=100000000;
  for(int i=0;i<n;++i)
    v.push_back(i);
  for(int i=0;i<n;++i)
    v.push_back(4*n-i);
  for(int i=n;i<3*n;++i)
    v.push_back(i);
  std::make_heap(v.begin(),v.end(),cmp);
  std::cout << v.size() << ' ' << count << '\n';
}

I get

400000000 599999960

(and the ratio is pretty much constant if I change n to 1000, 100000, etc)

So the example provided here does not show any violation of the complexity
requirement. I haven't looked at the implementation, maybe there are indeed
problematic cases, just not this one.