Archived

This topic is now archived and is closed to further replies.

VanKurt

How to work with < vector> correctly ?

Recommended Posts

I''m wondering how to use the STL vector right. Until now I''ve been using it for everything: Enemies, Bullets, whatever. Like this: for( i=0; i.Move(); if( EnemyVector[i].health < 0 ) EnemyVector.erase( EnemyVector.begin() + i ); } This works almost correctly, but sometimes is buggy (objects don''t move, collisions aren''t detected etc.). So I''m asking myself what''s wrong here...is it possible that when I call erase() the array gets resized so that there is a problem with the number of iterations? May objects be overseen? What do I have to take care of/ be careful with when using this vector-class? What could cause such bugs??? Thanks for your hel!

Share this post


Link to post
Share on other sites
Erasing elements from the middle of a vector isn''t a good usage scenario, you should be using a list for something like this.

Your theory about the vector being resized is quite possibly correct as well although the simple fact that erase() invalidates the iterator should be reason enough for things to mess up.

I''d really recommend using a list, they''re not much different and you can have better support for the usage you seem to want.

-Mezz

Share this post


Link to post
Share on other sites
More information that you could ever possibly use on the STL:

http://www.sgi.com/tech/stl/stl_index.html

In here, they'll tell you that (1) calling erase() does invalidate vector iterators, and that erasing from a vector is O(n), which means takes some amount of time multiplied by the number of elements to finish.

They'll also tell you that (2) a list can erase() with only invalidating iterators that point to the thing you just erased, and that erasing from a list always takes the same short amount of time, whether you have two elements or two thousand.

Generally, vector is good when you have jump around a lot in the indices of items you're looking at but only ever add or remove items from the end, and list is good if you want to remove or insert items anywhere, but will only be iterating straight through from one end of it to the other.

One more thing -- there are a couple classes in that reference which are SGI extensions to the STL. Don't use them (unless you have SGI header files lying around somewhere)!

edit: oops... didn't like my angle-brackets 'round "vector" and "list".

[edited by - CautionMan on March 18, 2004 8:39:01 PM]

Share this post


Link to post
Share on other sites
Your code seems to be missing a loop condition, also watch out for using i as an index variable because the boards interpret [letter_i] as an italics tag. Without the loop condition it's not totally clear what your problem is but it looks like you are erasing an element and then advancing i which means you will skip over the element after the element you erased (because when you erase the ith element the i+1th element becomes the ith element but you increment i and so never look at that element).

The correct way to code the loop would be:

EnemyVector::iterator it = EnemyVector.begin();
while(it != EnemyVector.end())
{
it->Move();
if(it->health < 0)
{
it = EnemyVector.erase(it);
}
else
{
++it;
}
}


[edited by - mattnewport on March 19, 2004 1:05:02 AM]

Share this post


Link to post
Share on other sites
(mattnewport''s suggestion will usually work - vector iterators are usually implemented as pointers - but since the standard says that the iterator is invalidated after an erase this code might not work on all standard library implementations. furthermore, vector.erase is still horribly inefficient and should be avoided most of the time.)

Share this post


Link to post
Share on other sites
quote:
Original post by marijnh
(mattnewport''s suggestion will usually work - vector iterators are usually implemented as pointers - but since the standard says that the iterator is invalidated after an erase this code might not work on all standard library implementations. furthermore, vector.erase is still horribly inefficient and should be avoided most of the time.)


this solution always works. erase returns the next valid iterator after the erased item, or end(). this is what he does as well.

but yes, erase isn''t that efficient.




If that''s not the help you''re after then you''re going to have to explain the problem better than what you have. - joanusdmentia

davepermen.net

Share this post


Link to post
Share on other sites
quote:
Original post by marijnh
(mattnewport''s suggestion will usually work - vector iterators are usually implemented as pointers - but since the standard says that the iterator is invalidated after an erase this code might not work on all standard library implementations. furthermore, vector.erase is still horribly inefficient and should be avoided most of the time.)


As davepermen pointed out the code I gave will always work because erase() returns the next valid iterator after the erased item. It would be a pretty useless function otherwise... It should be pretty obvious that that''s the case if you think for a moment about how vector works. A vector is only automatically resized when items are added, not when items are removed - it can only grow automatically, never shrink. That means there''s never going to be any reallocation of the vector''s memory on an erase() call, all that happens is that items above the erased item are all shifted down one place. The erase() call returns an iterator pointing to the item that is copied over the erased item (in most implementations that amounts to returning the same pointer as was passed in). The code I posted will work without alteration if EnemyVector is changed to a list or a deque anyway so it''s easy to try all three and see which is faster if this code proved to be a bottleneck (which is in itself pretty unlikely).

As for performance concerns over using vector vs. list, describing vector::erase() as ''horribly inefficient'' is pretty misleading. The standard algorithmic analysis of a list vs. a vector is based on an assumption that is wrong on modern architectures - that RAM is actually random access (i.e. that all memory accesses cost the same). There is a huge difference on modern machines between accessing a value that''s available in the L1 or L2 cache and accessing a value that has to be fetched from main memory. There''s an even bigger difference if you have a page miss and have to go the hard disk. Lists have horrible cache coherency whereas vectors have perfect cache coherency. In addition lists have a significant memory overhead (both for the list pointers and as a result of dynamically allocating every list node with all the memory overhead that entails) which compounds the cache coherency problem because a list with the same number of items as a vector will use more memory. A vector is going to perform better than a list in most usage scenarios, far more often than would be suggested by a naive algorithmic analysis.

Share this post


Link to post
Share on other sites

#include <functional>
#include <algorithm>

using namespace std;

struct IsDeadEnemy
: unary_function<Enemy, bool>
{
bool operator()(const Enemy& e)
{
return e.health < 0;
}
};

for_each( EnemyVector.begin(), EnemyVector.end(),
mem_fun_ref(&Enemy::Move) );

vector<Enemy>::iterator first_dead_enemy;
first_dead_enemy = remove_if( EnemyVector.begin(), EnemyVector.end(),
IsDeadEnemy() );

EnemyVector.erase(first_dead_enemy, EnemyVector.end());


[edited by - Fruny on March 19, 2004 1:56:05 PM]

Share this post


Link to post
Share on other sites
... oops - I did not read the code I was calling incorrect properly (missed the "it = " before the erase call, assuming it depended on the next element shifting into the position of the erased element thus leaving the iterator to automatically point at the next value), sorry!

Share this post


Link to post
Share on other sites