3.3. Library vector Type

A vector is a collection of objects of a single type, each of which has an associated integer index. As with strings, the library takes care of managing the memory associated with storing the elements. We speak of a vector as a container because it contains other objects. All of the objects in a container must have the same type. We'll have much more to say about containers in Chapter 9.

To use a vector, we must include the appropriate header. In our examples, we also assume an appropriate using declaration is made:

     #include <vector>
     using std::vector;

A vector is a class template. Templates let us write a single class or function definition that can be used on a variety of types. Thus, we can define a vector that holds strings, or a vector to hold ints, or one to hold objects of our own class types, such as Sales_items. We'll see how to define our own class templates in Chapter 16. Fortunately, we need to know very little about how templates are defined in order to use them.

To declare objects of a type generated from a class template, we must supply additional information. The nature of this information depends on the template. In the case of vector, we must say what type of objects the vector will contain. We specify the type by putting it between a pair of angle brackets following the template's name:

     vector<int> ivec;               // ivec holds objects of type int
     vector<Sales_item> Sales_vec;   // holds Sales_items

As in any variable definition, we specify a type and a list of one or more variables. In the first of these definitions, the type is vector<int>, which is a vector that holds objects of type int. The name of the variable is ivec. In the second, we define Sales_vec to hold Sales_item objects.

3.3.1. Defining and Initializing vectors

The vector class defines several constructors (Section 2.3.3, p. 49), which we use to define and initialize vector objects. The constructors are listed in Table 3.4.

Table 3.4. Ways to Initialize a vector

vector<T> v1;	vector that holds objects of type T;
	Default constructor v1 is empty
vector<T> v2(v1);	v2 is a copy of v1
vector<T> v3(n, i);	v3 has n elements with value i
vector<T> v4(n);	v4 has n copies of a value-initialized object

Creating a Specified Number of Elements

When we create a vector that is not empty, we must supply value(s) to use to initialize the elements. When we copy one vector to another, each element in the new vector is initialized as a copy of the corresponding element in the original vector. The two vectors must hold the same element type:

     vector<int> ivec1;           // ivec1 holds objects of type int
     vector<int> ivec2(ivec1);    // ok: copy elements of ivec1 into ivec2
     vector<string> svec(ivec1);  // error: svec holds strings, not ints

We can initialize a vector from a count and an element value. The constructor uses the count to determine how many elements the vector should have and uses the value to specify the value each of those elements will have:

     vector<int> ivec4(10, -1);       // 10 elements, each initialized to -1
     vector<string> svec(10, "hi!");  // 10 strings, each initialized to "hi!"

Key Concept: vectorS Grow Dynamically A central property of vectors (and the other library containers) is that they are required to be implemented so that it is efficient to add elements to them at run time. Because vectors grow efficiently, it is usually best to let the vector grow by adding elements to it dynamically as the element values are known. As we'll see in Chapter 4, this behavior is distinctly different from that of built-in arrays in C and for that matter in most other languages. In particular, readers accustomed to using C or Java might expect that because vector elements are stored contiguously, it would be best to preallocate the vector at its expected size. In fact, the contrary is the case, for reasons we'll explore in Chapter 9. Although we can preallocate a given number of elements in a vector, it is usually more efficient to define an empty vector and add elements to it (as we'll learn how to do shortly).

Value Initialization

When we do not specify an element initializer, then the library creates a value initialized element initializer for us. This library-generated value is used to initialize each element in the container. The value of the element initializer depends on the type of the elements stored in the vector.

If the vector holds elements of a built-in type, such as int, then the library creates an element initializer with a value of 0:

     vector<string> fvec(10); // 10 elements, each initialized to 0

If the vector holds elements of a class type, such as string, that defines its own constructors, then the library uses the value type's default constructor to create the element initializer:

     vector<string> svec(10); // 10 elements, each an empty string

There is a third possibility: The element type might be of a class type that does not define any constructors. In this case, the library still creates a value-initialized object. It does so by value-initializing each member of that object.

Exercises Section 3.3.1 Exercise 3.11: Which, if any, of the following vector definitions are in error? (a) vector< vector<int> > ivec; (b) vector<string> svec = ivec; (c) vector<string> svec(10, "null"); Exercise 3.12: How many elements are there in each of the following vectors? What are the values of the elements? (a) vector<int> ivec1; (b) vector<int> ivec2(10); (c) vector<int> ivec3(10, 42); (d) vector<string> svec1; (e) vector<string> svec2(10); (f) vector<string> svec3(10, "hello");

3.3.2. Operations on vectors

The vector library provides various operations, many of which are similar to operations on strings. Table 3.5 lists the most important vector operations.

Table 3.5. vector Operations

v.empty()	Returns true if v is empty; otherwise returns false
v.size()	Returns number of elements in v
v.push_back(t)	Adds element with value t to end of v
v[n]	Returns element at position n in v
v1 = v2	Replaces elements in v1 by a copy of elements in v2
v1 == v2	Returns TRue if v1 and v2 are equal
!=, <, <=, >, and >=	Have their normal meanings

The size of a vector

The empty and size operations are similar to the corresponding string operations (Section 3.2.3, p. 83). The size member returns a value of the size_type defined by the corresponding vector type.

     vector<int>::size_type        // ok
     vector::size_type            // error

Adding Elements to a vector

The push_back operation takes an element value and adds that value as a new element at the back of a vector. In effect it "pushes" an element onto the "back" of the vector:

     // read words from the standard input and store them as elements in a vector
     string word;
     vector<string> text;    // empty vector
     while (cin >> word) {
         text.push_back(word);     // append word to text
     }

This loop reads a sequence of strings from the standard input, appending them one at a time onto the back of the vector. We start by defining text as an initially empty vector. Each trip through the loop adds a new element to the vector and gives that element the value of whatever word was read from the input. When the loop completes, text will have as many elements as were read.

Subscripting a vector

Objects in the vector are not named. Instead, they can be accessed by their position in the vector. We can fetch an element using the subscript operator. Subscripting a vector is similar to subscripting a string (Section 3.2.3, p. 87).

The vector subscript operator takes a value and returns the element at that position in the vector. Elements in a vector are numbered beginning with 0. The following example uses a for loop to reset each element in the vector to 0:

     // reset the elements in the vector to zero
     for (vector<int>::size_type ix = 0; ix != ivec.size(); ++ix)
         ivec[ix] = 0;

Like the string subscript operator, the vector subscript yields an lvalue so that we may write to it, which we do in the body of the loop. Also, as we do for strings, we use the size_type of the vector as the type for the subscript.

Subscripting Does Not Add Elements

Programmers new to C++ sometimes think that subscripting a vector adds elements; it does not:

     vector<int> ivec;   // empty vector
     for (vector<int>::size_type ix = 0; ix != 10; ++ix)
         ivec[ix] = ix; // disaster: ivec has no elements

Key Concept: Safe, Generic Programming Programmers coming to C++ from C or Java might be surprised that our loop used != rather than < to test the index against the size of the vector. C programmers are probably also suprised that we call the size member in the for rather than calling it once before the loop and remembering its value. C++ programmers tend to write loops using != in preference to < as a matter of habit. In this case, there is no particular reason to choose one operator or the other. We'll understand the rationale for this habit once we cover generic programming in Part II. Calling size rather than remembering its value is similarly unnecessary in this case but again reflects a good habit. In C++, data structures such as vector can grow dynamically. Our loop only reads elements; it does not add them. However, a loop could easily add new elements. If the loop did add elements, then testing a saved value of size would failour loop would not account for the newly added elements. Because a loop might add elements, we tend to write our loops to test the current size on each pass rather than store a copy of what the size was when we entered the loop. As we'll see in Chapter 7, in C++ functions can be declared to be inline. When it can do so, the compiler will expand the code for an inline function directly rather than actually making a function call. Tiny library functions such as size are almost surely defined to be inline, so we expect that there is little run-time cost in making this call on each trip through the loop.

This code intended to insert new 10 elements into ivec, giving the elements the values from 0 through 9. However, ivec is an empty vector and subscripts can only be used to fetch existing elements.

The right way to write this loop would be

     for (vector<int>::size_type ix = 0; ix != 10; ++ix)
         ivec.push_back(ix);  // ok: adds new element with value ix