Vector Question

This is a discussion on Vector Question within the C++ Programming forums, part of the General Programming Boards category; Originally Posted by Hunter2 While we're talking about erase-efficiency, why not use a std::list if you're just looping through the ...

  1. #31
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    Quote 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.

    Quote 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
    Last edited by Death_Wraith; 06-04-2004 at 04:36 PM.

  2. #32
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    >>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.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  3. #33
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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).

  4. #34
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    So, how much faster is a list than a vector? Is it worth it?

  5. #35
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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).

  6. #36
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    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

  7. #37
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    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.
    Last edited by Hunter2; 06-05-2004 at 08:39 AM.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  8. #38
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    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...

  9. #39
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,669
    Effective STL

    Good book.

    gg

  10. #40
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    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

  11. #41
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >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++) {
      ...
    }
    My best code is written with the delete key.

  12. #42
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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;
        }
    }

  13. #43
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    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

  14. #44
    Registered User jlou's Avatar
    Join Date
    Jul 2003
    Posts
    1,088
    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++.

  15. #45
    Registered User
    Join Date
    Mar 2004
    Posts
    180
    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

Page 3 of 4 FirstFirst 1234 LastLast
Popular pages Recent additions subscribe to a feed

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21