How does std::deque work currently?

[Jonathan Wakely]

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.

jon

-- 
"Live fast, die old, and make very sure everyone knows you were there."
	- Alan Cox