Array and the vector

Hi, I recently read in a book i have that it is no good learning about arrays, and stick with and always use vectors. I know how to use both very well, and in general use vectors over arrays anyeay.

My question is this:

Why would people have to or want to learn about C-style arrays

eg:

Code:

---

int num[10]={1,2,3,4 ect.. };[

---

When vectors can do all the above can and is faster and has more capabilitys for sorting through a sequence like iterators?

Many books teach arrays and vectors, but I think they should stick with vectors and use arrays as an side learning subject. That is only my view mind.

vectors are dynamic containers. A static array is often more efficient than a vector because of this. Also, there are some things a vector cannot do, like the initialization you showed in your example (although that might be available in the next standard). Finally, an array can be sorted just as easily as a vector can.

So in the occasional situations when one needs the ultimate efficiency, an array is obviously the better choice. You might not run into these situations very often, which is why you are told to use vectors instead of arrays. But other programmers might be in different situations where using an array is the best solution.

Learning about arrays is a good idea regardless of whether you use them specifically instead of vectors or not. They are a data structure and understanding of arrays and how they work can be very beneficial to your understanding of what you are programming.

Thanks daved. That was just the answer I was looking for.

Are vectors really faster than arrays? (or does efficiency mean speed?)

Quote:

---

Originally Posted by Clyde

Are vectors really faster than arrays? (or does efficiency mean speed?)

---

Yes. Arrays are just a simple block of memory, so finding the right spot is a lot faster than something with dynamic allocation, eg. linked lists (where you have to traverse through each node), or vectors.

There's no reason arrays would be necessarily faster than vectors, except in startup time of the program. The expression v[i] can be compiled down to the exact same instructions no matter whether v is a T* or a vector<T>. Arrays can use one or two pointers' less memory if you don't want to grow them or if you have their size hard-coded, of course.

The power that vectors provide far outweighs any performance issues they may create...if any.


With my old space game I fired off 5000 lasers, tracked them per frame, render them in brute force with no culling and did all of this on an old GeForce 3 64MB card at well over 120 FPS with no vsync.

I doubt vectors are going to cause any major problems unless you are deleting and inserting multiple times per cycle or frame.

I use vectors for nearly all of my game resource managers and they work like a charm. Currently I'm getting over 900 FPS so I have plenty of frames there to work with.

As to the question should you always use vectors over arrays my answer is it depends on the task and the need.
That's like saying should you always use a certain tool over another when working on your car. This is ludicrous. Use the right tool for the job.

Vectors are not always the right tool.
Arrays are not always the right tool.

This is why we need people called programmers. So my answer is BOTH AND.

Quote:

---

When vectors can do all the above can and is faster and has more capabilitys for sorting through a sequence like iterators?

---

Be more careful about saying complex things are faster... because they aren't.

>Why would people have to or want to learn about C-style arrays
Working with legacy code, interfacing with libraries that use them, and writing code where vectors could be impractical. That last one could pop up on platforms where the overhead is just too much, or in critical applications that can't afford allocation errors.

>When vectors can do all the above can and is faster and has more capabilitys for sorting through a sequence like iterators?
It's trivial to write a container class for an array. The boost library has one, and then it can be used with the rest of the standard library in a syntactically consistent way.

I don't quite see what the kerfuffle is about (although as I don't currently program in C++ maybe I'm not class-centric enough). :confused:

You have an array of bytes. If you were to make a vector of it you'd split it up into a singular byte and a pointer to the next item (and these are usually 4 bytes on a 32-bit platform).

Isn't the inefficiency obvious?

You can view an array as a special contigious case of a vector whereby the next item is implicitly at the next memory address, elminating the need for a pointer.

If the future of programming is to have everything in vectors, I think I'll just calmly walk out back and commit suicide, ta. ;)

>Isn't the inefficiency obvious?
Not really. You're confusing vectors and lists. A vector is required to be stored in contiguous space, so the implementation is pretty much going to be a dynamic array. How else would we be able to do &v[0] and use it as an array of T? ;)

Oh right. Like I said, no experience of C++ so aside from cursory glances of things the only vector I recognise is the one with members x, y (and z). :o

So you're saying it uses realloc under all that shiz?

>So you're saying it uses realloc under all that shiz?
It uses allocators, where the default allocator relies on new, so by default a vector is logically no different memory-wise from:

Code:

---

T *p = new T[N];

---

I'm not even sure there should be a discussion around vectors performance over arrays. For one, different libraries are free to implement them however they wish (despite probably they all being roughly the same).

But most important is the fact STL containers are meant to provide us with specific data structure solutions out of the box. Not to replace standard structures and even less to try and outperform them; Vector is not a replacement for an array. It is an array wrapper (heck! probably it doesn't even need to be that).

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. Concerning static arrays, vectors will outperform arrays for insertions and deletions and match them for random access.

>I'm not even sure there should be a discussion around vectors performance over arrays.
I am sure. We have our performance guarantees from the standard, and anything beyond that requires profiling for specific cases. No debate is necessary.

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

Yes, but the same thing is true of a dynamic array. Whatever vector has to do under the covers you would have to do if you were using a dynamic array instead, and so while deleting from a vector can be expensive, it is really no more expensive than deleting from an array.

The reason a vector can be less efficient than a static array is because of the memory allocation and keeping track of the size. But if you compare a vector to a dynamic array you see both have those same issues.

It is really rather simple. In most cases use of std::tr1::array (boost::array) or std::vector is better than the built-in static or dynamic array because of the benefits of the interface and memory handling done for you. Occasionally, in some specific cases, there can be noticable differences in speed or size efficiency, in which case you might consider a built-in array instead.

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

Quote:

---

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.

Quote:

---

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?

Quote:

---

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

>> 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.
You still don't do that with a static array. You cannot create a "new" static array. They are created at compile time. That is why a static array cannot have insertions and deletions.

>> we have not arrived at a definite answer
Sure we have. Other than some confusion about the difference between static and dynamic arrays, it seems everybody is in agreement. I think the confusion lies in the fact that different containers are intended for different uses. Of course a static array wouldn't work well for a situation where the size changes dynamically, that's not what a static array is for. In a situation where the size of the array is a compile time constant, then a static array very well might outperform a vector or dynamic array, because they have other features for handling dynamic sizes that might slow them down or waste space. Similarly, it is difficult to say that a map is faster or slower than a vector, because they are generally meant for different situations.

The best comparison is between vector and a dynamic array, and in almost all cases a correctly used vector will match the performance of a correctly used dynamic array.

>> The only major STL container I've had performance hits with is std::map
BTW, our code had a severe performance degradation with the map container (and lists as well, although the map was more obvious) when we used a specific standard library implementation. The solution was to use a pool allocator to avoid the memory fragmentation that was being caused by the way that implementation allocated space for nodes in the map. This only happened with a single version of this implementation (I believe it was dinkumware's 3.08 version, but I could be wrong). If your performance hits are happening during allocation or deallocation, especially destruction of a full map, then you might be having a similar issue.

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

>> If you guys prefer instead to waste your time around picking every hair of my speech, be my guest.
It has nothing to do with picking every hair of your speech. It has to do with making sure the understanding is there, both for you and for others reading the thread. It makes little sense to discuss inserting and deleting from a static array. That is not what they are intended for and not what they are used for. If one wants to compare a vector to a static array, it makes sense to keep the comparison focused on the tasks that both can reasonably accomplish. Otherwise one ends up confusing the issue. Whether you share that confusion or not, it is still appropriate to clarify it for others reading the thread.

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.

Quote:

---

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.

---

Therein lies the crux of my arguments. There are multiple ways to do multiple things. Picking the right one and the most efficient one is ....well...programming. You can't always use A for B in every case or for every task. It's ludicrous.

I'd say we are in agreement as well that the overall underlying principle here is we have a set of tools out there be it static arrays, dynamic arrays, vectors, lists, etc, etc. Use the right tool for the job.