I tried searching google for this but it only returned sites about comparing Java and C++ speedwise. I was wondering if there is any speed hit in just accessing an element in the vector, or changing a pre-existant one (ie not adding new ones)? Would I gain anything from writing my own vector, consisting of only a wrapped array that gets re-allocated every time a certain element count is reached? I'm not looking for nanoseconds here, it is just for a game of mine similar to bomberman and I have these so called Very Important Entities that need to be updated every cycle ( I've build the game so that normal entities reside in a 1D-array which I treat as a 2D-array, where I only update those entities whom are visible to the player ). If you have any better ideas as to how to do this about the VIEs, I'll be happy to hear them! Thanks in advance!

std::vector is fast and there's likely very little (if anything) to be gained by writing your own, so I say just use std::vector :D

A vector actually is just a wrapped array (with some extra sugar added). It is really unlikely you could get a large speed-increase by creating your own vector.

Please use your enter and period keys more in the future, it makes your post much easier to read.

Quote:Original post by moussen15
I tried searching google for this but it only returned sites about comparing Java and C++ speedwise. I was wondering if there is any speed hit in just accessing an element in the vector, or changing a pre-existant one (ie not adding new ones)?

No more so than accessing an element of a normal array unless in debug mode (release mode will optimize out the overhead completely on any decent compiler).

Quote:Would I gain anything from writing my own vector, consisting of only a wrapped array that gets re-allocated every time a certain element count is reached?

You'd gain knowledge of implementation of such things, a learning experience.

You would loose (yes, loose!!!) speed however. std::vector increases the size allocated by a percentage of that allready used as needed, reducing the insertion of N elements from an O(N*N) operation to an O(N) one (if my complexity math is remembered right). You could duplicate this behavior, but chances are you wouldn't get any extra speed out of it. std::vector is pretty **** well optimized :-). (edit: err, depends on exactly what you meant by "a certain count" - I accidentally read that as "every time" - if you double the amount allocated each time then the speed loss comment does not apply, as this is the method used by at least some implementations of the standard library).

Quote:I'm not looking for nanoseconds here, it is just for a game of mine similar to bomberman and I have these so called Very Important Entities that need to be updated every cycle ( I've build the game so that normal entities reside in a 1D-array which I treat as a 2D-array, where I only update those entities whom are visible to the player ).
If you have any better ideas as to how to do this about the VIEs, I'll be happy to hear them!

It seems a bit vauge of a description.... do the two dimentions represent different coordinates?
Thanks in advance!
Anytime :-).

First of all thank you for all your answers. And I'll use by enter-key more in the future ;)

Yes I access the array through doing this: y*mLevelWidth+x. Then, every cycle, I calculate a set of coordinates forming a square (ie startx might be 10 and endx might be 20 and vice versa for starty and endy, creating a 10 times 10 square). All the entities inside this square will be update()d and draw()n (if they exist that is).

But in say multiplayer mode, I'd want to have bots or players that won't stop moving as soon as they move too far away. Therefore I figured I'd store them separetely. So now I'm iterating this vector every turn and updating and drawing these entities as well.

The only problem with this is that when I had everything inside my semi-2D-array collision detection and such was very easy. Say an object was moving down one position in the world. Then I'd check if there was an entity at the position below it by simply accessing the array. Now I have to go through the whole vector everytime an object moves, and this might take up uneccessesary(sp?) CPU resources if I were playing in a level with many creatures.

What if I had 500 VIEs and every one of them moved? That'd mean 500^499 checks, right?
So this solution really only works for small worlds, and in small worlds, there isn't really a point in having this special vector either, because then I could just draw the whole array without much overhead.

Oh, and maybe this should get moved to Game Programming now? :)

std::vector uses the heap when creating its internal array - storage. if you have small vectors, you should use the stack instead to gain some extra speed. to use stack based allocation, try vector - libraries like tinyvector from

http://oonumerics.org/blitz/

or use boost::array

"As replacement for ordinary arrays, the STL provides class std::vector. However, std::vector<> provides the semantics of dynamic arrays. Thus, it manages data to be able to change the number of elements. This results in some overhead in case only arrays with static size are needed."

http://www.boost.org/doc/html/array.html

or tvmet:
http://tvmet.sourceforge.net/

All the standard library containers have well defined time complexities. std::vector, for example, has constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle.

More about vectors.
About time complexity specifications.