Re: [RFC] libstdc++/18080: deque::push_back & co not O(1)

[Dhruv Matani <dhruvbird at gmx dot net>]

Hi,
	Maybe you should have a look at this:
http://groups.google.com/groups?hl=en&lr=&threadm=cf18e89.0306202024.7413de84%40posting.google.com&rnum=1&prev=/groups%3Fq%3Ddhruvbird%2Bdeque%2Bcomplexity%26hl%3Den%26lr%3D%26group%3Dcomp.std.c%252B%252B%26selm%3Dcf18e89.0306202024.7413de84%2540posting.google.com%26rnum%3D1

I guess there is no bug in the library.

-Dhruv.


On Thu, 2004-10-21 at 16:22, Paolo Carlini wrote:
> Hi everyone,
> 
> this is a recurring issue (see, f.i., libstdc++/13537): according to
> the current standard (I cannot find any open issue, by the way):
> 
>  "Inserting a single element either at the beginning or end of
>  a deque always takes constant time..."
> 
> People complain that this is not the case for our implementation, due
> to the reallocation of the "map" of pointers: in fact, the original
> SGI docs only guarantee *amortized* constant time.
> 
> What should we reply to those PRs? A few possibilities:
> 
>   1- The standard actually requires only amortized constant time
>      (DR 139 [TC] seems relevant about this).
>   2- We don't have a bug, because, according to 23.1/2, the complexity
>      requirements are stated solely in terms of the number of operations
>      *on the contained objects* (therefore, not on deque's "map")
>   3- We have a bug but the requirements of the standard are basically
>      unimplementable.
>   4- It's a "normal" bug and we plan to fix it (How? Any ideas?)
>   5- It's a "normal" bug and we don't plan to fix it in the short term
>      because requires almost complete rewrite of deque ([Suspended]?)
>   6- What else?
> 
> Some time ago, libstdc++/13537 has been closed by submitter himself basing
> on 2-, but I'm not completely convinced...
> 
> Thanks for any feedback,
> Paolo.
-- 
        -Dhruv Matani.
http://www.geocities.com/dhruvbird/

The price of freedom is responsibility, but it's a bargain, because
freedom is priceless. ~ Hugh Downs