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

Matt Austern austern@apple.com
Mon Jan 26 02:55:00 GMT 2004


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



More information about the Libstdc++ mailing list