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