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. .
Performance Tip 15.5
Choose the vector container for the best random-access performance in a container that can grow.
Performance Tip 15.6
Objects of class template vector provide rapid indexed access with the overloaded subscript operator [] because they’re stored in contiguous memory like a built-in array or an array object.
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
.
1 // Fig. 15.10: Fig15_10.cpp
2 // Standard Library vector class template.
3 #include <iostream>
4 #include <vector> // vector class-template definition
5 using namespace std;
6
7 // prototype for function template printVector
8 template < typename T > void printVector( const vector< T > &integers2 );
9
10 int main()
11 {
12 const size_t SIZE = 6; // define array size
13 int values[ SIZE ] = { 1, 2, 3, 4, 5, 6 }; // initialize values
14 vector< int > integers; // create vector of ints
15
16 cout << "The initial size of integers is: " << integers.size()
17 << "
The initial capacity of integers is: " << integers.capacity();
18
19 // function push_back is in vector, deque and list
20 integers.push_back( 2 );
21 integers.push_back( 3 );
22 integers.push_back( 4 );
23
24 cout << "
The size of integers is: " << integers.size()
25 << "
The capacity of integers is: " << integers.capacity();
26 cout << "
Output built-in array using pointer notation: ";
27
28 // display array using pointer notation
29 for ( const int *ptr = begin( values ); ptr != end( values ); ++ptr )
30 cout << *ptr << ' ';
31
32 cout << "
Output vector using iterator notation: ";
33 printVector( integers );
34 cout << "
Reversed contents of vector integers: ";
35
36 // display vector in reverse order using const_reverse_iterator
37 for ( auto reverseIterator = integers.crbegin();
38 reverseIterator!= integers.crend(); ++reverseIterator )
39 cout << *reverseIterator << ' ';
40
41 cout << endl;
42 } // end main
43
44 // function template for outputting vector elements
45 template < typename T > void printVector( const vector< T > &integers2 )
46 {
47 // display vector elements using const_iterator
48 for ( auto constIterator = integers2.cbegin();
49 constIterator != integers2.cend(); ++constIterator )
50 cout << *constIterator << ' ';
51 } // end function printVector
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
).
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.
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.
Performance Tip 15.7
It can be wasteful to double a vector’s size when more space is needed. For example, a full vector of 1,000,000 elements resizes to accommodate 2,000,000 elements when a new element is added. This leaves 999,999 unused elements. You can use resize and reserve to control space usage better.
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.
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.
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.
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:
for ( auto const &item : integers2 )
cout << item << ' ';
Common Programming Error 15.1
Attempting to dereference an iterator positioned outside its container is a runtime logic error. In particular, the iterator returned by end
should not be dereferenced or incremented.
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_iterator
s 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_iterator
s or reverse_iterator
s, based on whether the container is const
.
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.
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 vector
s as in
vector< int > integers{ 1, 2, 3, 4, 5, 6 };
or
vector< int > integers = { 1, 2, 3, 4, 5, 6 };
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.
1 // Fig. 15.11: fig15_15.cpp
2 // Testing Standard Library vector class template
3 // element-manipulation functions.
4 #include <iostream>
5 #include <array> // array class-template definition
6 #include <vector> // vector class-template definition
7 #include <algorithm> // copy algorithm
8 #include <iterator> // ostream_iterator iterator
9 #include <stdexcept> // out_of_range exception
10 using namespace std;
11
12 int main()
13 {
14 const size_t SIZE = 6;
15 array< int, SIZE > values = { 1, 2, 3, 4, 5, 6 };
16 vector< int > integers( values.cbegin(), values.cend() );
17 ostream_iterator< int > output( cout, " " );
18
19 cout << "Vector integers contains: ";
20 copy( integers.cbegin(), integers.cend(), output );
21
22 cout << "
First element of integers: " << integers.front()
23 << "
Last element of integers: " << integers.back();
24
25 integers[ 0 ] = 7; // set first element to 7
26 integers.at( 2 ) = 10; // set element at position 2 to 10
27
28 // insert 22 as 2nd element
29 integers.insert( integers.cbegin() + 1, 22 );
30
31 cout << "
Contents of vector integers after changes: ";
32 copy( integers.cbegin(), integers.cend(), output );
33
34 // access out-of-range element
35 try
36 {
37 integers.at( 100 ) = 777;
38 } // end try
39 catch ( out_of_range &outOfRange ) // out_of_range exception
40 {
41 cout << "
Exception: " << outOfRange.what();
42 } // end catch
43
44 // erase first element
45 integers.erase( integers.cbegin() );
46 cout << "
Vector integers after erasing first element: ";
47 copy( integers.cbegin(), integers.cend(), output );
48
49 // erase remaining elements
50 integers.erase( integers.cbegin(), integers.cend() );
51 cout << "
After erasing all elements, vector integers "
52 << ( integers.empty() ? "is" : "is not" ) << " empty";
53
54 // insert elements from the array values
55 integers.insert( integers.cbegin(), values.cbegin(), values.cend() );
56 cout << "
Contents of vector integers before clear: ";
57 copy( integers.cbegin(), integers.cend(), output );
58
59 // empty integers; clear calls erase to empty a collection
60 integers.clear();
61 cout << "
After clear, vector integers "
62 << ( integers.empty() ? "is" : "is not" ) << " empty" << endl;
63 } // end main
Vector integers contains: 1 2 3 4 5 6
First element of integers: 1
Last element of integers: 6
Contents of vector integers after changes: 7 22 2 10 4 5 6
Exception: invalid vector<T> subscript
Vector integers after erasing first element: 22 2 10 4 5 6
After erasing all elements, vector integers is empty
Contents of vector integers before clear: 1 2 3 4 5 6
After clear, vector integers is empty
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.
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_iterator
s. 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.
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.
Common Programming Error 15.2
The vector must not be empty; otherwise, the results of front and back are undefined.
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.)
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.
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.
Normally erase destroys the objects that are erased from a container. However, erasing an element that contains a pointer to a dynamically allocated object does not delete the dynamically allocated memory—this can lead to a memory leak. If the element is a unique_ptr, the unique_ptr would be destroyed and the dynamically allocated memory would be deleted. If the element is a shared_ptr, the reference count to the dynamically allocated object would be decremented and the memory would be deleted only if the reference count reached 0.
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.
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.]