Sign in to follow this  

Is end() guaranteed to be constant for a given STL container?

This topic is 3724 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

Can I safely set an STL container::iterator to container.end(), modify that container, and compare the iterator to container.end() afterwards? In other words, is container.end() guaranteed to be constant for a given STL container?

Share this post


Link to post
Share on other sites
no:


std::vector<int> myvec;

std::vector<int>::iterator it = myvec.begin();
std::vector<int>::iterator ite = myvec.end();
while ( it != ite )
{
if ( somecondition )
{
it = myvec.erase(it);
}
else
{
++it;
}
}




as soon as the .erase method is called, ite is invalidated and "hopefully" will result in a crash; unhopefully = undefined behavior i think. a non-crashy modification could be:


std::vector<int>::iterator it = myvec.begin();
while ( it != myvec.end() )
{
if ( somecondition )
{
it = myvec.erase(it);
}
else
{
++it;
}
}




-me

Share this post


Link to post
Share on other sites
each container's operations specify whether they invalidate iterators. For example if you insert or pushback on a vector the iterators are invalidated. For a list the iterators stay valid.

Share this post


Link to post
Share on other sites
It is not guaranteed to be constant but it depends on what modification you make to the container; some methods make assertions as to whether iterators will remain valid after the operation.

Just to show you an example of when end might move, imagine a vector of some size, in this case end points to a location 1-after the last element in the array, so now if you went and pushed or popped an element in the container then end would now point to a different location.

Share this post


Link to post
Share on other sites
Quote:
Original post by Glak
each container's operations specify whether they invalidate iterators. For example if you insert or pushback on a vector the iterators are invalidated. For a list the iterators stay valid.


ah yes. thank you. My example is vector (or any invalidating container) specific. the first example would work for a std::list

-me

Share this post


Link to post
Share on other sites
Fortunately, in my particular case, I'm using a std::list.

Am I then correct in assuming that once I've set a list::iterator to list.end(), it will always be equal to list.end(), no matter how much I might insert into, erase from, or clear that list?

Share this post


Link to post
Share on other sites
Don't go into some weird optimization.

If you need end iterator, call container.end().

There should be no noticeable performance penalty. Iterators are intended as temporary objects. Treat them as such.

Share this post


Link to post
Share on other sites
Nope, sorry. The obvious implementation that springs to my mind would satisfy that constraint, but it's definitely not required.

There is really no reason to worry about this. In the implementations where it *is* possible to treat std::list::end() that way, it's almost certainly because std::list::end() is very simple (e.g. constructs a structure with a pointer initialized to NULL and hands it back); simple enough that it will be inlined and then all the overhead iteratively stripped away in ordinary "peephole" optimization passes.

Share this post


Link to post
Share on other sites

This topic is 3724 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