8.3 Vectors

“Well, I’ll eat it,” said Alice, “and if it makes me grow larger, I can reach the key; and if it makes me grow smaller, I can creep under the door; so either way I’ll get into the garden….”

LEWIS CARROLL, Alice’s Adventures in Wonderland

Vectors can be thought of as arrays that can grow (and shrink) in length while your program is running. In C++, once your program creates an array, it cannot change the length of the array. Vectors serve the same purpose as arrays except that they can change length while the program is running. Vectors are part of a standard C++ library known as the STL (Standard Template Library), which we cover in more detail in Chapter 18.

You need not read the previous sections of this chapter before covering this section.

Vector Basics

Like an array, a vector has a base type, and like an array, a vector stores a collection of values of its base type. However, the syntax for a vector type and a vector variable declaration are different from the syntax for arrays.

Declaring a vector variable

You declare a variable v for a vector with base type int as follows:

vector<int> v;

The notation vector <Base_Type> is a template class, which means you can plug in any type for Base_Type and that will produce a class for vectors with that base type. You can think of this as specifying the base type for a vector in the same sense as you specify a base type for an array. You can use any type, including class types, as the base type for a vector. The notation vector <int> is a class name, and so the previous declaration of v as a vector of type vector <int> includes a call to the default constructor for the class vector <int>, which creates a vector object that is empty (has no elements).

Vector elements are indexed starting with 0, the same as arrays. The array square brackets notation can be used to read or change these elements, just as with an array. For example, the following changes the value of the ith element of the vector v and then outputs that changed value. (i is an int variable.)

v[i] = 42;
cout << "The answer is " << v[i];

There is, however, a restriction on this use of the square brackets notation with vectors that is unlike the same notation used with arrays. You can use v[i] to change the value of the ith element. However, you cannot initialize the ith element using v[i]; you can only change an element that has already been given some value. To add an element to an index position of a vector for the first time, you would normally use the member function push_back.

You add elements to a vector in order of positions, first at position 0, then position 1, then 2, and so forth. The member function push_back adds an element in the next available position. For example, the following gives initial values to elements 0, 1, and 2 of the vector sample:

vector<double> sample;
sample.push_back(0.0);
sample.push_back(1.1);
sample.push_back(2.2);

In C++11 we can initialize a vector the same way we initialize an array:

vector<double> sample = {0.0, 1.1, 2.2};

The number of elements in a vector is called the size of the vector. The member function size can be used to determine how many elements are in a vector. For example, after the previously shown code is executed, sample.size( ) returns 3. You can write out all the elements currently in the vector sample as follows:

for (int i = 0; i < sample.size( ); i++)
	cout << sample[i] << endl;

The function size returns a value of type unsigned int, not a value of type int. (The type unsigned int allows only nonnegative integer values.) This returned value should be automatically converted to type int when it needs to be of type int, but some compilers may warn you that you are using an unsigned int where an int is required. If you want to be very safe, you can always apply a type cast to convert the returned unsigned int to an int or, in cases like this for loop, use a loop control variable of type unsigned int as follows:

for (unsigned int  i = 0; i < sample.size( ); i++)
	cout << sample[i] << endl;

Equivalently, we could use the ranged for loop:

for (auto	i : sample)
	cout << i << endl;

A simple demonstration illustrating some basic vector techniques is given in Display 8.9.

Display 8.9 Using a Vector

 1	 #include <iostream>
 2	  #include <vector>
 3	  using namespace std;

 4	  int main( )
 5	  {
 6		  vector<int> v;
 7		  cout << "Enter a list of positive numbers.\n"
 8			   << "Place a negative number at the end.\n";

 9		  int next;
10		  cin >> next;
11		  while (next > 0)
12		  {
13			  v.push_back(next);
14			  cout << next << " added. ";
15			  cout << "v.size( ) = " <<v.size( ) <<endl;
16			  cin >> next;
17		  }

18		  cout << "You entered:\n";
19		  for (unsigned int i = 0; i <v.size( ); i++)
20			  cout << v[i] << " ";
21		  cout << endl;

22		  return 0;
23	  }

Sample Dialogue

Enter a list of positive numbers.
Place a negative number at the end.
2 4 6 8 −1
2 added. v.size( ) = 1
4 added. v.size( ) = 2
6 added. v.size( ) = 3
8 added. v.size( ) = 4
You entered:
2 4 6 8

There is a vector constructor that takes one integer argument and will initialize the number of positions given as the argument. For example, if you declare v as follows:

vector<int> v(10);

then the first ten elements are initialized to 0, and v.size( ) would return 10. You can then set the value of the ith element using v[i] for values of i equal to 0 through 9. In particular, the following could immediately follow the declaration:

for (unsigned int i = 0; i < 10; i++)
	v[i] = i;

To set the ith element, for i greater than or equal to 10, you would use push_back.

When you use the constructor with an integer argument, vectors of numbers are initialized to the zero of the number type. If the vector base type is a class type, the default constructor is used for initialization.

The vector definition is given in the library vector, which places it in the std namespace. Thus, a file that uses vectors would include the following (or something similar):

#include <vector>
using namespace std;

Pitfall Using Square Brackets Beyond the Vector Size

If v is a vector and i is greater than or equal to v.size( ), then the element v[i] does not yet exist and needs to be created by using push_back to add elements up to and including position i. If you try to set v[i] for i greater than or equal to v.size( ), as in

v[i] = n;

then you may or may not get an error message, but your program will undoubtedly misbehave at some point.

Vectors

Vectors are used very much like arrays are used, but a vector does not have a fixed size. If it needs more capacity to store another element, its capacity is automatically increased. Vectors are defined in the library <vector>, which places them in the std namespace. Thus, a file that uses vectors would include the following (or something similar):

#include <vector>
using namespace std;

The vector class for a given Base_Type is written vector <Base_Type>. Two sample vector declarations are

vector<int> v; //default constructor
 //producing an empty vector.
vector<AClass> record(20); //vector constructor
 //for AClass to initialize
 //20 elements.

Elements are added to a vector using the member function push_back, as illustrated below:

v.push_back(42);

Once an element position has received its first element, either with push_back or with a constructor initialization, that element position can then be accessed using square bracket notation, just like an array element.

Programming Tip Vector Assignment Is Well Behaved

The assignment operator with vectors does an element-by-element assignment to the vector on the left-hand side of the assignment operator (increasing capacity if needed and resetting the size of the vector on the left-hand side of the assignment operator). Thus, provided the assignment operator on the base type makes an independent copy of the element of the base type, then the assignment operator on the vector will make an independent copy.

Note that for the assignment operator to produce a totally independent copy of the vector on the right-hand side of the assignment operator requires that the assignment operator on the base type make completely independent copies. The assignment operator on a vector is only as good (or bad) as the assignment operator on its base type. (Details on overloading the assignment operator for classes that need it are given in Chapter 11.)

Efficiency Issues

At any point in time a vector has a capacity, which is the number of elements for which it currently has memory allocated. The member function capacity( ) can be used to find out the capacity of a vector. Do not confuse the capacity of a vector with the size of a vector. The size is the number of elements in a vector, while the capacity is the number of elements for which there is memory allocated. Typically, the capacity is larger than the size, and the capacity is always greater than or equal to the size.

Whenever a vector runs out of capacity and needs room for an additional member, the capacity is automatically increased. The exact amount of the increase is implementation-dependent but always allows for more capacity than is immediately needed. A commonly used implementation scheme is for the capacity to double whenever it needs to increase. Since increasing capacity is a complex task, this approach of reallocating capacity in large chunks is more efficient than allocating numerous small chunks.

Size and Capacity

The size of a vector is the number of elements in the vector. The capacity of a vector is the number of elements for which it currently has memory allocated. For a vector v, the size and capacity can be recovered with the member functions v.size( ) and v.capacity( ).

You can completely ignore the capacity of a vector and that will have no effect on what your program does. However, if efficiency is an issue, you might want to manage capacity yourself and not simply accept the default behavior of doubling capacity whenever more is needed. You can use the member function reserve to explicitly increase the capacity of a vector. For example,

v.reserve(32);

sets the capacity to at least 32 elements, and

v.reserve(v.size( ) + 10);

sets the capacity to at least 10 more than the number of elements currently in the vector. Note that you can rely on v.reserve to increase the capacity of a vector, but it does not necessarily decrease the capacity of a vector if the argument is smaller than the current capacity.

You can change the size of a vector using the member function resize. For example, the following resizes a vector to 24 elements:

v.resize(24);

If the previous size was less than 24, then the new elements are initialized as we described for the constructor with an integer argument. If the previous size was greater than 24, then all but the first 24 elements are lost. The capacity is automatically increased if need be. Using resize and reserve, you can shrink the size and capacity of a vector when there is no longer any need for some elements or some capacity.

Self-Test Exercises

19. Is the following program legal? If so, what is the output?

    #include <iostream>
    #include <vector>
    using namespace std;
    
    int main( )
    {
    	vector<int> v(10);
    	int i;
    	for (i = 0; i < v.size( ); i++)
    	   v[i] = i;
    	vector<int> copy;
    	copy = v;
    	v[0] = 42;
    	for	 (i = 0; i < copy.size( ); i++)
    	   cout << copy[i] << " ";
    	cout << endl;
    	return	0;
    }

20. What is the difference between the size and the capacity of a vector?