Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What happens if you increment an iterator that is equal to the end iterator of an STL container

What if I increment an iterator by 2 when it points onto the last element of a vector? In this question asking how to adjust the iterator to an STL container by 2 elements two different approaches are offered:

  • either use a form of arithmetic operator - +=2 or ++ twice
  • or use std::advance()

I've tested both of them with VC++ 7 for the edge case when the iterator points onto the last element of the STL container or beyond:

vector<int> vec; vec.push_back( 1 ); vec.push_back( 2 );  vector<int>::iterator it = vec.begin(); advance( it, 2 ); bool isAtEnd = it == vec.end(); // true it++; // or advance( it, 1 ); - doesn't matter isAtEnd = it == vec.end(); //false it = vec.begin(); advance( it, 3 ); isAtEnd = it == vec.end(); // false 

I've seen may times an advise to compare against vector::end() when traversing the vector and other containers:

for( vector<int>::iterator it = vec.begin(); it != vec.end(); it++ ) {     //manipulate the element through the iterator here } 

Obviously if the iterator is advanced past the last element inside the loop the comparison in the for-loop statement will evaluate to false and the loop will happily continue into undefined behaviour.

Do I get it right that if I ever use advance() or any kind of increment operation on an iterator and make it point past the container's end I will be unable to detect this situation? If so, what is the best practice - not to use such advancements?

like image 716
sharptooth Avatar asked Jun 29 '09 11:06

sharptooth


People also ask

What happens if you increment the iterator past the end?

Obviously if the iterator is advanced past the last element inside the loop the comparison in the for-loop statement will evaluate to false and the loop will happily continue into undefined behaviour.

What does the end iterator point to?

In something like an std::vector the ::end() iterator will point to one past the last element. You can't dereference this iterator but you can compare it to another iterator. If you compare another iterator to end() you know you've reached the end of the container.

Can you dereference end iterator?

In C++, you cannot dereference an iterator straight away because the end() function returns an iterator and object as a pointer, which isn't a valid member of the data structure.

Can you decrement end iterator?

It appears that you can still decrement the iterator returned from end() and dereference the decremented iterator, as long as it's not a temporary.


2 Answers

Following is the quote from Nicolai Josuttis book:

Note that advance() does not check whether it crosses the end() of a sequence (it can't check because iterators in general do not know the containers on which they operate). Thus, calling this function might result in undefined behavior because calling operator ++ for the end of a sequence is not defined

In other words, the responsibility of maintaining the iterator within the range lies totally with the caller.

like image 188
Naveen Avatar answered Oct 11 '22 15:10

Naveen


Perhaps you should have something like this:

template <typename Itr> Itr safe_advance(Itr i, Itr end, size_t delta) {     while(i != end && delta--)         i++;     return i; } 

You can overload this for when iterator_category<Itr> is random_access_iterator to do something like the following:

return (delta > end - i)? end : i + delta; 
like image 25
Motti Avatar answered Oct 11 '22 17:10

Motti