Using vectors Instead of Arrays

Problem

You have to store things (built-in types, objects, pointers, etc.) in a sequence, you require random access to elements, and you can't be confined to a statically sized array.

Solution

Use the standard library's vector class template, which is defined in ; don't use arrays. vector looks and feels like an array, but it has a number of safety and convenience advantages over arrays. Example 6-1 shows a few common vector operations.

Example 6-1. Using common vector member functions

#include #include #include using namespace std; int main( ) { vector intVec; vector strVec; // Add elements to the "back" of the vector with push_back intVec.push_back(3); intVec.push_back(9); intVec.push_back(6); string s = "Army"; strVec.push_back(s); s = "Navy"; strVec.push_back(s); s = "Air Force"; strVec.push_back(s); // You can access them with operator[], just like an array for (vector::size_type i = 0; i < intVec.size( ); ++i) { cout << "intVec[" << i << "] = " << intVec[i] << ' '; } // Or you can use iterators for (vector::iterator p = strVec.begin( ); p != strVec.end( ); ++p) { cout << *p << ' '; } // If you need to be safe, use at( ) instead of operator[]. It // will throw out_of_range if the index you use is > size( ). try { intVec.at(300) = 2; } catch(out_of_range& e) { cerr << "out_of_range: " << e.what( ) << endl; } }

Discussion

In general, if you need to use an array, you should use a vector instead. vectors offer more safety and flexibility than arrays, and the performance overhead is negligible in most casesand if you find that it's more than you can tolerate, you can fine-tune vector performance with a few member functions.

If you're not familiar with the containers that come with the standard library, or not acquainted with using class templates (writing them is another matter), the way vectors are declared in Example 6-1 may need some explanation. The declaration for a vector looks like this:

vector > // The memory allocator // to use

The standard containers are parameterized by the type of objects you want them to hold. There is also a template parameter for the memory allocator to use, but it defaults to the standard one, and writing one is uncommon, so I don't discuss it here.

If you want a vector that holds ints, declare it as in the example:

vector intVec;

And if you need one that holds strings, just change the vector's type argument:

vector strVec;

vectors can contain any C++ type that supports copy construction and assignment.

The next logical thing to do after you instantiate a vector is to put something in it. Add items to the back of it with push_back:

intVec.push_back(3); intVec.push_back(9); intVec.push_back(6);

This is roughly equivalent to adding elements 0, 1, and 2 to an array. It is "roughly" equivalent because, of course, push_back is a member function that returns void and pushes its argument onto the back of the vector. operator[] returns the memory location referenced by an index in an array. push_back makes sure there is enough room in the vector's internal buffer to add its argument; if there is, it adds the item to the next unused indexif there isn't room, it grows the buffer using an implementation-defined algorithm, then adds the argument object.

You can also insert items into the middle of a vector with the insert member function, though you should avoid it because doing so requires linear complexity. See Recipe 6.2 for a more detailed discussion of how to sidestep performance problems when using vectors. To insert an element, get an iterator to the point where you want your insert to begin (for a discussion of iterators, see Recipe 7.1):

string s = "Marines"; vector::iterator p = find(strVec.begin( ), strVec.end( ), s); if (s != strVec.end( )) // Insert s immediately before the element strVec.insert(p, s); // p points to

Overloaded versions of insert allow you to insert n copies of an object into a vector, as well as insert an entire range from another sequence (that sequence may be another vector, an array, a list, and so on).

Instead of inserting, you might want simply to assign the vector to a preexisting sequence from somewhere else, erasing whatever was there before. The assign member function does this. You can assign an entire range of values, or n copies of the same object, to your vector like this:

string sarr[3] = {"Ernie", "Bert", "Elmo"}; string s = "Oscar"; strVec.assign(&sarr[0], &sarr[3]); // Assign this sequence strVec.assign(50, s); // Assign 50 copies of s

assign will resize the vector's buffer to accommodate the new sequence if it is larger than the previous buffer size.

Once you have put your data in a vector, there are several ways for getting it back out. Probably the most intuitive is operator[], which returns a reference or a const reference to the item at that index, depending on whether the vector you are calling it on is const or not. In this respect, it looks a lot like an array:

for (int i = 0; i < intVec.size( ); ++i) { std::cout << "intVec[" << i << "] = " << intVec[i] << ' '; // rvalue } intVec[2] = 32; // lvalue

operator[] also behaves like an array in that if you use an index that is higher than the last element in the vector, the results are undefined, which usually means your program will corrupt data or crash. You can avoid this by querying the vector for the number of elements it contains with size( ). You should prefer iterators to operator[] though, because using iterators is the conventional way to iterate through any standard container:

for (vector::iterator p = strVec.begin( ); p != strVec.end( ); ++p) { std::cout << *p << ' '; }

Iterators are the more powerful approach because they allow for more generic interaction with containers. For example, if you write an algorithm that operates on a sequence of elements between two iterators, it can run against any standard container. This is a generic approach. If you use random access with operator[], you limit yourself to only those containers that support random access. The former approach is what allows the standard library algorithms in to work seamlessly with the standard containers (and other things that behave like them).

vectors also provide you with safety that you just can't get from a standard array. Unlike arrays, vectors offer range-checking with the at member function. If you give at an invalid index, it will throw an out_of_range exception, which you then have a chance to catch and react accordingly. For example:

try { intVec.at(300) = 2; } catch(std::out_of_range& e) { std::cerr << "out_of_range: " << e.what( ) << std::endl; }

As you know, if you reference an element past the end of an array with operator[], the operator does what you have told it to and fetches whatever is at that memory location. That's not good because either your program crashes from accessing memory it shouldn't, or it silently updates memory that belongs to another heap object, which is usually worse. operator[] works the same way for vector, but at least you can use at when you need to be safe.

So that's the crash course in vectors. But what is a vector? If you are writing in C++, you are probably performance-aware, and don't want to be given something and simply told that it works. Fair enough. See Recipe Recipe 6.2 for a discussion of how vectors work and tips for using them efficiently.

See Also

Recipe 6.2