15.5.1. vector Sequence Container

Class template vector, which we introduced in Section 7.10, provides a data structure with contiguous memory locations. This enables efficient, direct access to any element of a vector via the subscript operator [], exactly as with a built-in array. Like class template array, template vector is most commonly used when the data in the container must be easily accessible via a subscript or will be sorted, and when the number of elements may need to grow. When a vector’s memory is exhausted, the vector allocates a larger built-in array, copies (or moves; Chapter 24) the original elements into the new built-in array and deallocates the old built-in array. .

Using vectors and Iterators

Figure 15.10 illustrates several functions of the vector class template. Many of these functions are available in every first-class container. You must include header <vector> to use class template vector.

Click here to view code image

Fig. 15.10. Standard Library vector class template.

Creating a vector

Line 14 defines an instance called integers of class template vector that stores int values. When this object is instantiated, an empty vector is created with size 0 (i.e., the number of elements stored in the vector) and capacity 0 (i.e., the number of elements that can be stored without allocating more memory to the vector).

vector Member Functions size and capacity

Lines 16 and 17 demonstrate the size and capacity functions; each initially returns 0 for vector v in this example. Function size—available in every container except forward_List—returns the number of elements currently stored in the container. Function capacity (specific to vector and deque) returns the number of elements that can be stored in the vector before the vector needs to dynamically resize itself to accommodate more elements.

vector Member Function push_back

Lines 20–22 use function push_back—available in sequence containers other than array and forward_list—to add an element to the end of the vector. If an element is added to a full vector, the vector increases its size—some implementations have the vector double its capacity. Sequence containers other than array and vector also provide a push_front function.

Updated size and capacity After Modifying a vector

Lines 24 and 25 use size and capacity to illustrate the new size and capacity of the vector after the three push_back operations. Function size returns 3—the number of elements added to the vector. Function capacity returns 4 (though this could vary by compiler), indicating that we can add one more element before the vector needs to add more memory. When we added the first element, the vector allocated space for one element, and the size became 1 to indicate that the vector contained only one element. When we added the second element, the capacity doubled to 2 and the size became 2 as well. When we added the third element, the capacity doubled again to 4. So we can actually add another element before the vector needs to allocate more space. When the vector eventually fills its allocated capacity and the program attempts to add one more element to the vector, the vector will double its capacity to eight elements.

vector Growth

The manner in which a vector grows to accommodate more elements—a time consuming operation—is not specified by the C++ Standard. C++ library implementers use various clever schemes to minimize the overhead of resizing a vector. Hence, the output of this program may vary, depending on the version of vector that comes with your compiler. Some library implementers allocate a large initial capacity. If a vector stores a small number of elements, such capacity may be a waste of space. However, it can greatly improve performance if a program adds many elements to a vector and does not have to reallocate memory to accommodate those elements. This is a classic space–time trade-off. Library implementors must balance the amount of memory used against the amount of time required to perform various vector operations.

Outputting Built-in Array Contents with Pointers

Lines 29–30 demonstrate how to output the contents of the built-in array values using pointers and pointer arithmetic. Pointers into a built-in array can be used as iterators. Recall from Section 8.5 that C++11 functions begin and end (line 29) from the <iterator> header each take a built-in array as an argument. Function begin returns an iterator pointing to the built-in array’s first element and function end returns an iterator representing the position one element after the end of the built-in array. Functions begin and end may also receive container objects as arguments. Note that we use the != operator in the loop-continuation condition. When iterating using pointers to built-in array elements, it’s common for the loop-continuation condition to test whether the pointer has reached the end of the built-in array. This technique is commonly used by the standard library algorithms.

Outputting vector Contents with Iterators

Line 33 calls function printVector (defined in lines 45–51) to output the contents of a vector using iterators. The function receives a reference to a const vector. The for statement in lines 48–50 initializes control variable constIterator using vector member function cbegin (new in C++11), which returns a const_iterator to the vector’s first element. We infer the control variable’s type (vector<int>::const_iterator) using the auto keyword. Prior to C++11, you would have used the overloaded begin member function to get the const_iterator—when called on a const container, begin returns a const_iterator. The other version of begin returns an iterator that can be used for non-const containers.

The loop continues as long as constIterator has not reached the end of the vector. This is determined by comparing constIterator to the result of calling the vector’s cend member function (also new in C++11), which returns a const_iterator indicating the location past the last element of the vector. If constIterator is equal to this value, the end of the vector has been reached. Prior to C++11, you would have used the overloaded end member function to get the const_iterator. Functions cbegin, begin, cend and end are available for all first-class containers.

The body of the loop dereferences constIterator to get the current element’s value. Remember that the iterator acts like a pointer to the element and that operator * is overloaded to return a reference to the element. The expression ++constIterator (line 49) positions the iterator to the vector’s next element. Note that lines 48–50 could have been replaced with the following range-based for statement:

Click here to view code image

Displaying the vector’s Contents in Reverse with const_reverse_iterators

Lines 37–39 use a for statement (similar to the one in printVector) to iterate through the vector in reverse. C++11 now includes vector member function crbegin and crend which return const_reverse_iterators that represent the starting and ending points when iterating through a container in reverse. Most first-class containers support this type of iterator. As with functions cbegin and cend, prior to C++11 you would have used the overloaded member functions rbegin and rend to obtain const_reverse_iterators or reverse_iterators, based on whether the container is const.

C++11: shrink_to_fit

As of C++11, you can ask a vector or deque to return unneeded memory to the system by calling member function shrink_to_fit. This requests that the container reduce its capacity to the number of elements in the container. According to the C++ standard, implementations can ignore this request so that they can perform implementation-specific optimizations.

vector Element-Manipulation Functions

Figure 15.11 illustrates functions for retrieving and manipulating vector elements. Line 16 uses an overloaded vector constructor that takes two iterators as arguments to initialize integers. Line 16 initializes integers with the contents of the array values from beginning of values up to—but not including—values.cend() (which points to the element after the end of values). In C++11, you can use list initializers to initialize vectors as in

or

However, these are not fully supported across compilers yet. For this reason, this chapter’s examples frequently initialize other containers with array contents as in line 16.

Click here to view code image

Fig. 15.11. vector class template element-manipulation functions.

ostream_iterator

Line 17 defines an ostream_iterator called output that can be used to output integers separated by single spaces via cout. An ostream_iterator<int> outputs only values of type int or a compatible type. The first argument to the constructor specifies the output stream, and the second argument is a string specifying the separator for the values output—in this case, the string contains a space character. We use the ostream_iterator (defined in header <iterator>) to output the contents of the vector in this example.

copy Algorithm

Line 20 uses Standard Library algorithm copy (from header <algorithm>) to output the entire contents of integers to the standard output. The algorithm copies each element in a range from the location specified by the iterator in its first argument and up to, but not including, the location specified by the iterator in its second argument. These two arguments must satisfy input iterator requirements—they must be iterators through which values can be read from a container, such as const_iterators. They must also represent a range of elements—applying ++ to the first iterator must eventually cause it to reach the second iterator argument in the range. The elements are copied to the location specified by the output iterator (i.e., an iterator through which a value can be stored or output) specified as the last argument. In this case, the output iterator is an ostream_iterator that’s attached to cout, so the elements are copied to the standard output.

vector Member Functions front and back

Lines 22–23 use functions front and back (available for most sequence containers) to determine the vector’s first and last elements, respectively. Notice the difference between functions front and begin. Function front returns a reference to the first element in the vector, while function begin returns a random access iterator pointing to the first element in the vector. Also notice the difference between functions back and end. Function back returns a reference to the vector’s last element, whereas function end returns a random access iterator pointing to the location after the last element.

Accessing vector Elements

Lines 25–26 illustrate two ways to access vector elements. These can also be used with deque containers. Line 25 uses the subscript operator that’s overloaded to return either a reference to the value at the specified location or a reference to that const value, depending on whether the container is const. Function at (line 26) performs the same operation, but with bounds checking. Function at first checks the value supplied as an argument and determines whether it’s in the vector’s bounds. If not, function at throws an out_of_range exception (as demonstrated in lines 35–42). Figure 15.12 shows some of the Standard Library exception types. (The Standard Library exception types are discussed in Chapter 17.)

Fig. 15.12. Some exception types in header <stdexcept>.

vector Member Function insert

Line 29 uses one of the several overloaded insert functions provided by each sequence container (except array, which has a fixed size, and forward_list, which has the function insert_after instead). Line 29 inserts the value 22 before the element at the location specified by the iterator in the first argument. In this example, the iterator is pointing to the vector’s second element, so 22 is inserted as the second element and the original second element becomes the third element. Other versions of insert allow inserting multiple copies of the same value starting at a particular position, or inserting a range of values from another container, starting at a particular position. As of C++11, this version of member function insert returns an iterator pointing to the item that was inserted.

vector Member Function erase

Lines 45 and 50 use the two erase functions that are available in all first-class containers (except array, which has a fixed size, and forward_list, which has the function erase_after instead). Line 45 erases the element at the location specified by the iterator argument (in this example, the first element). Line 50 specifies that all elements in the range specified by the two iterator arguments should be erased. In this example, all the elements are erased. Line 52 uses function empty (available for all containers and adapters) to confirm that the vector is empty.

vector Member Function insert with Three Arguments (Range insert)

Line 55 demonstrates the version of function insert that uses the second and third arguments to specify the starting location and ending location in a sequence of values (in this case, from the array values) that should be inserted into the vector. Remember that the ending location specifies the position in the sequence after the last element to be inserted; copying occurs up to, but not including, this location. As of C++11, this version of member function insert returns an iterator pointing to the first item that was inserted—if nothing was inserted, the function returns its first argument.

vector Member Function clear

Finally, line 60 uses function clear (found in all first-class containers except array) to empty the vector—this does not necessarily return any of the vector’s memory to the system. [Note: We’ll cover many common container member functions in the next few sections. We’ll also cover many functions that are specific to each container.]