In article <MPG.126bfff8221d52289896e1@news.teleport.com>,
smeyers@aristeia.com (Scott Meyers) wrote:

> According to Josuttis' "The C++ Standard Library" (p. 163),
>
>   ...any insertion or deletion [in a deque] invalidates all pointers,
>   references, and iterators that refer to other elements of the deque.  The
>   exception is when elements are inserted at the front or the back.  In
>   this case, references or pointers to elements stay valid (but iterators
>   don't).
>
> What is the justification for the behavior described in this last sentence?
> Why would iterators be invalidated, but pointers/references would not be?

You ask the best questions! :-)

As I'm sure you know, deque is implemented as an "array of arrays",
typically by having a buffer of pointers to arrays.  The buffer of
pointers is normally stored in contiguous memory (for arguments sake, a
vector, though I'm not aware of any implementation that actually uses
vector).

So consider what information needs to be in an deque::iterator to support
dereferencing:  a pointer to the element is typical, though this could
also be a pointer to the beginning of the buffer, and an offset.

Now consider operator -- ():  Now we must have a pointer to the beginning
of the buffer in order to detect if the iterator is decremented beyond its
beginning.  This could either be a raw pointer, or a pointer into the
buffer of pointers (which contains the pointer to the beginning of the
buffer).

What happens when operator -- () decrements past the beginning of the
(non-first) buffer?  The logic must reference the previous pointer in the
buffer (thus ultimately, the iterator must have the knowledge of where it
is in the buffer of pointers).

During push_back/front, the capacity of the array of buffers may be
exceeded, and have to be reallocated.  This will invalidate all pointers
into the buffer.  And thus invalidates any outstanding deque::iterators.

It would be ideal if we could have a deque of pointers for the array of
buffers, but that leads to a recursive definition of deque.

Another possibility would be to use a list<pointer> for the buffer array.
That way pointers into the buffer are never invalidated.  But this is not
only expensive, it makes it difficult (impossible?) to create
constant-time random access relational operators for deque::iterator
(assuming you stay with the constraint that push_front won't invalidate
deque::iterator).

In short, deque::iterators are invalidated because the internal buffer of
pointers may experience a push_front, or a reallocation, which in turn
invalidates data members of the deque::iterators.  This invalidation
typically (but not necessarily) impairs the iterator's ability to
traverse, as opposed to dereference.

Now that I've thought about it, perhaps the buffer of pointers could be
implemented as a "vector" that allowed the initial index to be non-zero.
deque::iterator could store a pointer to this buffer, and the current
index.  Such indices would not be invalidated by a push_front on the
buffer.  Hmm... but such a design would suffer from a "traveling queue"
behavior:

push_front();
while (very long time)
   push_front();
   pop_back();

As this loop progressed, the index to the first buffer would approach
LONG_MAX.  At which time the deque would become inoperable, but holding
only 1 buffer.  Might be able to wrap the index  ...  I don't know,
probably more complication than it's worth.

-Howard
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

According to Josuttis' "The C++ Standard Library" (p. 163),

  ...any insertion or deletion [in a deque] invalidates all pointers,
  references, and iterators that refer to other elements of the deque.  The
  exception is when elements are inserted at the front or the back.  In
  this case, references or pointers to elements stay valid (but iterators
  don't).

What is the justification for the behavior described in this last sentence?
Why would iterators be invalidated, but pointers/references would not be?

Thanks,

Scott

--
Scott Meyers, Ph.D.                  smeyers@aristeia.com
Software Development Consultant      http://www.aristeia.com/
Visit http://meyerscd.awl.com/ to demo the Effective C++ CD


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

On 11 Oct 1999 22:56:15 GMT, smeyers@aristeia.com (Scott Meyers) wrote:

:
: According to Josuttis' "The C++ Standard Library" (p. 163),
:
:   ...any insertion or deletion [in a deque] invalidates all pointers,
:   references, and iterators that refer to other elements of the deque.  The
:   exception is when elements are inserted at the front or the back.  In
:   this case, references or pointers to elements stay valid (but iterators
:   don't).
:
: What is the justification for the behavior described in this last sentence?
: Why would iterators be invalidated, but pointers/references would not be?

The standard says the same thing.  It is one of those implementation
details that materialize in the standard.  "The" deque is an array
of pointers to arrays of T.  Inserting in the middle moves things in
one direction or the other invalidating some pointers, references,
and iterators.  Can't tell which ones; therefor, all.  Inserting on
the ends could cause allocation of a new array of pointers.  The
pointers and references to T would remain valid; however, the iterators
would no longer be valid.

John


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Scott Meyers <smeyers@aristeia.com> wrote:

> According to Josuttis' "The C++ Standard Library" (p. 163),

>   ...any insertion or deletion [in a deque] invalidates all pointers,
>   references, and iterators that refer to other elements of the deque.  The
>   exception is when elements are inserted at the front or the back.  In
>   this case, references or pointers to elements stay valid (but iterators
>   don't).

> What is the justification for the behavior described in this last sentence?
> Why would iterators be invalidated, but pointers/references would not be?

The deque is a "map" of *constant size* blocks. The "map" is just a
random access container of pointers to those blocks:

 M -> [TTTT]
 M -> [TTTT]
 M -> [TTTT]
 M -> [TTTT]
 ^    ^
 |    |
 |    +- Constant size blocks
 |
 +- Map

Inserting a new element at either the front or the back, may require
allocating a new block. The block needs to be added to the map, which
may require relocating the map. Since the map needs to be pointed to by
iterators, they are invalidated.

The point of this data structure is to eliminate the need to copy the
stored elements when operations happen only at front and/or back (double
ended queue), which is a common situation. Using deque in other
situation may not be wise, because iteration, requiring conditionals, is
slower than for vector and can be slower than for list.

---
Vesa Karvonen


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]