Vectors are nice..and useless at times

I have gotten into the habit of using std::vector for a lot of things. However I wanted to ask why in the world the STL designers made removing items from a vector invalidate every iterator/index after the removed item? This is a major drawback to an otherwise extremely nice container.

The problem of invalidation though makes a vector useless in certain instances. I've looked for a container that allows array like access and does not invalidate iterators when objects are removed. One could use the vector as a recycling array that did not remove the actual item from the vector but rather nullifed the data. The iterator would then be stored as a cached iterator and the add() function would then look at this. If it was null or invalid it would add to the end, if it was valid it would add where the last 'removal' was done. This does not require an invalidation of items beyond the 'removal' point.

I've looked at other container types in the STL and just cannot find a good fit for what I need. I don't want a static array because I don't want to iterate the entire array if only 5 elements are valid in the array. Yes I could code my own container type and have already, but I was wondering if there was an STL equivalent?

Reinvent the wheel!

Sorry, but I had to beat someone else before they said this. :D

This is where you wish you could properly subclass std::vector.... which I think you can't because its destructor isn't virtual (and other reasons).

Hehe. I hate reinventing the wheel but std::vector is just not cutting the mustard for what I need.
The STL is both a thing of beauty and a pain in the arse.

Quote:

Originally Posted by Bubba

I have gotten into the habit of using std::vector for a lot of things. However I wanted to ask why in the world the STL designers made removing items from a vector invalidate every iterator/index after the removed item? This is a major drawback to an otherwise extremely nice container.

There is no way for it to be otherwise, while still maintaining the vector's performance. When you remove an item from a vector the items following it all "slide down" one space. Any iterators pointing to those objects would have to be updated. In order to do that, the vector would have to track the existence of ALL iterators pointing into it so it could fix them up.

That would mean that each iterator would have to register itself with the original vector so it knows about it. Something as simple as copying an iterator would then involve going back to the original vector and registering the new iterator. And every time an iterator goes out of scope it must de-register itself. Since iterators are usually passed by value, this would entail enormous overhead even making simple function calls.

So I guess I'm SOL with this one. I don't want to force myself to call SetIter() or SetIndex() for every object beyond the removal pointer either. Since I could not find a way around it I coded what I call a SmartArray which is a templated static array that acts like a vector but does not use iterators. However, I'm not fond of coding my own containers and would rather use a proven and tested one from the STL.

I could probably fire off a thread to reset the iters and it would be a very lightweight one but that seems hackish.

Quote:

Originally Posted by Bubba

So I guess I'm SOL with this one. I don't want to force myself to call SetIter() or SetIndex() for every object beyond the removal pointer either. Since I could not find a way around it I coded what I call a SmartArray which is a templated static array that acts like a vector but does not use iterators. However, I'm not fond of coding my own containers and would rather use a proven and tested one from the STL.

I could probably fire off a thread to reset the iters and it would be a very lightweight one but that seems hackish.

I think the right answer is going to hinge on what exactly you are trying to do. What sort of items are in this vector, why do you add them and why do you remove them?

I have tons of sprites in a container. These sprites contain all the necessary data to draw a sprite on the screen. However these sprites can and will be removed by other events at runtime. Important issues are:

Random access - very important for finding the sprite to remove and/or use
Easy and quick iteration - very important for the manager so it can draw all the sprites
Insertion is not important since order has nothing to do with render speed.
Quick removal that does not affect other items in the container.

Each sprite has an ID which is essentially its index in the container. A vector will invalidate this information as soon as I remove anything and thus the code bails horribly.

I would post my SmartArray code but won't for fear of being blasted to smithereens by everyone. :)

Could you use some other container from the STL instead of a vector, like a list for example? http://www.sgi.com/tech/stl/List.html

Quote:

The ordering of iterators may be changed (that is, list<T>::iterator might have a different predecessor or successor after a list operation than it did before), but the iterators themselves will not be invalidated or made to point to different elements unless that invalidation or mutation is explicit. [1]

[1] A comparison with vector is instructive. Suppose that i is a valid vector<T>::iterator. If an element is inserted or removed in a position that precedes i, then this operation will either result in i pointing to a different element than it did before, or else it will invalidate i entirely. (A vector<T>::iterator will be invalidated, for example, if an insertion requires a reallocation.) However, suppose that i and j are both iterators into a vector, and there exists some integer n such that i == j + n. In that case, even if elements are inserted into the vector and i and j point to different elements, the relation between the two iterators will still hold. A list is exactly the opposite: iterators will not be invalidated, and will not be made to point to different elements, but, for list iterators, the predecessor/successor relationship is not invariant.

Quote:

Originally Posted by Bubba

I have tons of sprites in a container. These sprites contain all the necessary data to draw a sprite on the screen. However these sprites can and will be removed by other events at runtime. Important issues are:

Random access - very important for finding the sprite to remove and/or use
Easy and quick iteration - very important for the manager so it can draw all the sprites
Insertion is not important since order has nothing to do with render speed.
Quick removal that does not affect other items in the container.

Each sprite has an ID which is essentially its index in the container. A vector will invalidate this information as soon as I remove anything and thus the code bails horribly.

I would post my SmartArray code but won't for fear of being blasted to smithereens by everyone. :)

In that case I would say that the correct container to use is a std::map. It would map from SpriteID to Sprite, using some simple cookie generator for the SpriteID.
The to use a map instead reasons are:

You don't care about ordering within the vector or during iteration.
You want to be able to have unused key values between two other used key values.
You probably don't need the items consecutive in memory.

A map certainly seems to do what you want.
I guess that the reason you're using a vector instead of a map is for speed reasons. Are you sure speed is an issue? Have you tried timing using a custom allocator with a map?

Actually, it seems that even an unordered_map / hash_map would do what you want. Why not switch to that instead?

>> Random access - very important for finding the sprite to remove and/or use
>> Each sprite has an ID which is essentially its index in the container
By "random access" - are you just refering to the constant lookup you get by using the ID as an index? Or do you also need to have a linear array - so that pointer arithmetic like *(it + 5) works out?

Have you considered an associative container (like std::set) which would give you logrithmic lookups - it's not constant, but ain't too slow :)

gg

I agree, to a point, with the unordered_map suggestion. However, I also think a vector with delete-marked entries is worth another thought. Adding a new entry first scans the vector.

You'd have to monitor the usage pattern. If the sprite counts differ wildly between stretches of time, the delete-marked vector might become too sparse to be efficient. However, I rather think that you'd unload many sprites close together, then load a lot of sprites again, always topping at about the same level.

The problem with hash maps is that they generally have a rather high constant factor overhead.

I don't want to use a map since with my system it will degrade into a linked list. I may in the future use my random class to generate unique IDs for the objects in the map and then store the IDs of those objects. This may prove to be the best option.

I like the delete-marked vector though and I'm giving it a shot tonight. My custom template class is plagued with all the problems you'd come to expect from not properly thinking out a data structure beforehand. I will get it working but I'm not sure it's worth the time. Some of my friends are diehard STL and some are diehard code your own custom container. I think I fall somewhere in between those extremes.

I will try all of your suggestions as each one has had good ones. Hopefully I'll get this resolved soon so I can finish the game.

How about just making the "ID" a pointer value to the sprite object itself. Then you only need the container for iteration and deletion. Lookups are still constant - since the ID is the object.

Of course you take a space hit on 64bit systems, but probably acceptable.

gg

Quote:

How about just making the "ID" a pointer value to the sprite object itself. Then you only need the container for iteration and deletion. Lookups are still constant - since the ID is the object.

Because this breaks the design philosophy that the container and only the container owns and handles the objects. With the design you suggested I'll have pointers floating around everywhere that someone could misuse and abuse without the container knowing about it.

The sprite ID is like a social security number for the sprite. If the sprite ID is invalid then no request is granted to the objects in the container since the requesting object obviously obtained its ID incorrectly. It's not quite as secure as that but it's the general idea.

Having the container own and control the objects it contains is quite nice. It centralizes all operations on the objects in the container. So if something is bailing or bombing on the sprites I know who's fault it is. No one else in the game can alter the sprites without using the sprite container.

So - I'm assuming then that all sprite operations are performed using an ID - and the "user" has no exposure to the underlying sprite object implementation? Which would mean that just going from a constant lookup to a logarithmic lookup could severely impact performance?

I'm just trying to gauge how important the constant lookup is.

gg

Quote:

Originally Posted by Bubba

Random access - very important for finding the sprite to remove and/or use
Easy and quick iteration - very important for the manager so it can draw all the sprites
Insertion is not important since order has nothing to do with render speed.
Quick removal that does not affect other items in the container.

A hand-coded hash table with linear probing ought to suffice.

EDIT: Actually, on second thought, there may be performance issues depending how you assign sprite IDs. Suppose you remove a sprite and then insert it again. Does the sprite have the same ID as it did before? Then it will always land in the same bucket of the hash table, or in this case, starting position. So some sprites might be penalized by slow lookup since they always land in "bad" places in the table.

You could salt them with a random value.

What about creating a vector of iterators?

Code:

std::list<sprite> spriteList; std::vector<std::list<sprite>::iterator> vecIter;

When you delete a sprite in spriteList, it won't cause all the iterators in vecIter to move down, so those iterators wouldn't be invalidated, and by using a list as the main container, only the iterator you're deleting will be invalidated. You can either use the list iterators to move from the beginning to the end, or you can use the vector's operator[] to go right to the place you want...

Well right now I'm just crashing everywhere so nothing to show yet. Somedays I suck at code.

I got it working with the vector and a delete mark. It just tracks the last known deletion and uses vector::size() to iterate. It seems to work ok. Memory clean up is the responsibility of the class using the vector if the objects are created on the heap.

Quote:

Originally Posted by Bubba

I don't want to use a map since with my system it will degrade into a linked list. I may in the future use my random class to generate unique IDs for the objects in the map and then store the IDs of those objects. This may prove to be the best option.

Wait - what!?
A map never degrades to a linked list. A map guarantees O(log n) search time, typically by using a self-balancing red-black tree (or similiar).

an unordered_map can however, if the hash is extremely poor.

I thought about it some more, and I think a hybrid of a hash table and a doubly linked list would work. The hash table could be very simple, of fixed size. You simply take the hash code modulo the table size to get an index. If there is already a sprite at that index, you search forward with any reasonable deterministic method to find an empty location and insert the sprite there.

This solves the issues of: fast insertion, removal, and lookup (if the table is not too full). However, you have no good way of iterating over the sprites. You could scan the entire table looking for spots with sprites in them, but if your table is sparse, which is what you want for purposes of speed, then this is going to waste a lot of time looking at empty locations.

To solve that problem, you also insert the sprite into a circular linked list when you place it in the hash table. You can drop it into the cycle at any point you want. Now, your sprite iterator is just a pointer to a node of this list. You can follow the links forward until you re-arrive at your starting point, at which point you know you're done. Inserting new nodes at any point of the ring will not break the cycle so you can't get an infinite loop unless the point you started at is deleted. So how do you avoid deletion of the starting point? Insert a single dummy node into the cycle and use this as the starting point for all iterations. The dummy node can't get deleted, so you can never get an infinite loop.

But suppose you have some iterator P which started out at a spot on this ring and advanced forward several positions, and you now insert a new node between its original starting spot and its current position. This node will not be seen during the traversal of the links by iterator P.

So you can just specify that iterators are not guaranteed to iterate over EVERY element in the list if some insertion operation occurs between an iterator instantiation, and that iterator reaching end(). This doesn't seem too onerous a limitation...

It's not really possible to implement this with straight STL, though. The links of the sprite nodes have to be embedded in the hash table records themselves. That is, if you want to get an iterator to a specific node or erase a node through an iterator -- if you never do that, you could implement this all in plain STL.

Quote:

an unordered_map can however, if the hash is extremely poor.

And mine is.

Well here is the result so far:

Everything in the scene is animated and controlled by several instances of a SmartVector template class.

The bounding boxes are already implemented here so all that's left to do is a hit test, which is already coded, and then fire off the right explosion animation and/or split the asteroid into smaller ones or remove it completely.

I'll add some scoring to the bottom as well as some lives and maybe a front end menu later. The plan is to add some baddies to shoot and have different backdrops and asteroids for different levels. I'd also like to throw in some random comets in the background and other items just to improve the space atmosphere.

This is very strange but the program is crashing on array access to the SmartVector. But it only happens every so often so this is going to be a fun bug to track down.

It bails on:

SmartVector.h - SmartVector::operator []

Code:

T &operator[] (const size_t &index) { return m_vVector[index]; }

The debugger says that index cannot be evaluated. Nice. So now I have an error that is fragging a variable.

It has something to do with this code:

LaserMgr.cpp - LaserMgr::CheckHits()

Code:

void LaserMgr::CheckHits() { for (size_t i = 0;i < m_vLasers.GetSize(); ++i) { //If current laser 'slot' is valid if (m_vLasers[i]) { //Grab the sprite so we don't have to constantly call GetSpriteMgr() Sprite *pSprite = X3DGetApp()->GetSpriteMgr()->Get(m_vLasers[i]->SpriteID); //Grab sprite position and LOCAL/MODEL min/max boundaries D3DXVECTOR3 vecLaserPos = pSprite->GetPos(); D3DXVECTOR3 vecLaserMin = pSprite->GetMin(); D3DXVECTOR3 vecLaserMax = pSprite->GetMax(); //Transform min/max to WORLD sprite location float LaserLeft = vecLaserPos.x + vecLaserMin.x; float LaserTop = vecLaserPos.y + vecLaserMin.y; float LaserRight = vecLaserPos.x + vecLaserMax.x; float LaserBottom = vecLaserPos.y + vecLaserMax.y; //Grab the asteroid manager for use later AstMgr *pAstMgr = X3DGetApp()->GetAstMgr(); for (size_t j = 0;j < pAstMgr->GetSize(); ++j) { //Grab an asteroid Asteroid *pAst = pAstMgr->Get(j); //Is it valid? if (pAst) { //Check for collision int hit = pAst->Collide(LaserLeft,LaserTop,LaserRight,LaserBottom); if (hit > 0) { //We have a collision so remove laser from laser mgr and sprite mgr vectors X3DGetApp()->GetSpriteMgr()->Remove(m_vLasers[i]->SpriteID); m_vLasers.Remove(i); //Let the asteroid manager decide what to do with the doomed asteroid pAstMgr->Destroy(j); } } } } } }

SpriteMgr.cpp - SpriteMgr::Remove()

Code:

bool SpriteMgr::Remove(const size_t &index) { //De-allocate memory delete m_vSprites[index]; //Remove from vector (only nullifies, does not actually remove) return m_vSprites.Remove(index); }

SmartVector.h - SmartVector::Remove()

Code:

virtual bool Remove(const size_t &index) { //Check for out of range if (index > (m_vVector.size()-1)) { return false; } //Nullify current 'slot' m_vVector[index] = NULL; //Set cache index to this index (this will be used on next Add() operation) m_CacheIndex = index; //Cache value is now valid m_CacheValid = true; return true; }

Yes that's an ugly collision test but it's fast enough for now and I'll improve it later. It doesn't like me removing the lasers from the the laser mgr smart vector after I remove the laser sprite from the sprite mgr smart vector.

Call stack on access violation

Quote:

> Astroids.exe!SmartVector<Sprite *>::Remove(const unsigned int & index=) Line 53 + 0x11 bytes C++
Astroids.exe!SpriteMgr::Remove(const unsigned int & index=) Line 64 + 0x17 bytes C++
Astroids.exe!LaserMgr::CheckHits() Line 63 C++
Astroids.exe!LaserMgr::Update(float fTimeDelta=0.019000001) Line 115 C++
Astroids.exe!AstroidsApp::Update(const float fTimeDelta=0.019000001) Line 163 C++
Astroids.exe!D3DApp::EnterMsgLoop() Line 303 + 0x16 bytes C++
Astroids.exe!WinMain(HINSTANCE__ * hInstance=0x00400000, HINSTANCE__ * prevInstance=0x00000000, char * cmdLine=0x00151f14, int showCmd=1) Line 119 C++
Astroids.exe!__tmainCRTStartup() Line 589 + 0x35 bytes C
Astroids.exe!WinMainCRTStartup() Line 414 C

Check out index's value in Remove(). It's garbage right there and should not be. Index is just an integer that is actually the j variable in the LaserMgr::CheckHits() nested loop. Very strange. I've highlighted the important portions that I believe are bailing.

Any ideas?

This looks dangerous to me.

Code:

if (index > (m_vVector.size()-1)) { return false; }

if m_vVector.size() returns a size_t this test fails if the vector is empty.
I'd use

Code:

if (index >= m_vVector.size() ) { return false; }

Kurt

I think I found it: it's in the inner j loop.

Code:

... for (size_t j = 0;j < pAstMgr->GetSize(); ++j) { //Grab an asteroid Asteroid *pAst = pAstMgr->Get(j); //Is it valid? if (pAst) { //Check for collision int hit = pAst->Collide(LaserLeft,LaserTop,LaserRight,LaserBottom); if (hit > 0) { //We have a collision so remove laser from laser mgr and sprite mgr vectors X3DGetApp()->GetSpriteMgr()->Remove(m_vLasers[i]->SpriteID); m_vLasers.Remove(i); //Let the asteroid manager decide what to do with the doomed asteroid pAstMgr->Destroy(j); } } }

There is a serious problem here. I'm deleting a laser inside of the asteroid loop. This nullfies the laser data. But if we are not done with the asteroid loop, it will ASSUME m_vLasers[i] is still valid, which it's not.

Since I'm checking one laser against multiple asteroids it would do just as well do bail out of the inner loop if I remove the laser since I know 100% sure that testing an asteroid against an invalid laser is always going return false for hit detection. I'm essentially continually testing a dead laser against all asteroids. Not good.

EDIT:

This fixed it. Game works good now and no mem leaks from crtdbg.

Quote:

Originally Posted by Bubba

And mine is.

Yeah but you wouldn't pick a terrible hash function on purpose. No matter what the data is, you can always come up with a decent hash function.

Quote:

fragging a variable

LOL! I've never heard it put that way before :)

Nice pic btw!

Quote:

Originally Posted by Bubba

This is very strange but the program is crashing on array access to the SmartVector. But it only happens every so often so this is going to be a fun bug to track down.

It bails on:

SmartVector.h - SmartVector:: operator []

Code:

T &operator[] (const size_t &index) { return m_vVector[index]; }

If you use m_vVector.at( index ); instead of [index] then the vector should throw an out_of_bounds exception instead of just crashing.

Quote:

Originally Posted by Bubba

SpriteMgr.cpp - SpriteMgr::Remove()

Code:

bool SpriteMgr::Remove(const size_t &index) { //De-allocate memory delete m_vSprites[index]; //Remove from vector (only nullifies, does not actually remove) return m_vSprites.Remove(index); }

SmartVector.h - SmartVector::Remove()

Code:

virtual bool Remove(const size_t &index) { //Check for out of range if (index > (m_vVector.size()-1)) { return false; } //Nullify current 'slot' m_vVector[index] = NULL; //Set cache index to this index (this will be used on next Add() operation) m_CacheIndex = index; //Cache value is now valid m_CacheValid = true; return true; }

Shouldn't you check if the index is valid (i.e. in range) before deleting it?

Out of curiosity, why do you pass the size_ts by reference? They're a machine word large, so passing them by value should me more efficient.

I could change the function to check the range first.

Just an update here. The data structure I chose to use is a hybrid. It is a static array with a stack for 'remembering' empty slots. When an element is removed it's index in the array is pushed onto the stack. When an element is added the stack is checked. If it's not empty, the top item is popped off and used as an index for the element to be added. A cleanup function is ran periodically to ensure the array is being used effectively.

Because this structure re-uses so many empty elements it's size grows marginally. After 20 levels of asteroids it was only about 400 elements. On the first few levels big asteroids only spawn about 1 to 2 asteroids. On later levels they spawn 4 and 5 with each one of those spawning the same.