Vectors

Basic Properties

Vectors are containers used for storing multiple data elements. They have the following properties:

Random Access

vectors are random access containers meaning that the time to access an element in the container is constant - it does not depend on the size of the vector. This is as opposed to sequential access. An example of a random access device we use is a CD player, or an old-style turntable. A tape on the other hand is a sequential access device.

Dynamic Size

Readers who've worked with fixed length arrays will appreciate that it is annoying to have to decide the size of the container at compile time. This is both wasteful (because you may allocate more memory than needed) and limiting (because you may need more memory than you allocate). A better solution would be to allocate memory on-demand at runtime. And this is what the vector does. Allocating memory dynamically has it's potential pitfalls -- it is difficult to get right and easy to get wrong. Fortunately, the difficult stuff is neatly encapsulated in the internals of the vector class, and users (for the most part) do not have to worry about it.

Efficient ``Back-Insertion''

It is efficient to insert elements into the back of a vector. Inserting in the middle or at the front of the vector reuquires moving all the other elements, but inserting at the back doesn't. It possibly requires allocating more memory for the vector as needed, and that's all. Hence the following guideline:

When possible, always insert elements at the back of the vector.

Vectors ``Act Like'' Arrays

If you've used arrays, vectors will seem familiar. One can access their elements using the bracket operator []. The data in vectors is stored in a similar way to that in arrays.

Some Basic Methods

We can get started using vector with just a few methods:

• void push_back(const T&) Add an element to the back of a vector.
• unsigned int size() returns the size of the vector. (1)
• bool empty() returns true if the vector is empty. It is preferred to checking size == 0. (It is at least as fast, possibly faster).
• T& operator[](size_type) We can access elements in a vector using array notation. If v is a vector<int>, we can access elements of v using the notation v[i] where i is a positive integer.

Armed with these three methods alone, one can already write useful code. For example, here's a simple program to compute the average of several numbers:

vector1.cc

#include <vector>
#include <iostream>

using namespace std;

int main()
{
	vector<double> v;
	double d;
	double total=0;

	cout << "Enter a positive number (-1 to quit)" << endl;
	while (cin >> d && d != -1)
	{
		cout << "Enter a positive number (-1 to quit)" << endl;
		v.push_back(d);
	}

	// compute average 
	if ( v.empty() )
		cout << "The average is undefined" << endl;
	else
	{
		for ( int i = 0; i < v.size(); ++i ) 
			total += v[i];
		cout << "The average is:" <<  total/v.size() << endl;	
	}


}

There's many more exciting things one can do with vectors, and indeed we will do them -- but first we will introduce the string class

Footnotes

1. It is a little dishonest to say that size() returns unsigned int. It actually returns an integral data type called vector<T>::size_type. It's sometimes important to be aware of the fact that this type is unsigned, because comparing unsigned and signed data can produce surprising results if the numbers involved are negative.