0

I have 3 scenarios with c++ iterator which all together confused me.

Here's my main code:

int arr[] = {13,20,40};
set<int> st(arr,arr+3);

auto it=st.begin();
auto tmp=it;
it++;
st.erase(it);
//scenarios here

1- if I write the following, result is 20, why?

cout << *tmp << endl;

2- If I move pointer forward, result is 13, why?

tmp++;
cout << *tmp << endl;

3- If I move pointer backward, result is also 13, why it's same as moving forward?

tmp--;
cout << *tmp << endl;

4- Finally, if instead of erasing something from middle of set, I erase the start item, the result is a random number.

auto it=st.begin();
auto tmp = it;
st.erase(it);

cout << *tmp << endl;//result: 13

tmp++;
cout << *tmp << endl;//result: random number

If you know any useful link about iterators in c++ related to this issue, please mention them.

MehrdadAP
  • 417
  • 4
  • 11
  • 2
    the answer all questions is 'undefined behaviour' look up [iterator invaidation rules](http://stackoverflow.com/questions/6438086/iterator-invalidation-rules) – sp2danny Jul 23 '15 at 01:30
  • erase will remove the pointing node and return the iterator of the next node and assign to it. That's why you are getting 20 i.e. the value of next node. – paper.plane Jul 23 '15 at 01:37
  • @paper.plane, Actually I forgot to write it++ before erase part, I edited the code. It seems your guess is wrong cause the 20 is the value of iterator which is deleted already. – MehrdadAP Jul 23 '15 at 01:41
  • I agree the answer may be in the duplicate question, but I don't think it is duplicate because the answer don't explain the reason specific to this case clearly, at least I think the provided answer is too long, it is not beginner friendly to find which paragraph contains the answer for this case – ggrr Jul 23 '15 at 01:46
  • @amuse, Actually by reading explanations in proposed link, I fully understood it. It's completely reasonable when they say that's 'undefined behaviour', – MehrdadAP Jul 23 '15 at 01:54

2 Answers2

2

If you delete the entry in a set that an iterator points to, you have invalidated the iterator. Once an iterator has been invalidated, you should no longer user it, as it causes undefined behavior.

The Dark
  • 8,453
  • 1
  • 16
  • 19
  • I think it is lucky that the answer appeared before the question marked as duplicate – ggrr Jul 23 '15 at 01:37
0

First you don't mention your compiler. In a question like "how do I get C++ to do X,Y and Z" that is OK, but in a question like this where you ask why your program does not do what you expect you should specify compiler ( and version! ).

The reason is simple. First there may be a compiler bug which may cause certain code to not do what it is supposed to do. Second there are loose areas of the standard. For example in this case, there is no mention of how set is implemented, just how the interface is supposed to behave. So set can be implemented as a tree, an array, a hash table, whatever. Those behaviours change how set acts especially in "undefined" cases.

Second when you show multiple test cases, like here. it would be useful to separate the test cases with macros. 

#ifdef TEST1
   cout << *tmp << endl;
#endif
#ifdef TEST2
   tmp++;
   cout << *tmp << endl;
#endif
#ifdef TEST3
   tmp--;
   cout << *tmp << endl;
#endif

Generally you should avoid macros, but conditional compilation is one of the few exceptions to that rule.

So now on to your question.

First. I tend to use mostly vector, I tend to thing of iterators as C style pointers and ++ and -- as pointer arithmetic. It's hard to see how that is not the case for vector. but it is not always the case. It kind of messes with my instincts. Nevertheless it is a good picture to have in your head.

Just keep in mind that It's only mostly accurate. Depending on how set is implemented iterators will be different. In the case of a tree the iterator will be a pointer and ++ will be this->next and -- will be this->last.

Second. There are two types of collections. Collections ( which I will call basic collections ) which are based on "primitive" datatypes, and virtual collections which are things like directory listings or SQL Result Sets. In the first case, there is almost always a pointer hidden somewhere in the bowels of the iterator ( or not so deep ). Even in the second case, there is some sort of pointer like object ( a file descriptor/handle, a SQL Cursor ). So despite the fact that an iterator is put in an undefined state, it will still point to something. Though that thing might be invalid. It's like a character pointer which points to the wrong spot. There are still characters there, they just might be junk.

Third. To understand why iterators are made inconsistent when a collection changes, think about what you would have to do to create an iterator that remains consistent after a container change? First you would need an observer pattern implemented in the container and the iterator to let the iterator know when the container gets changed. An iterator is supposed to be a light weight object. This alone would cause at a doubling of iterator size. The message passing would add overhead when iterators are created.

The standards committee has a rule: any feature that you don't use should not have overhead when not used. That would mean you would need separate classes of at least a way to distinguish whether a container allows iterators that are consistent when the containers change. That would mean an extra level of complexity in the STL.

There is also the problem of how to fix an inconsistent iterator. Assume that the element pointed to by the iterator is deleted. What do you do? Go back one? Go forward one? What if the collection is unordered? Then changing the collection can cause the iteration order to be changed. How do you make sure that the iteratior hits all nodes?

Fourth. When doing something like this ( a teaching program ), it's a good idea to step through the code with a debugger to get an idea of what's going on inside.

Sorry it took so long. But the anwer was more complicated then I thought. That is not new for C++. Welcome to it.

TLOlczyk
  • 443
  • 3
  • 11