How do I properly pass iterator by reference?

Question

I have a game where I check collision between bullets and enemies which I store as 2 vector containers. People say if you're gonna erase an element in the for loop you better use iterators and so I did. But I have a problem now with passing the iterator to a function. The thing is I don't necessarily need to erase the element so it has to be a bit more complex.

This is the way I check collision. "CircularCollision" works fine, no mistakes there.

void ResolveColision(Weapon &weap, Map &map)
{
    std::vector<Bullet> bullets = weap.GetBullets();

    if (!bullets.empty())
    {
        for (std::vector<Bullet>::iterator i = bullets.begin(); i != bullets.end(); ++i)
        {
            std::vector<Enemy> enemies = map.GetEnemies();

            if (!enemies.empty())
            {
                for (std::vector<Enemy>::iterator j = enemies.begin(); j != enemies.end(); ++j)
                {
                    if (CircularCollision((*i), (*j)))
                    {
                        weap.DeleteByIndex(i);
                        map.TakeDamageByIndex(j, weap.GetDamage());
                        std::cout << "HIT!\n";
                    }
                }
            }
        }
    }
}

Here's the method which is supposed to decrease the health of an enemy:

void Map::TakeDamageByIndex(std::vector<Enemy>::iterator &itr, int damage)
{
   (*itr).SetHealth((*itr).GetHealth() - damage);
}

Here's the method which deletes the bullet:

void Weapon::DeleteByIndex(std::vector<Bullet>::iterator &itr)
{
    destroySprite((*itr).GetSprite());
    bullets.erase(itr);
}

I'm sure it looks horrible and it shouldn't work but I have no idea how to do it properly. Please help! Also, both methods work properly when the for loops operate with indexes (e.g. bullets[i]), in that case the problem is with "Vector subscript out of range" error.

Answer 1

You could do something like this:

void delByIndex(vector<int>::iterator &i, vector<int>& a)
{
    a.erase(i);
}   

int main()
{

    vector<int> a {1,5,6,2,7,8,3};
    vector<int> b {1,2,3,1};

    for(auto i=a.begin();i!=a.end();)
    {
        bool flag = false;
        for(auto j=b.begin();j!=b.end();j++)
            {
                if(*i==*j)
                {                    
                    flag = true;
                }
            }
            if(flag)
            {
                delByIndex(i, a);
            }
            else
                i++;

    }

    for(auto i:a)    
        cout << i << " ";


    return 0;
}

Be careful when using erase as it will change the size of the vector and also invalidates the vector iterator.

Answer 2

A few other comments in addition to Remy Lebeau’s answer.

It’s as efficient to pass a STL iterator by value as by reference, so the only reason you would need to pass one by reference is: when you intend to change the index and you want that change to be visible in the caller’s scope. (For example, a UTF-8 parser needs to consume anywhere from one to four bytes.) Since this code doesn’t need to do that, you’re better off just passing the iterator by value.

In general, if you aren’t modifying the variable you pass by reference, you should pass by const reference instead. In the case of Enemy::TakeDamage(), the only thing you do with the iterator is dereference it, so you might as well just pass in an Enemy& and call it with *i as the parameter.

The algorithm is not very efficient: if you delete a lot of items near the start of the list, you would need to move all remaining items of the array multiple times. This runs in O(N²) time. A std::list, although it has a high overhead compared to std::vector, can delete elements in constant time, and might be more efficient if you have a lot of insertions and deletions that are not at the end. You might also consider moving only the objects that survive to a new list and then destroying the old one. At least this way, you only need to copy once, and your pass runs in O(N) time.

If your containers store smart pointers to the objects, you only have to move the pointers to a new location, not the entire object. This will not make up for the overhead of lots of heap allocations if your objects are small, but could save you a lot of bandwidth if they are large. The objects will still be automatically deleted when the last reference to them is cleared.

Answer 3

In DeleteByIndex(), change this:

bullets.erase(itr);

To this:

itr = bullets.erase(itr);

std::vector::erase() returns an iterator to the next remaining element after the element that was erased. That next element is where your outer loop needs to continue from on its next iteration.

As such, you need to change your outer loop from a for to a while instead, or else you will skip elements (in fact, your original code suffers from that problem when you were still using indexes):

void ResolveColision(Weapon &weap, Map &map)
{
    std::vector<Bullet> bullets = weap.GetBullets();

    std::vector<Bullet>::iterator bullerItr = bullets.begin();
    while (bullerItr != bullets.end())
    {
        std::vector<Enemy> enemies = map.GetEnemies();
        bool wasAnyHit = false;

        for (std::vector<Enemy>::iterator enemyItr = enemies.begin(); enemyItr != enemies.end(); ++enemyItr)
        {
            if (CircularCollision(*bulletItr, *enemyItr))
            {
                wasAnyHit = true;
                weap.DeleteByIndex(bulletItr);
                map.TakeDamageByIndex(enemyItr, weap.GetDamage());
                std::cout << "HIT!\n";
                break;
            }
        }

        if (!wasAnyHit)
            ++bulletItr;
    }
}

---

That being said, I would suggest replacing the inner loop with std::find_if() instead. And renaming DeleteByIndex() and TakeDamageByIndex() since they don't take an index anymore. In fact, I would not pass an iterator to TakeDamage...() at all, pass the actual Enemy object instead. Or better, move TakeDamage() into Enemy itself.

Try something more like this:

void ResolveColision(Weapon &weap, Map &map)
{
    auto bullets = weap.GetBullets();

    auto bulletItr = bullets.begin();
    while (bulletItr != bullets.end())
    {
        auto enemies = map.GetEnemies();
        auto &bullet = *bulletItr;

        auto enemyHit = std::find_if(enemies.begin(), enemies.end(),
          [&](Enemy &enemy){ return CircularCollision(bullet, enemy); }
        );

        if (enemyHit != enemies.end())
        {
            weap.DeleteBulletByIterator(bulletItr);
            enemyHit->TakeDamage(weap.GetDamage());
            std::cout << "HIT!\n";
        }
        else
            ++bulletItr;
    }
}

void Enemy::TakeDamage(int damage)
{
   SetHealth(GetHealth() - damage);
}

void Weapon::DeleteBulletByIterator(std::vector<Bullet>::iterator &itr)
{
    destroySprite(itr->GetSprite());
    itr = bullets.erase(itr);
}