Thread: 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.

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).

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?

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.

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

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.

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.

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.