Re: An Interesting Gotcha
From: Siemel Naran (SiemelNaran_at_REMOVE.att.net)
Date: Thu, 01 Apr 2004 08:31:17 GMT
"Leor Zolman" <email@example.com> wrote in message
> On Wed, 31 Mar 2004 18:18:50 GMT, "Siemel Naran"
> <SiemelNaran@REMOVE.att.net> wrote:
> >"Uwe Schnitker" <schnitkerAffenschaukel@sigma-c.com> wrote in message
> >> "Siemel Naran" <SiemelNaran@REMOVE.att.net> wrote in message
> >> > Or use std::deque instead of std::vector, it has the same problem.
> >> No, it hasn't. Using push_back or push_front on a deque invalidates all
> >> iterators into the deque, but does >>not<< invalidate any pointer or
> >> reference into it.
> >> Discusion of details of a typical implementation: This is because a
> >> can just obtain another chunk of memory to store the new elements, and
> >> doesn't have to move existing elements.
> >But when you insert an element into the beginning of a chunk through
> >deque::push_front or deque::insert, then won't it have to rearrange the
> >elements in this one chunk?
> Yes for insert (except at the ends) but not for push_front or push_back.
> Whether you push_front or push_back, you're not re-arranging anything
> within that block. And when you get to either end, it allocates another
> block. So your pointers/references are safe. But not, as stated above,
> iterators (because they're /not/ just pointers).
Thanks, this makes sense. Iterators may become invalid because the previous
and next pointers to element/block won't get updated, right? I looked it up
in the standard too. 22.214.171.124 deque modifiers, item 1 Effects, says:: "An
insert in the middle of the deque invalidates all the iterators and
references to elements of the deque. An insert at either end of the deque
invalidates all the iterators to the deque, has no effect on the validity of
references to elements of the deque".