12.13.06

Going back to were we started

Posted in cplusplus at 9:43 pm by Fernando Cacciola

Consider the following straightforward C++ code:

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v));
copy(b,b+5,back_inserter(v));

Now suppose that we need an iterator range for the second batch insertion. That is, we need to know were the first element from ’b’ was inserted.
How could we do it?

Here’s a naive but tempting possibility

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v)); 

// Mark the place were the first ’b’ will be inserted
vector::iterator mark = v.end() ; 

copy(b,b+5,back_inserter(v)); 

// process from the point the first b was inserted
do_something(mark,v.end());

As right as that might appear to be, it has undefined behaviour in the case of a std::vector, even if .reserve() is called. Let me explain:

Inserting elements into a vector invalidates all iterators if and only if reallocation ocurrs. But a proper call to reserve() guarantees that reallocation won’t ocurr, so, to some extent, you don’t have to worry about invalidated iterators when appending into a vector which sufficient capacity. With one exception: the .end() iterator.

The reason is that after c.insert(pos,value), all elements from pos included need to be shifted up, so logically, all iterators >= pos become invalid, whether there is reallocation or not.

c.push_back(value); is equivalent to c.insert(c.end(),value), thus, clearly, end() is always invalid after insert() (thus push_back()) and erase().

OK, but what if the container is a std::list instead. After all list iterators are still valid after insertion/removal.
Well, this is still undefined behaviour because .end(), being still valid for a list, is allowed to keep pointing to the end of the list, so it cannot be assumed to become a valid iterator to the next element to be added.

The correct way to do it becomes ovbious if you consider the simplest case:

vector v ;
v.push_back(0);   

// How do I get an iterator to the lastly added element?
// Like this of course:
vector::iterator last = v.end();
-- last ;

Which extrapolates easily into the general case shown at the beggining:

vector v ;
int a[] = {0,1,2,3,4};
int b[] = {5,6,7,8,9};
copy(a,a+5,back_inserter(v));
copy(b,b+5,back_inserter(v));   

vector::iterator mark = v.end() ;
std::advance(mark,-5);   

// process from the point the first b was inserted
do_something(mark,v.end());

Leave a Comment