[Bug c++/18080] New: STL deque push_front, pop_front, push_back, and pop_back not O(1)

["ron at vaniwaarden dot org" <gcc-bugzilla at gcc dot gnu dot org>]

I had to implement a new deque myself (had to have special behaviour for
modifications) and could not come up with a way to do the summarized operations
in O(1).  I then looked at the deque in g++ and saw it had, basically, the same
algorithm I had come up with.

I don't know if there is an implementation of the deque that actually meets all
the performance requirements but included a program that illustrates the O(n)
growth of the summarized methods.  I admit that this is not a standard use of
the deque but still, thought it was worth mentioning and putting in the database...

#include <deque>
#include <iostream>
#include <time.h>

using std::cout;
using std::endl;
using std::deque;

double testDeque(int sz, int iterations)
{
  deque<int> d;
  for (int i=0; i < sz; ++i) d.push_front(i);
  clock_t t1 = clock();
  for (int i=0; i < iterations; ++i)
  {
    for (int j=0; j < sz; ++j)
    {
      int f = d.front();
      d.pop_front();
      d.push_back(f);
    }
  }
  clock_t t2 = clock();
  return ((double)(t2 - t1))/(double)CLOCKS_PER_SEC;
}

int main()
{
  const int sz = 1000;
  int nIts = 10000;
  double eTime = testDeque(sz, nIts);
  nIts = (int)(0.01*nIts/eTime); //should make nIts calls ~10ms

  for (int testSize = sz; testSize < sz*100; testSize += 100)
  {
    cout<<"Size:"<<testSize<<" time:"<<testDeque(testSize, nIts)<<endl;
  }

}

-- 
           Summary: STL deque push_front, pop_front, push_back, and pop_back
                    not O(1)
           Product: gcc
           Version: 3.2
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: c++
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ron at vaniwaarden dot org
                CC: gcc-bugs at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18080