Vector Question

Originally Posted by Hunter2

While we're talking about erase-efficiency, why not use a std::list if you're just looping through the lasers?

K this is how my game works:

if you pressed space bar, creat a new instace of the class User_Laser

regardless of the first condition (space bar pressed) loop trought all the lasers and perform collision detection.

then loop through all the lasers again, but this time check if any of the have hit anything or are off the screen. If either is the case, delete this laser, then reset the counter(the goto) and go through the loop again, checking for obsolete lasers. I've noticed that this is *rather* memory intensive tho! I need to find a new way, but for the moment, this is what i'm doing.

Originally Posted by grib

In addition erase() is an expensive operation for a vector, but pop_back() is very cheap. Thus we can have a much faster version to remove lasers so long as we don't preserve order.

Alright, can I use this with my current code? All that does is swap the laser[i] with the last one, the remove the last one right?

Also, i could only get my vectors to work if I started my loop at, get this, 92. WTH? Whacked stuff

Thx for the help

Cheers

DW

>>does pop_back erase the last member or what?
Yes.

regardless of the first condition (space bar pressed) loop trought all the lasers and perform collision detection.

then loop through all the lasers again, but this time check if any of the have hit anything or are off the screen. If either is the case, delete this laser, then reset the counter(the goto) and go through the loop again, checking for obsolete lasers. I've noticed that this is *rather* memory intensive tho! I need to find a new way, but for the moment, this is what i'm doing.

Can't you loop just once?
Loop through - for each one: do collision detection; then check for hit or offscreen; if either, then delete it.

Why do you need to reset the counter? Can't you just keep going through the loop (decrease the counter by 1 and keep going)?
And even if you do need to, just set b = 0 or whatever it is.

It does sound like a list is more what you want than a vector. A vector is more appropriate if you need random access, meaning you have a laser that you know is at position 12, and you need to access it. (Note that even if you need that, a map might be better than a vector.)

Here is some example code for a list:

Code:

#include <iostream>
#include <list>

class User_Laser
{
    int data;
public:
    User_Laser(int start) : data(start) { }
    bool Obsolete() { return ++data > 5; }
};

void FireShot(std::list<User_Laser>& laserList, int start);
void EraseObsoleteLasers(std::list<User_Laser>& laserList);

int main()
{
    std::list<User_Laser> laserList;

    // fire some shots
    FireShot(laserList, 3);
    std::cout << "After fire: " << laserList.size() << std::endl;
    EraseObsoleteLasers(laserList);
    std::cout << "After erase: " << laserList.size() << std::endl;

    FireShot(laserList, 0);
    std::cout << "After fire: " << laserList.size() << std::endl;
    EraseObsoleteLasers(laserList);
    std::cout << "After erase: " << laserList.size() << std::endl;

    FireShot(laserList, 2);
    std::cout << "After fire: " << laserList.size() << std::endl;
    EraseObsoleteLasers(laserList);
    std::cout << "After erase: " << laserList.size() << std::endl;

    while (!laserList.empty())
    {
        EraseObsoleteLasers(laserList);
    }
    std::cout << "At the end: " << laserList.size() << std::endl;
}

void FireShot(std::list<User_Laser>& laserList, int start)
{
    laserList.push_back(User_Laser(start));
}

void EraseObsoleteLasers(std::list<User_Laser>& laserList)
{
    std::list<User_Laser>::iterator currentLaser = laserList.begin();
    std::list<User_Laser>::iterator pastEndLaser = laserList.end();
    while (currentLaser != pastEndLaser)
    {
        if (currentLaser->Obsolete())
            currentLaser = laserList.erase(currentLaser);
        else
            ++currentLaser;
    }
}

I used User_Laser objects instead of pointers because that is easier for me. Notice the last function - EraseObsoleteLasers. It allows you to check for obsolete lasers and erase them from the list. No need to go through the list more than once, and certainly no need for a goto. Similar code can be used for vectors (NOT the same, though, since an erase in a vector invalidates the end iterator I cached).

So, how much faster is a list than a vector? Is it worth it?

I don't know how complicated your code is, or how big your data structure will be during normal program operation, so it's hard to say. Chances are that you would never notice a difference.

It's more about choosing the most appropriate data structure for your needs. In this case, since you will be removing from the middle, a list would be more appropriate because it doesn't have the overhead of copying all the data after the removed object.

When you erase something from a vector, all of the values after that entry must be moved over one spot in memory using copying. For a list, only a couple of internal pointers need to be updated. If your vector only has 5-10 User_Laser's in it, you won't notice the speed difference. If that is the case, then it would be perfectly fine for you to decide that vectors are better for you because of other reasons (like being more familiar with them or not wanting to learn about lists now that you've been working on vectors).

Ah well, the vector has, at times, up wards of 20+ objects. Pretty much its how fast you can hit the space + control key! Also, I notice that it runs kinda slow... I have that code I posted running 3 times, one for missiles, one for laser, and one for baddy lasers. So do you figure that thats making the difference?

Cheers

DW

No, probably not. If anything, it's going to be either graphics or the constructor or hit detection or something else that's slowing it down, not the vector/list. Looping through a list or vector isn't slow at all, the only reason you would consider the number of elements is that with more, each loop has to keep going longer - which isn't normally a problem - or in the case of a vector, it'll take longer to do insert/erase operations in the middle/beginning of the vector. In the case of a list, it takes the same amount of time inserting/erasing from any part of the list, no matter how many elements there are.

Alright. Well I guess i'll keep with the vectors, as i'm used to working with them atm. I'll see if I can speed up the res of my code though...

Effective STL

Good book.

gg

Awsome, thx guys. Also, how do I do this, but with vectors?

Code:

    std::list<User_Laser>::iterator currentLaser = laserList.begin();
    std::list<User_Laser>::iterator pastEndLaser = laserList.end();

and how do I compare it against an int, such as,

Code:

for(i=currentLaser ; i < laser.size();i++
{

}

cheers

>Also, how do I do this, but with vectors?
Change the word list to vector.

>and how do I compare it against an int
You mean how do you extract an integral index from an iterator? By subtracting the current iterator from the first iterator in the sequence. The result is the distance between the two iterators in number of items:

Code:

for (int i = currentLaser - laser.begin(); i < laser.size(); i++) {
  ...
}

Unless you need the integer index for a specific reason, I would just use the iterators to access the data. The code compiles whether it is a list or a vector, so if you use the iterators it makes it easier to change your mind later.

There is one important note that I briefly referred to above. Erasing from a vector invalidates the iterators after it, so you can't cache the end() iterator. Here is that function for a vector:

Code:

void EraseObsoleteLasers(std::vector<User_Laser>& laserList)
{
    std::vector<User_Laser>::iterator currentLaser = laserList.begin();
    while (currentLaser != laserList.end())
    {
        if (currentLaser->Obsolete())
            currentLaser = laserList.erase(currentLaser);
        else
            ++currentLaser;
    }
}

Hmmm, I couldn't get that too work, so I tried somthing else, and that didn't work either. I declare my iterator up top, globlay,

Code:

std::vector<User_Laser*>::iterator currentLaser = laser.begin();

then I use it below

Code:

    while (currentLaser != laser.end())
    {
        if (currentLaser->Obsolete)
            currentLaser = laser.erase(currentLaser);
        else
            currentLaser++;
    }

but I get this error when I compile

Code:

[C++ Error] Unit1.cpp(127): E2288 Pointer to structure required on left side of -> or ->*

with the highlighting on the

Code:

if (currentLaser->Obsolete)

part

cheers


DW

Since your vector holds pointers (my example did not), then you must add one more dereference to your code:

Code:

void EraseObsoleteLasers(std::vector<User_Laser*>& laserList)
{
    std::vector<User_Laser*>::iterator currentLaser = laserList.begin();
    while (currentLaser != laserList.end())
    {
        if ((*currentLaser)->Obsolete())
            currentLaser = laserList.erase(currentLaser);
        else
            ++currentLaser;
    }
}

Also, setting the iterator globally is not a good idea, because the iterator returned from begin will change when you add things to the vector. It is better to set it in the function just before you use it. And finally, ++currentLaser is preferred over currentLaser++.

Wow...I must have reached some record for most help needed! lol.
thx for the quick answers guys, definatly I really appreciate it. I tried what you suggested jlou, but I get a "Call to non-function" at this line :

Code:

if ((*currentLaser)->Obsolete())

Oh... and why is ++i preffered over i++ ?

cheers

DW