which container's iterator is competent

[breadbread1984]

I want a container whose iterator can pointer to the right element as long as the element stay in it.
I found that the iterator of a vector is invalidate immediate after I remove some element before the element which the iterator pointed to. I test it by

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	vector<int> v;
	for(int i = 0 ; i < 10 ; i++) v.push_back(i);
	vector<int>::const_iterator it1 = v.end() - 5;

	cout<<*it1<<endl;
	v.erase(v.begin());
	cout<<*it1<<endl;
}

I tried to replace the vector with deque in the above demo and got the right result. But I am still not sure about it. I wonder whether the deque is really the right choice for a competent container whose iterator pointers to the right element before the element is removed.

[Disch]

afaik the only container class whose elements are guaranteed not to move after insertion/deletion of elements is std::list.

Although maybe std::map and std::multimap have this trait as well -- I never actually checked. Of course map and list are not random access, so you can't do end() - 5 like that with their iterators. That's kind of the thing -- not moving around and random access are mutually exclusive.

This is something you'd have to look up for each container class. I'm pretty certain you can't use vector or deque like this -- both can move around elements at their will.

[jsmith]

I think all of the containers except std::vector<> and std::deque<> (and std::string, if you call it a container)
do not invalidate other iterators upon erase (only iterators to the erased element are invalidated).

Pretty much any container that is not implemented in whole or in part as a static or dynamically allocated
array. (std::deque<> can be thought of, for the purposes of this discussion, as std::list<std::vector<>>).

But the thing to watch out for is that an invalidated iterator cannot be incremented or decremented either
(it's not limited to just "dereferencing").