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

Hybrid View

  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,426

    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
    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?

  5. #5
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,328

    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.

  6. #6
    Join Date
    Apr 1999
    Posts
    27,426

    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

  7. #7
    Join Date
    Dec 2012
    Location
    England
    Posts
    2,328

    Re: Problems with iterators

    Quote Originally Posted by Paul McKenzie View Post
    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:artition() and erase(), and all of those problems that were plaguing that part of the code (for months) became resolved in less than 5 minutes.
    ...and the moral of the story is to know your STL algorithms!

    PS I wish that c++ tutors and books would remember the STL and give all of it the coverage it deserves - not just vectors, maps and i/o streams if you're lucky.
    Last edited by 2kaud; January 21st, 2014 at 11:59 AM.
    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.

  8. #8
    Join Date
    Apr 1999
    Posts
    27,426

    Re: Problems with iterators

    Quote Originally Posted by 2kaud View Post
    ...and the moral of the story is to know your STL algorithms!
    Since this is the Visual C++ forum, I would also like to mention that partition(), remove_if(), sort(), random_shuffle(), and most of the algorithms works for the MFC CArray class and all of the CxxxxArray container classes.

    A lot of people think STL is just about containers, not realizing there are a whole lot of algorithm functions that work on sequences of data, regardless of how the sequence is stored (array, vector, CArray, etc.).

    Regards,

    Paul McKenzie

  9. #9
    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...?

  10. #10
    Join Date
    Apr 1999
    Posts
    27,426

    Re: Problems with iterators

    Quote Originally Posted by Droopy View Post
    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
    The function object as I've written needs to be a global or static function, not a non-static member function.

    There is a way to get a non-static member function as part of the call, and that is to use std::mem_fun_ref to convert a pointer-to-member into a function object. It's a little advanced, but I will show you here:
    Code:
    if (innerHit)
    {
       sprites.erase(remove_if(sprites.begin(), sprites.end(), std::mem_fun_ref(&Enemy::hasCollided)), sprites.end());
    }
    This now calls your member function Enemy::hasCollided for each one of the sprites. If you still want the function to be more "local" and were not using Visual Studio 2013, you could do this using this method:
    Code:
    if (innerHit)
    {
       struct HasCollidedImpl { static bool HasCollided(Sprite* s) { return s->getCollided(); } };
       sprites.erase(remove_if(sprites.begin(), sprites.end(), &HasCollidedImpl::HasCollided), sprites.end());
    }
    The above creates a local struct with a static function that test for collision. You then feed the erase() function with the address of this function.

    Since you are using Visual Studio 2013, C++ now supports lambda functions -- these are local functions that you plug directly into the algorithm call (similar to example above). The difference is that C++ officially supports this. I haven't used the lambda functions, but I believe this should work:
    Code:
    if (innerHit)
    {
       sprites.erase(remove_if(sprites.begin(), sprites.end(), [](Sprite *s) { return s->getCollided(); }), sprites.end());
    }
    Note that the third argument to remove_if is an entire function body and not a pointer to a function or function object. The syntax is weird if you don't know lambda's, as they can have various options and can get advanced.

    Regards,

    Paul McKenzie

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

    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

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

    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.

  13. #13
    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

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

    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.

  15. #15
    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

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
  •  


Azure Activities Information Page

Windows Mobile Development Center


Click Here to Expand Forum to Full Width

This is a CodeGuru survey question.


Featured


HTML5 Development Center