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

[Matt Austern <austern at apple dot com>]

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?

			--Matt