C++: Vectors vs. Arrays

In many of our programs we are using C-style arrays to store data. These are easy to write, but can be difficult to work with—they cannot be resized, they don’t know their own size, and most array operations require the use of pointers and memory management.

For many applications, you may want or need a data structure that is simpler to use. Check out the vector library in C++. The syntax for vectors may be new to you, but they make many operations a whole lot easier. A brief introduction to using the vector class is here.

Personally I like vectors because they make C++ operations more Matlab-esque, and they help prevent the memory management errors that are so common with C-style arrays. The downside, according to the C purists, is that vectors are slower than arrays. This can be true, depending on how you use them. But the vector class is really only an abstraction of the C-style array, so basic operations like storage and retrieval are still completed in constant time. The only time vectors slow down is when you append items to them, because behind the scenes, the vector is copying an entire array and adding a single element to it. This runs in O(N) time and can really slow things down if you do it every loop iteration. (Source: the tutorial above, and here).

So: vectors can make your life a lot easier, and they are the same speed as arrays for indexing operations. Just be careful to resize vectors as few times as necessary to preserve the efficiency of your program.

P.S. I’m sure there are dissenting opinions on the array/vector debate … please add your two cents.

Advertisements

5 thoughts on “C++: Vectors vs. Arrays

  1. So, does using the vector.reserve(size) method alleviate the slowdown due to appending items? What about inserting items? Also, if you are looping through the elements of a vector using an iterator, does this have any speed implications relative to a normal C-style array?

    Joe identified some interesting memory management issues with vectors a while back and eventually took some of them out of his code. Maybe he could expand on this briefly.

    I myself have used vectors frequently for small codes such as non-domination sorting. However, I would be very careful about utilizing them in larger codes that will require very high efficiency. Additionally, I’m not sure of their implications in a parallel environment (i.e., MPI).

    I wrote a set of vector and matrix classes for use in my EnKF code that I think are pretty streamlined. Obviously, they don’t provide all of the functionality of the STL vector class, but I think this is what speeds them up in a sense. If anyone ever needs to uses them, just let me know. They would at least serve as a good starting point for whatever it is you need to do.

    Just some food for thought…thanks for the useful post Jon.

  2. Thanks for the good questions Josh. I agree that if you really, really need maximum efficiency, it’s probably best to stick with C-style allocation.

    My thoughts: inserting items would require the same slowdown as appending items, and would run in O(N) time. Reserving a size for the vector would reduce the append operation to O(1), because it would only be storing one element, but inserting would still require O(N) because items would need to be copied. About iterator speed, I honestly don’t know (I usually just use for loops with direct indexing).

  3. Interesting discussion! I don’t think the vector class is too black-boxy, but it does set up different areas of concern.

    With C arrays, you have to be very careful about memory, particularly when it comes to reading and writing past the end of the array. Your best case scenario if you make such an error is for your program to crash, since you can have an edge case that writes past the end of the array, corrupts something else on the heap, and doesn’t cause a crash, leaving you with an impossible debugging scenario. (Valgrind helps mightily with this problem.)

    With vectors, you have to be cautious about triggering inefficient code. Indexed element access has been inlined and optimized to within an inch of its life and should be very close to, if not in fact equivalent to, the speed of indexed access in C. Indexing isn’t range-checked, either, but you could take a small hit and use at() instead. Iterators should be nearly as fast as indexing, about as fast as at(). Inserting an element in the middle of the vector is O(N), just as it would be for a C array, but it’s much easier to do to a vector without thinking about the consequences. Appending should be O(1) as long as you’ve reserved enough memory. Copying the vector could be a big drag if you accidentally make a deep copy rather than a reference. Et cetera.

    I favor using vectors whenever possible for their memory-safety and convenience, but if array operations are a bottleneck, C-style arrays do cut overhead to the barest minimum. I have Stroustrup’s book at my desk if you want to know every last detail about how vector works.

  4. The problem of mine Josh was referring to has to do with making vectors of nonstandard types. You can’t make a vector of ofstream objects, for example. And there’s some caveat of using vectors of classes that I didn’t really understand.

    I think it would be worthwhile to look into the actual performance issues with using vectors for 2d and 3d arrays though. What if, instead of allocating memory using new and delete, we just used the .resize() command at the beginning of the code, ensuring that the vector is never resized through all the calculations. In that case, I would bet that it’s as fast as the C-style arrays. But just a thought.

  5. Pingback: Water Programming Blog Guide (Part I) – Water Programming: A Collaborative Research Blog

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s