Deitel & Associates, Inc. Logo

Back to
digg.png delicious.png blinkit.png furl.png
C++ How to Program, 5/e

© 2005
pages: 1500
Buy the Book!
Amazon logo
InformIT logo

23.2.1 vector Sequence Container (continued)

Line 17 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 19 and 20 demonstrate the size and capacity functions; each initially returns 0 for vector v in this example. Function size—available in every container—returns the number of elements currently stored in the container. Function capacity 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 23–25 use function push_back—available in all sequence containers—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 STL implementations have the vector double its capacity.

Performance Tip
Performance Tip 23.10
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. Programmers can use resize to control space usage better.

Lines 27 and 28 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, 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 allocation 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 8 elements.

The manner in which a vector grows to accommodate more elements—a time consuming operation—is not specified by the C++ Standard Document. C++ library implementors 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 implementors 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 32–33 demonstrate how to output the contents of an array using pointers and pointer arithmetic. Line 36 calls function printVector (defined at lines 53–61) to output the contents of a vector using iterators. Function template printVector receives a const reference to a vector (integers2) as its argument. Line 55 defines a const_iterator called constIterator that iterates through the vector and outputs its contents. Notice that the declaration in line 55 is prefixed with the keyword typename. Because printVector is a function template and vector< T > will be specialized differently for each function-template specialization, the compiler cannot tell at compile time whether or not vector< T >::const_iterator is a type. In particular specialization, const_iterator could be a static variable. The compiler needs this information to compile the program correctly. Therefore, you must tell the compiler that a qualified name, whether the qualifier is a dependent type, is expected to be a type in every specialization.

A const_iterator enables the program to read the elements of the vector, but does not allow the program to modify the elements. The for statement at lines 58–60 initializes constIterator using vector member function begin, which returns a const_iterator to the first element in the vector—there is another version of begin that returns an iterator that can be used for non-const containers. Note that a const_iterator is returned because the identifier integers2 was declared const in the parameter list of function printVector. 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 integers2.end(), which returns an 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. Functions begin and end are available for all first-class containers. The body of the loop dereferences iterator constIterator to get the value in the current element of the vector. 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 59) positions the iterator to the next element of the vector.

Performance Tip
Performance Tip 23.11
Use prefix increment when applied to STL iterators because the prefix increment operator does not return a value that must be stored in a temporary object.
Error-Prevention Tip
Error-Prevention Tip 23.4
Only random-access iterators support <. It is better to use != and end to test for the end of a container.

Line 40 declares a const_reverse_iterator that can be used to iterate through a vector backward. Line 41 declares a const_reverse_iterator variable tempIterator and initializes it to the iterator returned by function rend (i.e., the iterator for the ending point when iterating through the container in reverse). All first-class containers support this type of iterator. Lines 44–46 use a for statement similar to that in function printVector to iterate through the vector. In this loop, function rbegin (i.e., the iterator for the starting point when iterating through the container in reverse) and tempIterator delineate the range of elements to output. As with functions begin and end, rbegin and rend can return a const_reverse_iterator or a reverse_iterator, based on whether or not the container is constant.

Performance Tip
Performance Tip 23.12
For performance reasons, capture the loop ending value before the loop and compare against that, rather than having a (potentially expensive) function call for each iteration.

Page 1 | 2 | 3 | 4 | 5 | 6

Tutorial Index