Vector Operations

Each of the member functions provided by the vector data type will shortly be described in more detail. Note that while member functions provide basic operations, the utility of the data structure is greatly extended through the use of the generic algorithms described in Chapters 13 and 14.

Requirements of an Element Type

Because it is a template class, the declaration of a vector must include a designation of the component type. This can be a primitive language type (such as integer or double), a pointer type, or a user-defined type. In the latter case, the user-defined type must implement a default constructor, as this constructor is used to initialize newly created elements. A copy constructor, either explicitly or implicitly defined, must also exist for the container element type. Like an array, a vector is most commonly declared with an integer argument that describes the number of elements the vector will hold:

   vector<int> vec_one(10);
 

The constructor used to create the vector in this situation is declared as explicit, which prevents it being used as a conversion operator. (This is generally a good idea, since otherwise an integer might unintentionally be converted into a vector in certain situations.)

There are a variety of other forms of constructor that can also be used to create vectors. In addition to a size, the constructor can provide a constant value that will be used to initialize each new vector location. If no size is provided, the vector initially contains no elements, and increases in size automatically as elements are added. The copy constructor creates a clone of a vector from another vector.

   vector<int> vec_two(5, 3);      // copy constructor
    vector<int> vec_three;
    vector<int> vec_four(vec_two);  //  initialization by assignment
 

A vector can also be initialized using elements from another collection, by means of a beginning and ending iterator pair. The arguments can be any form of iterator; thus collections can be initialized with values drawn from any of the container classes in the standard library that support iterators.

   vector <int> vec_five (aList.begin(), aList.end());
 

Constructors and Iterators

A vector can be assigned the values of another vector, in which case the target receives a copy of the argument vector.

   vec_three = vec_five;
 

The assign() member function is similar to an assignment, but is more versatile and, in some cases, requires more arguments. Like an assignment, the existing values in the container are deleted, and replaced with the values specified by the arguments. There are two forms of assign(). The first takes two iterator arguments that specify a subsequence of an existing container. The values from this subsequence then become the new elements in the receiver. The second version of assign() takes a count and an optional value of the container element type. After the call the container will hold only the number of elements specified by the count, which are equal to either the default value for the container type or the initial value specified.

   vec_six.assign(list_ten.begin(), list_ten.end());
    vec_four.assign(3, 7);      // three copies of the value 7
    vec_five.assign(12);        // twelve copies of value zero
 

If a destructor is defined for the container element type, the destructor will be called for each value removed from the collection.

Finally, two vectors can exchange their entire contents by means of the swap() operation. The argument container will take on the values of the receiver, while the receiver will assume those of the argument. A swap is very efficient, and should be used, where appropriate, in preference to an explicit element-by-element transfer.

   vec_three.swap(vec_four); 
 

The class vector includes a number of type definitions. These are most commonly used in declaration statements. For example, an iterator for a vector of integers can be declared in the following fashion:

vector<int>::iterator location;
 

In addition to iterator, the following types are defined:

The value being maintained by a vector at a specific index can be accessed or modified using the subscript operator, just like an ordinary array. And, like arrays, there currently are no attempts to verify the validity of the index values (although this may change in future releases). Indexing a constant vector yields a constant reference. Attempts to index a vector outside the range of legal values will generate unpredictable and spurious results:

   cout << vec_five[1] << endl;
    vec_five[1] = 17;
 

The member function at() can be used in place of the subscript operator. It takes exactly the same arguments as the subscript operator, and returns exactly the same values.

The member function front() returns the first element in the vector, while the member function back() yields the last. Both also return constant references when applied to constant vectors.

   cout << vec_five.front() << " ... " << vec_five.back() << endl;
 

There are, in general, three different "sizes" associated with any vector. The first is the number of elements currently being held by the vector. The second is the maximum size to which the vector can be expanded without requiring that new storage be allocated. The third is the upper limit on the size of any vector. These three values are yielded by the member functions size(), capacity(), and max_size(), respectively.

   cout << "size: " << vec_five.size() << endl;
    cout << "capacity: " << vec_five.capacity() << endl;
    cout << "max_size: " << vec_five.max_size() << endl;
 

The maximum size is usually limited only by the amount of available memory, or the largest value that can be described by the data type size_type. The current size and capacity are more difficult to characterize. As we will note in the next section, elements can be added to or removed from a vector in a variety of ways. When elements are removed from a vector, the memory for the vector is generally not reallocated, and thus the size is decreased but the capacity remains the same. A subsequent insertion does not force a reallocation of new memory if the original capacity is not exceeded.

Memory Management

An insertion that causes the size to exceed the capacity generally results in a new block of memory being allocated to hold the vector elements. Values are then copied into this new memory using the assignment operator appropriate to the element type, and the old memory is deleted. Because this can be a potentially costly operation, the vector data type provides a means for the programmer to specify a value for the capacity of a vector. The member function reserve() is a directive to the vector, indicating that the vector is expected to grow to at least the given size. If the argument used with reserve() is larger than the current capacity, then a reallocation occurs and the argument value becomes the new capacity. (It may subsequently grow even larger; the value given as the argument need not be a bound, just a guess.) If the capacity is already in excess of the argument, then no reallocation takes place. Invoking reserve() does not change the size of the vector, nor the element values themselves (with the exception that they may potentially be moved should reallocation take place).

   vec_five.reserve(20);
 

A reallocation invalidates all references, pointers, and iterators referring to elements being held by a vector.

The member function empty() returns true if the vector currently has a size of zero (regardless of the capacity of the vector). Using this function is generally more efficient than comparing the result returned by size() to zero.

   cout << "empty is " << vec_five.empty() << endl;
 

The member function resize() changes the size of the vector to the value specified by the argument. Values are either added to or erased from the end of the collection as necessary. An optional second argument can be used to provide the initial value for any new elements added to the collection. If a destructor is defined for the element type, the destructor will be called for any values that are removed from the collection.

               // become size 12, adding values of 17 if necessary
    vec_five.resize (12, 17); 
 

As we noted earlier, the class vector differs from an ordinary array in that a vector can, in certain circumstances, increase or decrease in size. When an insertion causes the number of elements being held in a vector to exceed the capacity of the current block of memory being used to hold the values, then a new block is allocated and the elements are copied to the new storage.

Costly Insertions

A new element can be added to the back of a vector using the function push_back(). If there is space in the current allocation, this operation is very efficient (constant time).

   vec_five.push_back(21);   // add element 21 to end of collection
 

The corresponding removal operation is pop_back(), which decreases the size of the vector, but does not change its capacity. If the container type defines a destructor, the destructor will be called on the value being eliminated. Again, this operation is very efficient. (The class deque permits values to be added and removed from both the back and the front of the collection. These functions are described in Chapter 7, which discusses deques in more detail.)

More general insertion operations can be performed using the insert() member function. The location of the insertion is described by an iterator; insertion takes place immediately preceding the location denoted. A fixed number of constant elements can be inserted by a single function call. It is much more efficient to insert a block of elements in a single call, than to perform a sequence of individual insertions, because with a single call at most one allocation will be performed.

                                  // find the location of the 7
    vector<int>::iterator where = 
          find(vec_five.begin(), vec_five.end(), 7);
                              // then insert the 12 before the 7
    vec_five.insert(where, 12);
    vec_five.insert(where, 6, 14); // insert six copies of 14
 

The most general form of the insert() member function takes a position and a pair of iterators that denote a subsequence from another container. The range of values described by the sequence is inserted into the vector. Again, because at most a single allocation is performed, using this function is preferable to using a sequence of individual insertions.

   vec_five.insert (where, vec_three.begin(), vec_three.end());
 

Iterator Invalidation

In addition to the pop_back() member function, which removes elements from the end of a vector, a function exists that removes elements from the middle of a vector, using an iterator to denote the location. The member function that performs this task is erase(). There are two forms; the first takes a single iterator and removes an individual value, while the second takes a pair of iterators and removes all values in the given range. The size of the vector is reduced, but the capacity is unchanged. If the container type defines a destructor, the destructor will be invoked on the eliminated values.

   vec_five.erase(where);
                                     // erase from the 12 to the end
    where = find(vec_five.begin(), vec_five.end(), 12);
    vec_five.erase(where, vec_five.end());
 

The member functions begin() and end() yield random access iterators for the container. Again, we note that the iterators yielded by these operations can become invalidated after insertions or removals of elements. The member functions rbegin() and rend() return similar iterators, however these access the underlying elements in reverse order. Constant iterators are returned if the original container is declared as constant, or if the target of the assignment or parameter is constant.

A vector does not directly provide any method that can be used to determine if a specific value is contained in the collection. However, the generic algorithms find() or count() (Chapter 13, Find an Element Satisfying a Condition and Count the Number of Elements that Satisfy a Condition) can be used for this purpose. The following statement, for example, tests to see whether an integer vector contains the element 17.

int num = 0;
 count (vec_five.begin(), vec_five.end(), 17, num);
 
 if (num)
    cout << "contains a 17" << endl;
 else
    cout << "does not contain a 17" << endl;
 

Initializing Count

A vector does not automatically maintain its values in sequence. However, a vector can be placed in order using the generic algorithm sort() (Chapter 14, Sorting Algorithms). The simplest form of sort uses for its comparisons the less-than operator for the element type. An alternative version of the generic algorithm permits the programmer to specify the comparison operator explicitly. This can be used, for example, to place the elements in descending rather than ascending order:

    // sort ascending
 sort (aVec.begin(), aVec.end());
 
    // sort descending, specifying the ordering function explicitly
 sort (aVec.begin(), aVec.end(), greater<int>() );
 
    // alternate way to sort descending
 sort (aVec.rbegin(), aVec.rend());
 

A number of the operations described in Chapter 14 can be applied to a vector holding an ordered collection. For example, two vectors can be merged using the generic algorithm merge() (Chapter 14, Merge Ordered Sequences).

   // merge two vectors, printing output
 merge (vecOne.begin(), vecOne.end(), vecTwo.begin(), vecTwo.end(),
    ostream_iterator<int> (cout, " "));
 

Sorting a vector also lets us use the more efficient binary search algorithms (Chapter 14, Binary Search), instead of a linear traversal algorithm such as find().

Most of the algorithms described in Chapter 13 can be used with vectors. The following table summarizes a few of the more useful of these. For example, the maximum value in a vector can be determined as follows:

vector<int>::iterator where = 
    max_element (vec_five.begin(), vec_five.end());
 cout << "maximum is " << *where << endl;