[C++] Optimize this method

This topic is 3157 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hello, i'm coding a vertical shooter like (i hope!) Ikaruga, e co. I've a method Called Update() that update the bullets coordinates and control if they must be deleted from the scene. I've write this method, but is horrible. Anyone can help me to optimize this?
 for(mBulletsVectorItr = mBulletsVector.begin();
mBulletsVectorItr != mBulletsVector.end();
++mBulletsVectorItr)
{
(*mBulletsVectorItr)->performShoot();
}
for(mBulletsVectorItr = mBulletsVector.begin();
mBulletsVectorItr != mBulletsVector.end();
++mBulletsVectorItr)
{
if((*mBulletsVectorItr)->getNode()->getPosition().z > 140.0f)
{
(*mBulletsVectorItr)->destroy();
mBulletsVector.erase(mBulletsVectorItr);
break;
}
}
I'm using Ogre3D. Another question is about the use of a Vector or a List for my shooting system. Thanks for your help and sorry for my english =).

Share on other sites
A couple of questions:
1. Why do you update all bullets and then do the erasure in a second loop? Why can't you just use one loop?
2. Why do you only want to remove one bullet each time?

It looks to me more like you want:
for(mBulletsVectorItr = mBulletsVector.begin(); mBulletsVectorItr != mBulletsVector.end();){   Bullet* pBullet = *mBulletsVectorItr;   pBullet->performShoot();   if(pBullet->getNode()->getPosition().z > 140.0f)   {      pBullet->destroy();      mBulletsVectorItr = mBulletsVector.erase(mBulletsVectorItr);   }   else      ++mBulletsVectorItr;}

Share on other sites
You could try something like:

mBulletsVectorItr = mBulletsVector.begin();while(mBulletsVectorItr != mBulletsVector.end()) {    YourBulletType& bullet = **mBulletsVectorItr;    bullet.performShoot();    if(bullet.getNode()->getPosition().z > 140.0f) {        bullet.destroy();        mBulletsVectorItr = mBulletsVector.erase(mBulletsVectorItr);    }    else        ++mBulletsVectorItr;}

std::vector<T>::erase returns a iterator to the element that followed the newly erased element, so you can use it to handle the iteration over your bullets when you need to delete one.

If you are deleting bullets frequently, you might be better served by a std::list<T>, as that has a O(1) erase method, while std::vector<T>'s is O(n).

(I am talking about the single-iterator versions of erase here).

Share on other sites
Thanks for your reply. I've used a single cicle, but when i delete a component into the vector the game crash. That's because i can't delete a vector's component into for cicle using a iterator. (sorry for my english!).

Another solution was that:

Bullet* b;    for(int i = 0; i < mBulletsVector.size(); ++i )    {        b = mBulletsVector;        if(b->getNode()->getPosition().z > 140.0f)        {            b->destroy();            mBulletsVector = mBulletsVector.back();            mBulletsVector.pop_back();            --i;        }        else           b->performShoot();    }

Share on other sites
Quote:
 Original post by mattdIf you are deleting bullets frequently, you might be better served by a std::list, as that has a O(1) erase method, while std::vector's is O(n).

Ok that's really important for me! In this case a list is more efficent than a vector? I need to insert and delete bullets in a very fast way. So what's the best solutions? I've a limited numbers of bullets on the screen..

Share on other sites
Quote:
Original post by Tano_ITA
Quote:
 Original post by mattdIf you are deleting bullets frequently, you might be better served by a std::list, as that has a O(1) erase method, while std::vector's is O(n).

Ok that's really important for me! In this case a list is more efficent than a vector? I need to insert and delete bullets in a very fast way. So what's the best solutions? I've a limited numbers of bullets on the screen..

Why don't you try profiling each and seeing for sure? You might find it doesn't make any difference in the long run, as it might just be premature optimization, especially if you only have a limited amount of bullets.

Also, did you notice this bit?:
Quote:
 std::vector::erase returns a iterator to the element that followed the newly erased element, so you can use it to handle the iteration over your bullets when you need to delete one.

If you original two-loops routine works, I don't see why me or Steve's versions wouldn't work either. If a bullet needs to be erased, we use this returned iterator to get to the next bullet, otherwise we just advance the iterator normally, by incrementing it.

Share on other sites
Quote:
 Original post by Tano_ITAThanks for your reply. I've used a single cicle, but when i delete a component into the vector the game crash. That's because i can't delete a vector's component into for cicle using a iterator. (sorry for my english!).
Your English is a lot better than some native English speakers I know [smile]

The problem is usually that you erase an element from a container and then increment the iterator instead of assigning it to the return value of erase() (As is done in mattd and my examples).

Quote:
Original post by Tano_ITA
Quote:
 Original post by mattdIf you are deleting bullets frequently, you might be better served by a std::list, as that has a O(1) erase method, while std::vector's is O(n).

Ok that's really important for me! In this case a list is more efficent than a vector? I need to insert and delete bullets in a very fast way. So what's the best solutions? I've a limited numbers of bullets on the screen..
If you need fast insertion and deletion, then std::list is a good choice.
If you need random access to the container, then std::vector would perhaps be better.
std::vector is only slow to add or remove from near the start. If the container doesn't need to be sorted, you could use a std::vector and only add at the end, and to remove an element you can swap it with the last element in the vector and pop_back().

Share on other sites
Ok thanks a lot. I will try to use each methods and i will see how is the best for my game. Thanks a lot for your suggets. I've a last question: Is better to use a mesh or a BillboardSet to represent the bullets on the screen?

thanks!

Share on other sites
If you really want to optimise your code then I would recommend you implement your own doubly-linked list class rather than using a vector. This way you can easily loop through the list, add and remove items at will.

However, if you're set on using STL vector class then you could perhaps have a 'to be destroyed' list. Then in the first loop when you encounter a bullet that needs to be destroyed add the bullet to the 'to be destroyed' list. Then instead of looping through every bullet in the original vector you can loop through and destroy all bullets in the new list.

Share on other sites
Quote:
 Original post by BoReDoM_IncIf you really want to optimise your code then I would recommend you implement your own doubly-linked list class rather than using a vector. This way you can easily loop through the list, add and remove items at will.

There's already std::list<T>, which I virtually guarantee would be more performant than anything most of the people here could write. This isn't meant to be an insult; it's just that the STL has a well designed list class already, and the implementation your STL vendor provides will be optimized for your specific compiler, well-tested and proven already.

Quote:
 However, if you're set on using STL vector class then you could perhaps have a 'to be destroyed' list. Then in the first loop when you encounter a bullet that needs to be destroyed add the bullet to the 'to be destroyed' list. Then instead of looping through every bullet in the original vector you can loop through and destroy all bullets in the new list.

Steve's method, overwriting the bullet that needs removing with the last bullet in the vector, and then pop_back'ing is easier, and about as fast as you're going to get. Your proposed list method doesn't meet the requirement that the bullets need to be removed from the vector after destruction.

• 11
• 20
• 12
• 10
• 35
• Forum Statistics

• Total Topics
631399
• Total Posts
2999857
×