C.Plus.Plus.Primer.4th.Edition [Electronic resources] نسخه متنی

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. Well 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 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 templates 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.

vector is not a type; it is a template that we can use to define any number of types. Each of vector type specifies an element type. Hence, vector<int> and vector<string> are types.

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 well 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 well 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 well 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 types default constructor to create the element initializer:

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

Chapter 12, some classes that define their own constructors do not define a default constructor. We cannot initialize a vector of such a type by specifying only a size; we must also specify an initial element value.

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.

To use size_type, we must name the type in which it is defined. A vector type always includes the element type of the vector:

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

Adding Elements to a vector

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.

Even if ivec is empty, this for loop executes correctly. If ivec is empty, the call to size returns 0 and the test in the for compares ix to 0. Because ix is itself 0 on the first trip, the test would fail and the loop body would not be executed even once.

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

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 well 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

An element must exist in order to subscript it; elements are not added when we assign through a subscript.