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; } }
Could you please have a look to libstdc++/13537? IMO, wither we should reopen that one or close both ;) Thanks.
(In reply to comment #1) > Could you please have a look to libstdc++/13537? IMO, wither we should reopen > that one or close both ;) Thanks. Quoting from Sean Kirby in that discussion: >> 23.2.1.3.3 says, "Inserting a single element either at the beginning or end >> of a deque always takes constant time". >> (Aside: Does the Standard mean true constant time there? > 23.1/2 says, "All of the complexity requirements in this clause are stated > solely in terms of the number of operations on the contained objects." and then goes on to state: > You are talking about complexity in terms of the number of operations > performed on pointers to the contained objects. If that is true, than inserting before an iterator in a singly linked list is constant time since one only operates on list elements that contain the elements. Obviously, this is not true. The fact that the implementation of the deque uses an array of pointers to arrays of elements should excuse the behavior. I agree that either 13537 should be reopened or this should be marked invalid. I don't believe the response to 13537 is sufficient to mark either invalid. My understanding of big O notation is that for O(1) methods, the amount of time to perform the operation should be independant of the number of elements in the container. The example I gave clearly shows that these methods can be linear in the number of objects in the container. One does not look at the number of operations on elements of the container, one only looks at the total number of operations performed in executing the method. Again, I don't think there is an implementation which can meet the requirements of the standard. The current implementation is the standard implementation that I have been able to find and does a good job when one is not doing bizare behaviour as I demonstrate in the example. However, it is not O(1).
There is agreement among library maintainers that the analysis in libstdc++/13537 (Comment #3) is correct. See also http://tinyurl.com/52oro *** This bug has been marked as a duplicate of 13537 ***