Re: [RFC] Re: How does std::deque work currently?

[Dhruv Matani <dhruvbird at gmx dot net>]

On Mon, 2004-01-26 at 08:24, Matt Austern wrote:
> On Jan 14, 2004, at 3:29 AM, Dhruv Matani wrote:
> 
> > On Wed, 2004-01-14 at 15:16, Jonathan Wakely wrote:
> >> On Wed, Jan 14, 2004 at 03:01:28PM +0530, Dhruv Matani wrote:
> >>
> >>> After reading the source, it seems that something like this is 
> >>> happening
> >>> in the current version if std::deque:
> >> [snip]
> >>> I think that my understanding of erase/insert is incorrect, since the
> >>> standard says that erase/insert should be constant time (I think)
> >>>
> >>> Please correct me if I'm wrong.
> >>
> >> I can't comment on all your points, but the standard says that deque
> >> guarantees (amortized) constant time for insert/erase at the 
> >> beginning or
> >> end of the sequence. Insertion in the middle is linear in n, where n 
> >> is
> >> the minimum of the distance to the beginning and to the end.
> >> The deque container is a model of Front Insertion Sequence and Back
> >> Insertion Sequence.
> >
> > Ok, thanks! So, it's only for the front and back, and that too 
> > amortized
> > conatant time as expected (sorry I did not mention the word amortized
> > earlier), because obviously, some time the map would need to be
> > reallocated.
> >
> > Now, I was wondering if it would be feasible to make the map point to
> > only 1 element instead of a collection of elements?
> 
> I'm not 100% sure what you're asking.  Are you asking why we have
> a block that's large enough to hold N elements instead of one that's
> only large enough to hold one element?

Yes. Exactly. What's the reasoning that went behind that decision?



-- 
	-Dhruv Matani.
http://www.geocities.com/dhruvbird/