Problems with iterators
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Problems with iterators

  1. #1
    Join Date
    Jan 2014
    Posts
    7

    Problems with iterators

    So I have this problem with not being able to iterate over a vector in a nestled for-loop. Here's the nestled for-loop:

    bool innerHit = false;
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
    {
    Sprite* spriteOne = *outerIter;
    for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
    {
    Sprite* spriteTwo = *innerIter;
    if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
    {
    spriteOne->collisionReaction(spriteTwo);
    spriteTwo->collisionReaction(spriteOne);
    spriteOne->collisionDestroy(sprites);
    spriteTwo->collisionDestroy(sprites);
    innerHit = true;
    }
    if (innerHit)
    break;
    }
    }

    What happens is, after having called the collisionDestroy-function and the program tries to execute the nest loop in the outer for-loop, it all crashes with the text "Expression: vector iterator not decrementable", which I understand is because the iterator will have already become useless. The question is: know this, how do I fix it? I can't seem to get a hang of it.

    Here's the collisionDestroy-function (the collisionReaction does nothing but sets a few local variables):

    void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
    {
    for (std::vector<Sprite*>::iterator iter = sprites.begin(); iter != sprites.end(); iter++)
    {

    Enemy* tmp = dynamic_cast<Enemy*>(*iter);
    if (this == tmp && collisionType == 3 || collisionType == 1)
    {
    sprites.erase(iter);
    break;
    }
    }
    }

  2. #2
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    And sorry for the lack of indentation.

  3. #3
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Problems with iterators

    Quote Originally Posted by Droopy View Post
    So I have this problem with not being able to iterate over a vector in a nestled for-loop. Here's the nestled for-loop:
    1) Use code tags when posting code. The code you posted is almost unreadable.

    2) Your post is plain C++, i.e. there is no use of MFC, ATL, or other technologies relevant to the usage of the Visual C++ compiler. It is straight C++, with a few types such as "Sprite" that we don't know about. Therefore it would have been relevant to post in the non-Visual C++ forum.

    For everyone's benefit, here is your code, formatted using code tags:
    Code:
    bool innerHit = false;
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
    {
        Sprite* spriteOne = *outerIter;
        for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
        {
            Sprite* spriteTwo = *innerIter;
            if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
           {
                spriteOne->collisionReaction(spriteTwo);
                spriteTwo->collisionReaction(spriteOne);
                spriteOne->collisionDestroy(sprites);
                spriteTwo->collisionDestroy(sprites);
                innerHit = true;
            }
            if (innerHit)
                break;
        }
    }
    There is no need to write loops like this if you know what the ultimate goal is when it comes to proper usage of containers. The way you rewrite this entire sequence is to use algorithms from the STL that alters the container in a safe way.
    Here's the collisionDestroy
    Here is the problem. It calls
    Code:
    std::vector<Sprite*>::erase()
    which is a very big issue.

    Let's start at the beginning:
    Code:
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
    The above has the issue of being inefficient and very hard to read. First, it would be a lot easier if you used typedef:
    Code:
    typedef std::vector<Sprite*> SpriteVector;
    //...
    for (SpriteVector::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); ++outerIter)
    Note how we typedef'ed the vector, and we use pre-increment in the outerIter loop variable.

    Now we see that you are erasing items in the vector while you're looping (see the item in red). Whenever I see this, I can bet you had to write this loop and your inner loop (which has the same sort of checking) 2, 3, 4, or more times to get working in some manner, all due to bugs being discovered. The goal, if possible, is to not write loops that erase items in a container while looping within the container. This is especially the case for a simple container such as vector. There are very few times when you need to erase elements in a vector while looping over the vector.

    The way you go about doing erasures in a vector is to arrange the items in the vector so that the "erased" items appear at the end of the container, with an iterator pointing to the beginning of the erased items so that you can safely call erase() in a separate step starting at this iterator. Again, usage of remove_if() / erase or std::partition() and erase() is recommended.

    The easiest way to overcome this is in your Sprite class, have a simple bool member variable that sets whether this sprite has been destroyed (make sure you initialize this variable when you create a sprite to false). Then just set this boolean to true in your collisionDestroy method -- do not erase the item in the vector -- in effect, you're delaying the real erasure of the items for later. In your other loops above, you skip over the ones that have this bool variable set to true -- that is much easier than figuring out what is empty and potentially accessing an invalid iterator. Now, you are no longer erasing items in the middle of the loop which means your loop constraints need no longer check for invalid iterators, since they will always be valid.
    Code:
    void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
    {
        for (SpriteVector::iterator iter = sprites.begin(); iter != sprites.end(); ++iter)
        {
            Enemy* tmp = dynamic_cast<Enemy*>(*iter);
            if (this == tmp && collisionType == 3 || collisionType == 1)
            {
                tmp->hasCollided = true;
    	    break;
    	}
        }
    }
    I changed the code so that we no longer erase, but just set the boolean. But this can also be rewritten, again, using algorithms (and why did you need to cast to Enemy??)
    Code:
    void Enemy::collisionDestroy(SpriteVector& sprites)
    {
        if ( collisionType == 1 || collisionType == 3)              
        {
            SpriteVector::iterator it = find(sprites.begin(), sprites.end(), this);
            if ( it != sprites.end() )
               it->hasCollided = true;  
         }
    }
    If the goal was to find the sprite that equaled "this", and then erase it, then the above code should work.

    Then in a separate step afterwards, outside of all of these loops, you use the remove_if() / vector::erase idiom.
    Code:
    #include <algorithm>
    
    bool hasCollided(Sprite* sprite)
    {
       return sprite->isCollided();  // this is just a public "getter" for the hasCollided flag that was set earlier.
    }
    //...
    void Enemy::RemoveCollided()
    {
        sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
    }
    Problem solved, or at least, made easier. The above checks the vector and erases all the ones that have the "hasCollided" flag set to true. Basically, all I did was come up with a scheme to invalidate the item (setting a simple bool member), and then at the end, erase the invalidated items.

    (Note that I am using C++ 98 features, and not C++ 11. If I knew you were using C++ 11 (or Visual Studio 2013), then the RemoveCollided would make use of lamda's in the remove_if() call instead of a separate function such as hasCollided).

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 21st, 2014 at 02:49 AM.

  4. #4
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,572

    Re: Problems with iterators

    The basic problem, put simply, is that .erase() invalidates any iterators for that vector so shouldn't really be used within an iterator loop.

    See http://www.cplusplus.com/reference/vector/vector/erase/

    There are ways of making .erase work in an iterator loop but I won't detail them here as they are not recommended and can make code maintenance a nightmare. The method suggested by Paul is the way to go about this. Depending upon how the vector is used, you might not need to actually remove the elements, just have them marked as collided and other code can use hasCollided().
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  5. #5
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    Quote Originally Posted by Paul McKenzie View Post
    1) Use code tags when posting code. The code you posted is almost unreadable.

    2) Your post is plain C++, i.e. there is no use of MFC, ATL, or other technologies relevant to the usage of the Visual C++ compiler. It is straight C++, with a few types such as "Sprite" that we don't know about. Therefore it would have been relevant to post in the non-Visual C++ forum.

    For everyone's benefit, here is your code, formatted using code tags:
    Code:
    bool innerHit = false;
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
    {
        Sprite* spriteOne = *outerIter;
        for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend() && (!sprites.empty()); innerIter++)
        {
            Sprite* spriteTwo = *innerIter;
            if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
           {
                spriteOne->collisionReaction(spriteTwo);
                spriteTwo->collisionReaction(spriteOne);
                spriteOne->collisionDestroy(sprites);
                spriteTwo->collisionDestroy(sprites);
                innerHit = true;
            }
            if (innerHit)
                break;
        }
    }
    There is no need to write loops like this if you know what the ultimate goal is when it comes to proper usage of containers. The way you rewrite this entire sequence is to use algorithms from the STL that alters the container in a safe way.
    Here is the problem. It calls
    Code:
    std::vector<Sprite*>::erase()
    which is a very big issue.

    Let's start at the beginning:
    Code:
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); outerIter++)
    The above has the issue of being inefficient and very hard to read. First, it would be a lot easier if you used typedef:
    Code:
    typedef std::vector<Sprite*> SpriteVector;
    //...
    for (SpriteVector::iterator outerIter = sprites.begin(); outerIter != sprites.end() && (!sprites.empty()); ++outerIter)
    Note how we typedef'ed the vector, and we use pre-increment in the outerIter loop variable.

    Now we see that you are erasing items in the vector while you're looping (see the item in red). Whenever I see this, I can bet you had to write this loop and your inner loop (which has the same sort of checking) 2, 3, 4, or more times to get working in some manner, all due to bugs being discovered. The goal, if possible, is to not write loops that erase items in a container while looping within the container. This is especially the case for a simple container such as vector. There are very few times when you need to erase elements in a vector while looping over the vector.

    The way you go about doing erasures in a vector is to arrange the items in the vector so that the "erased" items appear at the end of the container, with an iterator pointing to the beginning of the erased items so that you can safely call erase() in a separate step starting at this iterator. Again, usage of remove_if() / erase or std:artition() and erase() is recommended.

    The easiest way to overcome this is in your Sprite class, have a simple bool member variable that sets whether this sprite has been destroyed (make sure you initialize this variable when you create a sprite to false). Then just set this boolean to true in your collisionDestroy method -- do not erase the item in the vector -- in effect, you're delaying the real erasure of the items for later. In your other loops above, you skip over the ones that have this bool variable set to true -- that is much easier than figuring out what is empty and potentially accessing an invalid iterator. Now, you are no longer erasing items in the middle of the loop which means your loop constraints need no longer check for invalid iterators, since they will always be valid.
    Code:
    void Enemy::collisionDestroy(std::vector<Sprite*>& sprites)
    {
        for (SpriteVector::iterator iter = sprites.begin(); iter != sprites.end(); ++iter)
        {
            Enemy* tmp = dynamic_cast<Enemy*>(*iter);
            if (this == tmp && collisionType == 3 || collisionType == 1)
            {
                tmp->hasCollided = true;
    	    break;
    	}
        }
    }
    I changed the code so that we no longer erase, but just set the boolean. But this can also be rewritten, again, using algorithms (and why did you need to cast to Enemy??)
    Code:
    void Enemy::collisionDestroy(SpriteVector& sprites)
    {
        if ( collisionType == 1 || collisionType == 3)              
        {
            SpriteVector::iterator it = find(sprites.begin(), sprites.end(), this);
            if ( it != sprites.end() )
               it->hasCollided = true;  
         }
    }
    If the goal was to find the sprite that equaled "this", and then erase it, then the above code should work.

    Then in a separate step afterwards, outside of all of these loops, you use the remove_if() / vector::erase idiom.
    Code:
    #include <algorithm>
    
    bool hasCollided(Sprite* sprite)
    {
       return sprite->isCollided();  // this is just a public "getter" for the hasCollided flag that was set earlier.
    }
    //...
    void Enemy::RemoveCollided()
    {
        sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
    }
    Problem solved, or at least, made easier. The above checks the vector and erases all the ones that have the "hasCollided" flag set to true. Basically, all I did was come up with a scheme to invalidate the item (setting a simple bool member), and then at the end, erase the invalidated items.

    (Note that I am using C++ 98 features, and not C++ 11. If I knew you were using C++ 11 (or Visual Studio 2013), then the RemoveCollided would make use of lamda's in the remove_if() call instead of a separate function such as hasCollided).

    Regards,

    Paul McKenzie
    Thank you! For the record, i AM using Visual Studio 2013/C++11. What would you change knowing that?

  6. #6
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    Still not working. Now I get the following error: Error 1 error C3867: 'Sname::Engine::hasCollided': function call missing argument list; use '&Sname::Engine::hasCollided' to create a pointer to member c:\users\johan\documents\visual studio 2013\projects\project3\project3\engine.cpp 100 1 Project3

    The loops now look like this:

    Code:
    bool innerHit = false;
    for (std::vector<Sprite*>::iterator outerIter = sprites.begin(); outerIter != sprites.end(); outerIter++)
    {
    	Sprite* spriteOne = *outerIter;
    	for (std::vector<Sprite*>::reverse_iterator innerIter = sprites.rbegin(); innerIter != sprites.rend(); innerIter++)
    	{
    		Sprite* spriteTwo = *innerIter;
    		if (spriteOne->getRect() != spriteTwo->getRect() && spriteOne->getRect().overlaps(spriteTwo->getRect()) && spriteOne != spriteTwo)
    		{
    			spriteOne->collisionReaction(sprites, spriteTwo);
    			spriteTwo->collisionReaction(sprites, spriteOne);
    			innerHit = true;
    		}
    	}
    }
    if (innerHit)
    {
    	sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
    }
    And then there's the hasCollided-function in the same class as the loops (the Engine-class):

    Code:
    bool Engine::hasCollided(Sprite* sprite)
    {
    	return sprite->getCollided();
    }
    The collisionReaction-function in Enemy (which enherits from Sprite) now looks like this:

    Code:
    void Enemy::collisionReaction(std::vector<Sprite*>& sprites, Sprite* other)
    {
    	std::vector<Sprite*>::iterator it = find(sprites.begin(), sprites.end(), this);
    	if (it != sprites.end())
    		(*it)->setCollided(true);
    	}
    }
    Any idea...?

  7. #7
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,629

    Re: Problems with iterators

    1) Some notes:

    Code:
    sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());
    where sprites is a std::vector<Sprite*>

    I assume that the elements of vector were created using new. If so, you
    have a memory leak (unless I missed the delete somewhere)

    2) You can use auto to declare the type of the loop variable:

    Code:
    for (auto iter = sprites.begin(); iter != sprites.end(); ++iter)
    3) You can use range based for loops. Examples:

    Code:
    for (Sprite * p : sprites) {  }
    for (auto p : sprites) { }
    for (auto & p : sprites) { }
    for (const Sprite * p : sprites) {  }
    see http://msdn.microsoft.com/en-us/libr...v=vs.110).aspx

  8. #8
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,629

    Re: Problems with iterators

    Generally, the functor (hasCollided in your code), is a stand-alone function, not a member
    function (or it is a static member function). There is a syntax to use if it is a member
    function (which I don't recall off the top of my head). I think that is what the

    use '&Sname::Engine::hasCollided'

    is stating.

  9. #9
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    I changed it to:

    Code:
    if (innerHit)
    {
    	sprites.erase(remove_if(sprites.begin(), sprites.end(), &Sname::Engine::hasCollided), sprites.end());
    }
    Now it says:

    Error 1 error C2064: term does not evaluate to a function taking 1 arguments c:\program files (x86)\microsoft visual studio 12.0\vc\include\algorithm 1758 1 Project3

  10. #10
    Join Date
    Aug 2000
    Location
    West Virginia
    Posts
    7,629

    Re: Problems with iterators

    I don't see a reason why you can not make it a stand-alone function
    or a static member function.

  11. #11
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    I just solved it! Thanks Philip

    And also, thank you Paul McKenzie! You're seriously the coolest guy ever

  12. #12
    Join Date
    Jan 2014
    Posts
    7

    Re: Problems with iterators

    By the way, do any of you guys have a great link to where I can learn more about this: sprites.erase(remove_if(sprites.begin(), sprites.end(), hasCollided), sprites.end());? I get sprites.erase and remove_if, but not together, and not with the sprites.end() at the end.
    Last edited by Droopy; January 21st, 2014 at 09:18 AM.

  13. #13
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,572

    Re: Problems with iterators

    I can suggest these books

    Accelerated c++ (c++98)
    http://www.amazon.co.uk/Accelerated-...erated+c%2B%2B
    Gives good examples of how to use the STL containers, algorithms etc

    Professional c++ (v2 covers c++11)
    http://www.amazon.co.uk/Professional...sional+c%2B%2B

    The c++ Standard Libray: A Tutorial and Reference (v2 covers c++11)
    http://www.amazon.co.uk/The-Standard...andard+library

    Effective STL (c++98)
    http://www.amazon.co.uk/Effective-ST...=effective+stl

    Also
    http://www.cplusplus.com/reference/
    http://en.cppreference.com/w/cpp
    All advice is offered in good faith only. You are ultimately responsible for effects of your programs and the integrity of the machines they run on.

  14. #14
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Problems with iterators

    Quote Originally Posted by Droopy View Post
    I just solved it! Thanks Philip :)
    Make sure that if those Sprite pointers are pointing to allocated memory using "new", that instead you want to partition the collided items first, delete them, and then remove them.
    Code:
    void Enemy::RemoveCollided()
    {
        // partition items -- items satisfying the condition will go on the left of the partition, otherwise go 
        // to right of partition
        SpriteVector::iterator itEnd = std::partition(sprites.begin(), sprites.end(), hasCollided);
        SpriteVector::iterator it = sprites.begin();
        // call delete on each item that has collided
        while (it != itEnd)
        {
            delete (*it);
            ++it;
        }
    
        // erase them from the vector
        sprites.erase(sprites.begin(), itEnd);
    }
    Basically, partition does the same as remove_if() -- items satisfying the condition are placed on the right, else on the left of the partition. The partition is the iterator that is returned by std::partition.

    The difference between partition and remove_if is that partition just moves items around, but those items are still valid. The remove_if() not only moves the items to the end, but also makes them garbage values. So you don't want to do a straight remove_if() if you need to delete them first.

    If you want to keep the same order, then use std::stable_partition instead of partition.

    Regards,

    Paul McKenzie
    Last edited by Paul McKenzie; January 21st, 2014 at 10:54 AM.

  15. #15
    Join Date
    Apr 1999
    Posts
    27,434

    Re: Problems with iterators

    Quote Originally Posted by 2kaud View Post
    There are ways of making .erase work in an iterator loop but I won't detail them here as they are not recommended and can make code maintenance a nightmare.
    At one of my jobs, the programmers there were doing basically the same thing as the OP. They could never figure out how to erase from a vector while looping -- you should have seen the creative ways that were done, all would eventually fail. Things like jumping over invalidated iterators, reseating the iterator, all sorts of things that made it a nightmare to maintain and work consistently.

    I introduced them to std::partition() and erase(), and all of those problems that were plaguing that part of the code (for months) became resolved in less than 5 minutes.

    Regards,

    Paul McKenzie

Page 1 of 2 12 LastLast

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center