Sign in to follow this  

C++: Can an iterator be negative?

This topic is 3599 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

So I'm iterating through a map to selectively delete stuff. The logic is:
std::map m;
std::map<>::iterator it;

for ( it = m.begin(); it != m.end(); ++it )
{
  if ( it.second == data )
  {
    m.erase( it );
    --it;
  }
}
My question involves what happens if the first element is deleted. For a brief moment 'it' will equal '-1'. It won't try to access this invalid iterator, as the next iteration of the loop will quickly change it back to '0', but I'm just wondering if it's valid to set an iterator to a negative number. (I'm not sure how iterators are implemented typewise)

Share this post


Link to post
Share on other sites
erase returns a valid iterator pointing after the object that was erased, which should be used (since erase will invalidate any current iterators).

So,

for ( it = m.begin(); it != m.end(); )
{
if ( it.second == data )
{
it = m.erase( it );
}

else
{
++it;
}
}

Share this post


Link to post
Share on other sites
The iterator is invalidated under such circumstances. Doing pretty much anything with them, other than calling the copy assignment operator (EDIT: i.e. assigning to such an invalidated iterator) or destructor invokes undefined behaviour.

Once the element is erased the iterator is left slack jawed and gormless; it doesn't know where the element has gone. It doesn't even no where *it* is, much less what's before or after it.

Do "it = container.erase(it);" instead.

Share this post


Link to post
Share on other sites
Using -- on the iterator returned by begin() for a container with bidirectional iterators has undefined behavior. It could work, or it could not work, depending on the implementation of the map. Unfortunately, in standard C++ std::map<>::erase() does not return the iterator to the next element, so you need to do something like:

for ( it = m.begin(); it != m.end();) {
if ( it.second == data ) {
std::map<>::iterator next = it;
++next; // need to increment iterator before erase so the iterator doesn't
// get invalidated
m.erase(it);
it = next;
} else {
++it;
}
}

Share this post


Link to post
Share on other sites
Thanks for the quick replies!

I did not realize that erase() returns an iterator. Is the reference on www.cppreference.com incorrect? It claims that erase() returns void:

http://www.cppreference.com/cppmap/erase.html

Share this post


Link to post
Share on other sites
Quote:
Original post by SiCrane
Unfortunately, in standard C++ std::map<>::erase() does not return the iterator to the next element, so you need to do something like:


Of note is that is you are using MSVC++, it is non-standard (for the better in this case, IMO).

Share this post


Link to post
Share on other sites
I'm using g++, so I'll just go with SiCrane's method to be safe. I generally like to follow the standards anyways.

Out of curiosity, does anybody know why the C++ standard doesn't have map.erase() return an iterator? It seems like it would make sense, and parallel the other containers better.

Share this post


Link to post
Share on other sites
The official answer is that having it return the iterator would be an unacceptable performance penalty if the return value isn't actually used. I find this claim to be a little fishy.

Also note, that the inside of the loop I showed can be written more succinctly as:

if ( it.second == data ) {
m.erase(it++);
} else {
++it;
}

The original version was written with the goal of clarity of what is going as a priority.

Share this post


Link to post
Share on other sites
Would std::remove_if work with map iterators? (I suppose it would end up modifying the .first of various "nodes" of the map, but since the order would be preserved, it should be ok?)

Share this post


Link to post
Share on other sites

This topic is 3599 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this