Thread: Vector Question

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

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

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