------- Additional Comments From ron at vaniwaarden dot org 2004-10-20 16:45 -------
(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).
--
What |Removed |Added
----------------------------------------------------------------------------
Component|libstdc++ |c++
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=18080
