[s0me0ne]

I was recently playing with std::list and its functions.

And i was doing something like this:

      for( iter = mylist.begin(); iter != mylist.end(); iter++ )
                if( ( *iter ).getdays() > cround ) // It will still exist on map
                    ( *iter ).factor();
                else mylist.erase( iter );

So i was getting a segmentation fault because i didnt know that when deleting an item in a list, the iterator is also deleted.
But i have randomly fixed it before by just doing iter++ inside the erase function. Heres the code:

    for( iter = mylist.begin(); iter != mylist.end(); iter++ )
                if( ( *iter ).getdays() > cround ) // It will still exist on map
                    ( *iter ).factor();
                else mylist.erase( iter++ );

But now that i know that about iterators, i cant see why it keeps working.( i tested with many items and everything is working perfectly )

Any explanation to this ?
Thanks in advance

[sepp2k]

At the point that the node is deleted, iter already points to the next node, so there is no problem. Note that iter++ increments iter to the next node and then returns an iterator (which is no longer connected to iter) that points to the old node.

[Karel-Lodewijk]

Yes this works and it is actually valid according to standards. I didn't understand why either until I actually tried to write an iterator.

So lets look at how an implementation of post-increment within an iterator might look.

iterator operator++(int) {
    iterator previous = *this;
    ++(*this);
    return previous;
}

Yes that is right, you create a copy of the iterator, then increment the current object and return the copy to the previous iterator. This copy is what makes it work, btw this copy is also why it is more efficient to use pre-increment in a loop.

list::erase invalidates only iterators pointing to the object you erase, no other iterators. So the iterator iter is still perfectly valid.

Don't try something similar on a std::vector for example. std::erase on a vector invalidates all iterators pointing to all elements after and including the first element that is erased.

This post has been edited by Karel-Lodewijk: 21 December 2011 - 11:07 AM

[s0me0ne]

Wow thanks for the really fast replies
I think i understood but let me check it.

What you two are saying is that when i do erase( iter++ ), i believe that i am incrementing the iterator but i am not really doing that. Because the original iter is incremented and then lost, but the backup of him ( which isnt incremented ) is returned ?

This post has been edited by s0me0ne: 21 December 2011 - 11:07 AM

[Karel-Lodewijk]

s0me0ne, on 21 December 2011 - 06:06 PM, said:

Wow thanks for the really fast replies
I think i understood but let me check it.

What you two are saying is that when i do erase( iter++ ), i believe that i am incrementing the iterator but i am not really doing that. Because the original iter is incremented and then lost, but the backup of him ( which isnt incremented ) is returned ?

No you are incrementing the iterator iter. But you don't call erase on iter, you call erase on a copy of iter, a copy that was made before iter was incremented.

[sepp2k]

You are incrementing the iterator. The iterator is not lost, it's still in the variable iter. However the iterator that gets passed to erase is not the incremented iterator that is stored in iter, but a copy of iter before it was incremented.

This is not much different from doing this:

int x = 3;
f(x++);

Here the value of x will be 4, but f is called with the argument 3 because the "return value" of x++ is the old value of x, not the incremented value of x.

[s0me0ne]

Karel-Lodewijk, on 21 December 2011 - 11:10 AM, said:

s0me0ne, on 21 December 2011 - 06:06 PM, said:

Wow thanks for the really fast replies
I think i understood but let me check it.

What you two are saying is that when i do erase( iter++ ), i believe that i am incrementing the iterator but i am not really doing that. Because the original iter is incremented and then lost, but the backup of him ( which isnt incremented ) is returned ?

No you are incrementing the iterator iter. But you don't call erase on iter, you call erase on a copy of iter, a copy that was made before iter was incremented.

Thinking of that, it shouldnt work. I am deleting a backup of iter, but the original iter is incremented? I also increment him at the for loop. So i should get back only items in positions 0,2,4,6 because every time i am incrementing the original iter twice.
I am a little confused sorry for that :S

[Karel-Lodewijk]

s0me0ne, on 21 December 2011 - 06:13 PM, said:

Karel-Lodewijk, on 21 December 2011 - 11:10 AM, said:

s0me0ne, on 21 December 2011 - 06:06 PM, said:

Wow thanks for the really fast replies
I think i understood but let me check it.

What you two are saying is that when i do erase( iter++ ), i believe that i am incrementing the iterator but i am not really doing that. Because the original iter is incremented and then lost, but the backup of him ( which isnt incremented ) is returned ?

No you are incrementing the iterator iter. But you don't call erase on iter, you call erase on a copy of iter, a copy that was made before iter was incremented.

Thinking of that, it shouldnt work. I am deleting a backup of iter, but the original iter is incremented? I also increment him at the for loop. So i should get back only items in positions 0,2,4,6 because every time i am incrementing the original iter twice.
I am a little confused sorry for that :S

I think your code does, I think you need to remove iter++ from your for loop. This code does:

#include <iostream>
#include <list>

int main() {
    std::list<int> mylist = {1,2,3,4,5,6,7,8,9,10};

    for(auto iter = mylist.begin(); iter != mylist.end(); iter++ ) {
                std::cout << *iter << std::endl;
                mylist.erase( iter++ );
    }
}

In fact this and your code is invalid. The double increment allows you to increment 2 past the end of the list which is undefined.

This post has been edited by Karel-Lodewijk: 21 December 2011 - 11:36 AM

[ishkabible]

just a note, most containers' operations invalidate all iterators. std::list dosn't do this because it is implemented as a linked list. you can't do the same thing with a vector or deque(or any of the containers that rely off of them such as stack and queue).

[Karel-Lodewijk]

ishkabible, on 21 December 2011 - 06:21 PM, said:

just a note, most containers' operations invalidate all iterators. std::list dosn't do this because it is implemented as a linked list. you can't do the same thing with a vector or deque(or any of the containers that rely off of them such as stack and queue).

That's somewhat of an overstatement. Only operations that remove elements, add elements or resize the container, can invalidate iterators. Which iterators is well documented and dependents on the container.

As I said, this wouldn't work for a vector, but it would work for set/multiset/map/multimap for example, this seems to summarize it nicely:

http://stackoverflow...alidation-rules

This post has been edited by Karel-Lodewijk: 21 December 2011 - 11:29 AM

[MirrorFish]

Karel-Lodewijk, on 21 December 2011 - 11:01 AM, said:

iterator operator++(int) {
    iterator previous = *this;
    ++(*this);
    return previous;
}

Hello,

Why operator++ in your example takes an "int" argument ?

Regards

[ishkabible]

good point, let me phase that "most containers' operations that add, remove or re-size". erase is such an operation so the code the OP presented would be such a case if it were not an std::list.

This post has been edited by ishkabible: 21 December 2011 - 11:31 AM

[Karel-Lodewijk]

MirrorFish, on 21 December 2011 - 06:29 PM, said:

Karel-Lodewijk, on 21 December 2011 - 11:01 AM, said:

iterator operator++(int) {
    iterator previous = *this;
    ++(*this);
    return previous;
}

Hello,

Why operator++ in your example takes an "int" argument ?

Regards

That's just the declaration of the post-increment (it++) operator.

iterator& operator++();

is the pre-increment iterator (++it) operator.

The int is to distinguish between the two, it has no other meaning.

This post has been edited by Karel-Lodewijk: 21 December 2011 - 11:33 AM

[s0me0ne]

Karel-Lodewijk, on 21 December 2011 - 11:16 AM, said:

In fact this and your code is invalid. The double increment allows you to increment 2 past the end of the array which is undefined.

Ok i fixed it and its working. Maybe i tested with numbers or cases that wouldnt have a problem. Thanks thanks thanks a lot both of you guys

[kragnoth]

The following is some code that I use to remove a string value if its greater in length than 5.

erase returns a new iterator, so what you can do is take the ++iterator out of your for loop, and put it into your conditionals.

Sorry for sloppy code, just cut and paste out of existing test code. Was messing around with iterators and list<string> commands.

for (list<string>::iterator it=testvector.begin(); it!=testvector.end(); )
	{
		if (it->size() > 5)
			it = testvector.erase(it);
		else
			++it;
		cout << *it << "\n";
	}