Thread: Array and the vector

>deleteing an individual item would result in a new block of memory being
>allocated (new T[N-1]), stuff copied over and the previous block deleted, yes?
The algorithms used are pretty smart. They may be wasteful of memory, but they generally take care not to call the allocator more than absolutely necessary. Just because you erase an item from a vector doesn't mean the memory actually gets freed. It just means that the item is no longer available for defined access.

>That's fine for small amounts of data or few changes, but baaaaaad news if you're gonna be
>moving megabytes or doing it hundreds of times.
The trick is to treat a vector like a dynamic array that you wrote. If you wouldn't use your own dynamic array library to solve a problem, why would you use someone else's? It all comes down to intelligently choosing your tools to best solve the problem at hand. Most of the time if a non-allocation operation on a dynamic array is expensive, it'll be just as expensive with a regular array.

Originally Posted by SMurf

Okay, but in terms of the dynamicness of vectors, deleteing an individual item would result in a new block of memory being allocated (new T[N-1]), stuff copied over and the previous block deleted, yes?

In which case, I would second Bubba's statement. That's fine for small amounts of data or few changes, but baaaaaad news if you're gonna be moving megabytes or doing it hundreds of times.

As I was alluding to, in the future this point may well be moot. But it saddens me from an engineering perspective.

This is not true. They are smart enough to allocate larger chunks. In other words... vector::count is not equal to the maximum in the buffer. You have to remember that we don't have beginners programming these stl classes.

In terms of a sad day for engineering... I pity the dinosaurs who can not see the value of OOP when it comes to engineering.

Originally Posted by Mario F.

I'm inclined to believe (read, from Scott Meyers' books) that all things equal, vectors will match dynamic arrays performance for random access, but come short in terms of insertions and deletions.

How so? What can a dynamic array possibly do faster than a class that effectively wraps a dynamic array?

Concerning static arrays, vectors will outperform arrays for insertions and deletions and match them for random access.

Static arrays simply can't have insertions or deletions. That's what static means.

Static arrays will outperform (and "out-safe", usually) vectors at initial construction and final destruction. Other than that, since they're likely on the stack, they might have better cache coherency than a vector that allocates data on the heap. That's only a guess, though, and will be wrong in many situations.

Which comes down to.....we have not arrived at a definite answer. In my personal experience I have found no major issues with vectors, unless you do a lot of inserting and deleting and even then the performance hit is near nothing.

When I get lasers and other objects up and running in the game I'll post some figures so we can have some hard data. Keep in mind the vectors I use that won't change during game such as texture managers, sound managers, and model managers will probably outperform the vectors that may have objects added/removed from them at runtime. A smart use of a vector though should curtail any problems. It is possible to use a vector as a type of recycling static array.

I just cannot fathom using a static array or coding my own dynamic array class and expect to outperform or perform as good as an STL vector. A static array would be a mess of code and a dynamic array would be a disaster to code and I doubt I'd get anything close to what I want.

So for now, I'll stick with vector. The only major STL container I've had performance hits with is std::map and I'm not exactly sure why since it uses the same <algorithm>(s) as vector. I use a std::map in my tile editor and when the tile counts get rather large you do begin to notice some performance degradation. This could be because I'm misusing the map or am simply uninformed about how to use them efficiently. So I would blame the performance of the map more on me than the underlying code.

> Static arrays simply can't have insertions or deletions. That's what static means.

I was hoping it was obvious that I was taking into consideration the time needed to create a new array and copy the values of the previous one.

>I just cannot fathom using a static array or coding my own dynamic array class
>and expect to outperform or perform as good as an STL vector.
You can sacrifice functionality and play games to get performance boosts here and there. However, if you're basically duplicating the work of a standard vector, it's very hard to beat existing implementations in any significant way. I've tried, and the difference is always single digit percentages or less.

>The only major STL container I've had performance hits with is std::map and
>I'm not exactly sure why since it uses the same <algorithm>(s) as vector.
map is usually an efficient implementation of a red black tree. I can't see structure changes causing a problem without grinding your machine to a halt from cache misses and thrashing. My guess would be the expense of copying data if you aren't storing pointers, but that'sjust a guess.

> You still don't do that with a static array. You cannot create a "new" static array.

Geez. Aren't we picky today! The mechanism for "resizing" a static array involves another array (a dynamic or static one, it doesn't matter) and the copying of one array elements into the other. This one of the first things they teach you when talking about static arrays.

If you guys prefer instead to waste your time around picking every hair of my speech, be my guest.

With all honesty it's probably much more interesting than discussing wich is faster; if vector or array. That is indeed a waste of time.

Heck, if you really cared about performance, you wouldn't be inserting and deleting elements in and out of a vector anyway. There are better ways to do those sorts of things.