Computing & Information Systems    Department Search CIS Site      Tutorials

## Software Design Using C++

### What are Vectors?

The Standard Template Library's vectors are somewhat like arrays but are considerably more flexible. Unlike a typical array, a vector can grow and shrink in size as needed, although there can sometimes be a performance penalty when the size is increased. But like an array, a vector can be indexed using the [] notation. There are class functions available for inserting a new item just before the item pointed to by an iterator, erasing (removing) an item, pushing an item onto the end of the vector, popping an item off of the end of the vector, returning the size of the vector, telling you if the vector is empty, clearing out the contents of the vector, etc. There are also several constructors for the vector class, with the default constructor building an empty vector. One can also use the various algorithms, such as those for sorting and searching, which are available for vectors and the other container classes.

### Example

#### Basics of Using Vectors

The above example illustrates some of what can be done with vectors. To use vectors you must include the `vector` header file. The `std` namespace is also needed in order to have access to the names used in the STL for the classes and functions. If you want to use any of the algorithms provided by the STL, you also need to include the `algorithm` header. Remember that these algorithms are separate from the functions provided by the vector container class itself.

 `````` #include #include #include using namespace std; ``````

To create a vector one uses something like the following. Note the use of `int` in angle brackets to specify that we want a vector of integers. The name of the vector is Num and it starts out with size 8.

 `````` vector Num(8); ``````

We can then use indexing to access individual items in the Num vector. For example, we can assign an item to the 0-th vector slot as follows:

 `````` Num[0] = 17; ``````

Note the first section of code for printing out the contents of the vector. It, too, uses indexing. It also illustrates the use of the `size` function to look up the current size of the vector. That is certainly more convenient than keeping a separate integer counter like we did with arrays.

 `````` for (k = 0; k < Num.size(); k++) cout << Num[k] << " "; ``````

There are several ways to grow the vector. One is to push a new item onto the end (back) of the vector. In our example program this is done as follows:

 `````` Num.push_back(-55); ``````

Adding a new item to the end of a vector can usually be done in constant time, but on occasion the vector will have to be relocated in memory, an operation that takes linear time, that is, Theta(n) time. On average, though, `push_back` would be expected to take constant time.

#### Iterators

We can also use the `insert` class function to insert a new item at a specific place in the vector. There are actually several versions of `insert`. Our sample program uses the simplest; it inserts a single item. To use this function we need an iterator that points to the location before which to insert. (Remember that an iterator is like a pointer.) Note how our example creates an iterator named `p` for use on a vector of integers. The iterator can be initialized by assigning it a value such as `Num.begin()`. The `begin` class function returns an iterator to the first item in the vector. In our example we add 4 to this, which gives a pointer to the item at index 4 in the vector.

 `````` vector::iterator p; cout << "We can insert -44 before the item at index 4." << endl; p = Num.begin() + 4; Num.insert(p, -44); ``````

Next, let's look at how the example program uses an iterator in printing the contents of the vector. This is an alternative to using indexing. Note that iterator `p` is initialized to point to the first item in the vector. Each time around the loop, `p` is incremented with the `++` operator. The loop test is to see whether `p` is not equal to `Num.end()`, which returns an iterator to the item one past the end of vector. (Just off the end is just right for loop control!) Each time around the loop we output the value `*p`, which is the value pointed at (as with regular pointers).

 `````` for (p = Num.begin(); p != Num.end(); p++) cout << *p << " "; ``````

The code to print the contents of a vector can also be packaged up as a (generic) function. Look at the function which is shown below. It can print a vector having any type of component (as long as that type is printable using the << stream operator.) Note that the vector parameter is made a reference parameter for efficiency.

 `````` template void Print(vector & Vec) { vector::iterator p; cout << "Contents of vector:" << endl; for (p = Vec.begin(); p != Vec.end(); p++) cout << *p << " "; cout << endl << endl; } ``````

#### Algorithms

Finally we look at some of the standard algorithms available for the vector and other container classes. One very useful one is `find`, which does a search for a given item within a certain section of the container (a vector in this case). The following code from our example searches for a 7 in the `Num` vector. Here we search the whole vector since the first and second parameters are iterators to the start and end (one off the end, actually) of the vector. The `find` returns an iterator to the first place where the item was found. If the item was not found, `find` returns an iterator to the end of the container (really one past the last item, as always). Note that we do not know (or need to know) the code for the `find` routine. All we know is how to call it and the fact that the STL guarantees that it runs in linear time.

 `````` p = find(Num.begin(), Num.end(), 7); if (p == Num.end()) cout << "Could not find 7 in the vector" << endl; else cout << "Have found 7 in the vector" << endl; ``````

Another very useful algorithm is `sort`, which is used to sort a section of the container. In the example below, we sort the entire vector by passing in as parameters iterators to the start and one past the end of the vector. This certainly makes it easy to sort as there is no code to write for the sort routine! Supposedly the STL guarantees that the `sort` algorithm runs in Theta(n * lg(n)) time, which is very good for sorting. There is no guarantee about what underlying algorithm might be used to perform the sorting. (For example, it might be mergesort or heapsort, but we do not know for sure.)

 `````` sort(Num.begin(), Num.end()); ``````

There are many more algorithms and much more that can be done with vectors, but we will not go further with those topics here. See the references for more information.

### Related Items

 PointersIntermediate Topic. Basics of ArraysIntroductory Topic. ArraysIntermediate Topic.
Back to the main page for Software Design Using C++

Author: Br. David Carlson with contributions by Br. Isidore Minerd
Last updated: August 27, 2009
Disclaimer