I've been wondering what 'iterator NOT invalidated' means. Does it
means that:

   (a) the adress of the designated object is not changed?
   (b) the reference return by e.g. iterator::operator*() does not
change?

Imagine a std::vector iterator implementation that uses a containter
pointer
and index and defines returnning reference by something like

   container->storage [index].

Now, if reallocation of 'storage' occurs without adding/deleting
new elements, objects are physically moved in memory, but the
references returned by iterators are still valid. So, is this iterator
invalidation or not? Are there actually any operations in STL
containers
that guaranties that objects are not moved phisically?

Radoslav Getov

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]

Radoslav Getov wrote:
>
> I've been wondering what 'iterator NOT invalidated' means. Does it
> means that:
>
>    (a) the adress of the designated object is not changed?
>    (b) the reference return by e.g. iterator::operator*() does not
> change?

It means that the iterator is still valid; it can still be used to refer
to the object.

> Imagine a std::vector iterator implementation that uses a containter
> pointer
> and index and defines returnning reference by something like
>
>    container->storage [index].
>
> Now, if reallocation of 'storage' occurs without adding/deleting
> new elements, objects are physically moved in memory, but the
> references returned by iterators are still valid. So, is this iterator
> invalidation or not? Are there actually any operations in STL
> containers
> that guaranties that objects are not moved phisically?

Yes: the standard in various cases specifies that certain actions do, or
do not, invalidate previously generated iterators, or pointers or
references into the objects that the iterators refer to. Sometimes it
only refers to iterators, or only to pointers and references, sometimes
to all three. I'm not entirely sure that the distinction between those
cases was always intentional. However, it's very clear that any
operation that is guaranteed to leave pointers valid, cannot be an
operation that moves the objects the pointers point at. I believe that's
also true of references. The technique you describe is acceptable any
time that it's only the iterators that are guarateed to remain invalid.
It doesn't work if the pointers and references derived from the iterator
are required to remain valid.

Since you meantioned std::vector<> in particular; here's summary of what
the standard says about iterator/pointer/reference validity. You'll note
that there's no case in which the iterators are guaranteed to remain
valid, but the pointers and references are not:

swap():  iterators, pointers, and references
remain valid.

erase(): pointers & refences
invalid after the point of erasure.

reallocation: iterators, pointers, and references
(can occur only in certain circumstances - see 23.2.4.2p2)
all become invalid

insert(): iterators and references
If no reallocation, remain valid for all elements before the insertion
point

---
[ 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://www.research.att.com/~austern/csc/faq.html                ]