This is the mail archive of the
libstdc++@gcc.gnu.org
mailing list for the libstdc++ project.
Re: How does std::deque work currently?
- From: Jonathan Wakely <cow at compsoc dot man dot ac dot uk>
- To: Dhruv Matani <dhruvbird at gmx dot net>
- Cc: libstdc++ <libstdc++ at gcc dot gnu dot org>
- Date: Wed, 14 Jan 2004 09:46:04 +0000
- Subject: Re: How does std::deque work currently?
- References: <1074072638.3260.12.camel@home.free>
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