Good practice? modifying vector while iterating through it

[Alan]

I was wondering whether it is good programming practice or asking
for trouble to modify a vector while iterating through it. That is, I
want to do something like the following pseudocode in C++:

for each element of the vector
for each subsequent element of the vector
if the belong together <some code to compare them>
then merge the elements (add the 2nd to the 1st, then
delete the 1st)

Does deleting an element before reaching it in the iteration mess up
the indexing and/or size of the vector, or do C++ compilers handle
this fine?

Thanks, Alan

 

[Kai-Uwe Bux]

I was wondering whether it is good programming practice or asking
for trouble to modify a vector while iterating through it.

Both

a) It is a little more complicated than just iterating through a vector.
b) Sometimes, it is just what you need to do.

That is, I
want to do something like the following pseudocode in C++:

for each element of the vector
for each subsequent element of the vector
if the belong together <some code to compare them>
then merge the elements (add the 2nd to the 1st, then
delete the 1st)

Do you mean delete the 2nd?

Does deleting an element before reaching it in the iteration mess up
the indexing and/or size of the vector, or do C++ compilers handle
this fine?

a) Deleting any element will change the size of the vector. Also the return
value of end() will change. The indexing will still run from 0 to size()-1
and the relative order of elements will not change. In that sense, C++
handles deletions within a vector (and indeed within any container) just
fine.


b) Calling erase on a vector invalidates all iterators, pointers, and
references to elements at and _behind_ the point of deletion. In
particular: if you really want to erase the lower-index element, you are in
trouble using iterators.

In any case, you will invalidate the inner iterator in your nested loop.
Thus, you will have to take special care. An idiom for erasing an element
within a loop for sequences is:

for ( sequence<int>::iterator iter = some_start_value;
iter != the_seq.end(); ) { // note the missing ++iter !
// do something
if ( we_do_not_erase ) {
++iter;
} else {
iter = the_seq.erase( iter );
}
}

It might be better to just use a running index and not an iterator. In this
case you have to keep in mind that you do not need to increment the index
when deleting the element (since the following element moves down).


c) On the other hand, erasing elements in the middle of a vector is costly
since all subsequent elements move. You might want to consider std::list<>
instead of std::vector. In this case, you will have to use iterators.



Best

Kai-Uwe Bux

 

[Alan]

Do you mean delete the 2nd? Oops, yes I did.

Thank you for your advice. Alan

 

[Andrew Koenig]

c) On the other hand, erasing elements in the middle of a vector is costly
since all subsequent elements move. You might want to consider std::list<>
instead of std::vector. In this case, you will have to use iterators.

Alternatively, instead of deleting elements from the vector, create a new
vector with just the elements that you want to keep. This technique avoids
the complexity and time overhead of deleting elements from the middle of the
vector, and the space overhead of using a list. It does create two copies
of the elements you keep, but that might be less than the space overhead for
a list, depending on how large the elements are.

 

[Alan]

Andrew,
Good idea. Thanks

 

[Grizlyk]

Alternatively, instead of deleting elements from the vector, create a new
vector with just the elements that you want to keep. This technique
avoids the complexity and time overhead of deleting elements from the
middle of the vector, and the space overhead of using a list. It does
create two copies of the elements you keep, but that might be less than
the space overhead for a list, depending on how large the elements are.

One can say concrete rules to compare list and vector. List adds size of one
or two pointers (assuming worst - two) in addition to size of type of its
object (for each object).