vector modifiers and invalidation of iterators

[subramanian100in]

In the ISO/IEC 14882:2003 document, in page 492 section '23.2.4.3
vector modifiers', item 1 mentions the following:

"Notes: Causes reallocation if the new size is greater than old
capacity. If no reallocation happens, all the iterators and references
before the insertion point remain valid."

My questions:
---------------------
If reallocation happens, does the above 'Item 1' mean that all the
iterators, references and pointers to elements in the vector, will be
invalidated ?

To know whether reallocation has happened, we first need to store the
old capacity in a variable; then do the modification to the vector;
then check if the new size is greater than the variable value (which
gives the old capacity). Is this how we need to check if reallocation
has happened ? In real world applications, how is this accomplished ?
Kindly explain with some sample code.

Thanks
V.Subramanian

 

[Öö Tiib]

In the ISO/IEC 14882:2003 document, in page 492 section '23.2.4.3
vector modifiers', item 1 mentions the following:

"Notes: Causes reallocation if the new size is greater than old
capacity. If no reallocation happens, all the iterators and references
before the insertion point remain valid."

My questions:
---------------------
If reallocation happens, does the above 'Item 1' mean that all the
iterators, references and pointers to elements in the vector, will be
invalidated ?
Yes.

To know whether reallocation has happened, we first need to store the
old capacity in a variable; then do the modification to the vector;
then check if the new size is greater than the variable value (which
gives the old capacity). Is this how we need to check if reallocation
has happened ? In real world applications, how is this accomplished ?
Kindly explain with some sample code.

Kindly explain with example problem?

You can not solve all possible related problems with single tool or
technique.

On common case no one cares to detect if reallocation did happen and
when. Commonly iterators, references and pointers to elements of
vector are not stored somewhere for future reuse.

 

[Bo Persson]

In the ISO/IEC 14882:2003 document, in page 492 section '23.2.4.3
vector modifiers', item 1 mentions the following:

"Notes: Causes reallocation if the new size is greater than old
capacity. If no reallocation happens, all the iterators and
references before the insertion point remain valid."

My questions:
---------------------
If reallocation happens, does the above 'Item 1' mean that all the
iterators, references and pointers to elements in the vector, will
be invalidated ?

To know whether reallocation has happened, we first need to store
the old capacity in a variable; then do the modification to the
vector; then check if the new size is greater than the variable
value (which gives the old capacity). Is this how we need to check
if reallocation has happened ? In real world applications, how is
this accomplished ? Kindly explain with some sample code.

Most of the time you just don't care about storing iterators or
references to the vector elements, precisely beacuse they are
sometimes invalidated.

If you really DO care, you can bump up the capacity by calling
reserve() before adding any elements to the vector.



Bo Persson

 

[James Kanze]

In the ISO/IEC 14882:2003 document, in page 492 section '23.2.4.3
vector modifiers', item 1 mentions the following:

"Notes: Causes reallocation if the new size is greater than old
capacity. If no reallocation happens, all the iterators and references
before the insertion point remain valid."

My questions:
---------------------
If reallocation happens, does the above 'Item 1' mean that all the
iterators, references and pointers to elements in the vector, will be
invalidated ?
Yes.

To know whether reallocation has happened, we first need to store the
old capacity in a variable; then do the modification to the vector;
then check if the new size is greater than the variable value (which
gives the old capacity). Is this how we need to check if reallocation
has happened ? In real world applications, how is this accomplished ?
Kindly explain with some sample code.

In real world code, you don't dynamically test; if the vectors
might be invalidated, you just suppose they are, and get on with
it. In real world code, you sometimes to ensure that they won't
be invalidated, e.g. by calling reserve with a sufficiently
large value beforehand.

 

[TJorgenson]

In real world code, you don't dynamically test; if the vectors
might be invalidated, you just suppose they are, and get on with
it.  In real world code, you sometimes to ensure that they won't
be invalidated, e.g. by calling reserve with a sufficiently
large value beforehand.

Agreed, but I still find the OPs question interesting. Is testing the
capacity before and after calling a vector function that _could_
invalidate iterators a reliable way to determine if iterators were in
fact invalidated by the call? I mean is this technique guaranteed by
the standard?

Not that I would actually use such a technique...

Tony

 

[Francesco S. Carta]

Agreed, but I still find the OPs question interesting. Is testing the
capacity before and after calling a vector function that _could_
invalidate iterators a reliable way to determine if iterators were in
fact invalidated by the call? I mean is this technique guaranteed by
the standard?

I was about to say: "it is, because you can tell we had a reallocation
(invalidating the iterators) when you see that the capacity has changed"
but I believe it isn't: reallocation isn't the only thing that can
invalidate iterators - just imagine swapping that vector with another
one having the same capacity: only entry points have been swapped, no
reallocation has been made and no exception has been thrown, but still,
all the iterators got invalidated.

To mention another (non-working) way: even if checking that begin()
compares equal to a previously stored iterator pointing to the same
position will ensure that no reallocation has been made (and thus,
theoretically, all iterators would be "valid" in the sense that they
still point to memory belonging to that vector) some of those iterators
could still be "invalid" because they could point past the end of the
used slots.

Just imagine calling resize() to cut some elements out from the tail, no
reallocation, same capacity as before... and the worst thing, an
implementation could well let us write and read (using the subscript
operator or those "invalid" iterators) in the range up to capacity()-1
without any warning or error, at both compile and run time.

The safest thing is to completely avoid storing vector iterators,
eventually storing indexes instead. If one really needs to store them,
one has to take further protection steps (i.e. the call to reserve() as
suggested by James) and be well aware of the consequences of ALL the
operations made onto those vectors.

 

[James Kanze]

Agreed, but I still find the OPs question interesting. Is
testing the capacity before and after calling a vector
function that _could_ invalidate iterators a reliable way to
determine if iterators were in fact invalidated by the call?
I mean is this technique guaranteed by the standard?

There's no way to guarantee that the iterators are in fact
invalidated. But if the capacity doesn't change, iterators
pointing to elements before the insertion are guaranteed to not
be invalidated.

Note that you can check this before the insertion as well: if
size() + numberOfElementsToInsert <= capacity(), the insertion
won't invalidate iterators. This could be useful, since before
insertion, you could convert any iterators you had to indexes
(iter - container.begin()), and reconvert the indexes back to
iterators afterwards.

 

[subramanian100in]

In real world code, you don't dynamically test; if the vectors
might be invalidated, you just suppose they are, and get on with
it. In real world code, you sometimes to ensure that they won't
be invalidated, e.g. by calling reserve with a sufficiently
large value beforehand.

Thanks for your reply. Kindly clarify the following question related
to your reply.

Suppose I want to ensure that vector::insert() does not do
invalidation. To accomplish this, you have suggested to use
vector::reserve(sufficiently large value). But in this case also, if
this large value is greater than the old capacity, reallocation
happens. Am I correct ? But then, once reallocation happens all
iterators, pointers and references are invalidated. Is this
understanding of mine is correct ?

Thanks
V.Subramanian

 

[Bo Persson]

Thanks for your reply. Kindly clarify the following question related
to your reply.

Suppose I want to ensure that vector::insert() does not do
invalidation. To accomplish this, you have suggested to use
vector::reserve(sufficiently large value). But in this case also, if
this large value is greater than the old capacity, reallocation
happens. Am I correct ? But then, once reallocation happens all
iterators, pointers and references are invalidated. Is this
understanding of mine is correct ?

Yes, you should call reserve at a point where you don't have any
iterators or references into the vector, or you don't want to use them
again. One obvious point is when the vector is still empty.


Bo Persson