5.2 vector Operations

In this section, each of the member functions provided by the vector datatype is described in more detail. These member functions provide the basic operations for vectors. They can be greatly extended through the generic algorithms described in Chapter 13.

Because it is a class template, the declaration of a vector must include a designation of the component type. This can be a primitive language type, like an int or double, a pointer type, or a user-defined type. A user-defined type must implement a copy constructor, as this constructor is used to initialize newly created elements.

---

REMEMBER -- Elements that are held by a vector must define a copy constructor. Although not used by functions in the vector class, some of the generic algorithms also require vector elements to recognize either the equivalence operator==() or the relational less-than operator<().

---

Like an array, a vector is most commonly declared with an integer argument that describes the number of elements the vector will hold and an initial value for each element:

std::vector<int> vec_one(10,0);

If the type has a default constructor, as it does in this case, then the second argument can be omitted.

For vectors as well as other C++ Standard Library containers, an allocator type can also be provided as an additional template parameter:

std::vector<int,allocator<int> >

These two declarations are synonymous. Note that if the allocator template parameter is provided explicitly, then its type must match the contained type.

There are a variety of other forms of constructor that can also be used to create vectors. 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.

std::vector<int> vec_two(5, 3);       // initialization by
                                      // assignment

std::vector<int> vec_three;           // no elements
std::vector<int> vec_four(vec_two);   // copy constructor

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 C++ Standard Library that support iterators.

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

---

NOTE -- Because it requires the ability to define a member function with a template argument different from the class template, some compilers may not yet support the initialization of containers using 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 sub-sequence of an existing container. The values from this sub-sequence then become the new elements in the receiver.

The second version of assign() takes a count and a value. The value must be the same type as the container elements. After the call, the container holds only the number of elements specified by the count, and all elements in the container are equal to the value provided.

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

If a destructor is defined for the container element type, the destructor is 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 takes on the values of the receiver, while the receiver assumes those of the argument. A swap is very efficient, and should be used in preference to an explicit element-by-element transfer where appropriate.

vec_three.swap(vec_four); 

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

std::vector<int>::iterator location;

In addition to iterator, a vector defines the following types:

Table 9: Type definitions for class vector

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. Also like arrays, there are no attempts to verify the validity of the index values. Indexing a constant vector yields a constant reference. Attempts to index a vector outside the range of legal values generates unpredictable and spurious results:

std::cout << vec_five[1] << std::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, but it will throw an out-of-range exception if the argument is invalid.

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.

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

In general, there are three different sizes associated with any vector:

• the number of elements currently being held by the vector

• the maximum size to which the vector can be expanded without requiring that new storage be allocated

• the upper limit on the size of any vector.

These three values are yielded by the member functions size(), capacity(), and max_size(), respectively:

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

The size is simply the number of elements in the vector. The maximum size is usually limited only by the amount of available memory, or the largest value that can be described by the datatype size_type. The capacity is more difficult to characterize. As noted in Section 5.2.5, 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.

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 datatype 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, 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, no reallocation takes place. Invoking reserve() does not change the size of the vector, nor the element values themselves. However, the elements may change location in memory 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.

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

The member function resize() takes two arguments, a size and a value of the container member type. The value argument is optional if the member type has a default constructor. resize() changes the size of the vector to the size specified, adding or erasing elements as needed. If elements are added, their initial contents will be copied from the value argument, or created using the member type's default constructor if no value is provided.

If a destructor is defined for the element type, the destructor is called for any elements that are removed from the collection:

// resize to 12 elements, adding values of 17 if necessary
vec_five.resize (12, 17); 

---

NOTE -- A vector stores values in a single large block of memory. A deque, on the other hand, employs a number of smaller blocks. This difference may be important on machines that limit the size of any single block of memory, because in such cases a deque will be able to hold much larger collections than a vector.

---

As noted earlier, unlike an ordinary array, the class template vector can increase or decrease in size in certain circumstances. 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, a new block is allocated and the elements are copied to the new storage.

---

NOTE -- Even adding a single element to a vector can, in the worst case, require time proportional to the number of elements in the vector, as each element is moved to a new location. If insertions are a prominent feature of your current problem, you should explore the possibility of using containers which are optimized for insert operations, such as lists or sets.

---

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 with value of 21 to vec_five

The corresponding removal operation is pop_back(), which decreases the size of the vector, but does not change its capacity. If the element type defines a destructor, the destructor is called on the element being removed. Again, this operation is very efficient. (The class template deque permits values to be added and removed from both the back and the front of the collection, as described in Chapter 7.)

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
std::vector<int>::iterator where = 
      std::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 sub-sequence from another container. The range of values described by the sequence is inserted into the vector. Again, using this function is preferable to using a sequence of individual insertions because at most a single allocation is performed.

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

---

NOTE -- Once more, it is important to remember that should an insertion cause reallocation, all references or pointers to elements in the vector, and all iterators associated with the vector become invalid.

---

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(). The function has two forms:

• the first takes a single iterator and removes an individual value

   
vec_five.erase(where);

• 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 is invoked on the eliminated values:

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

---

NOTE -- When an element is erased, all references or pointers to elements after the erased element become invalid. Iterators that refer to a position after the erased element also become invalid.

---

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, but 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 std::find() or std::count() can be used for this purpose (see Section 13.3.1 and Section 13.6.1). For example, the following statement tests to see whether an integer vector contains an element with a value of 17:

std::find(vec_five.begin(), vec_five.end(), 17);

If your compiler does not support partial specialization, then you must use the following interface instead:

int num = 0;
std::count(vec_five.begin(), vec_five.end(), 17, num);

if (num)
   std::cout << "contains a 17" << std::endl;
else
   std::cout << "does not contain a 17" << std::endl;

A vector does not automatically maintain its values in sequence. However, a vector can be placed in order using the generic algorithm std::sort() (see Section 14.2). The simplest form of sort() uses operator<() for comparisons. An alternative version of sort() 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
std::sort(aVec.begin(), aVec.end());

// sort descending, specifying the ordering function explicitly
std::sort(aVec.begin(), aVec.end(), std::greater<int>() );

// alternate way to sort descending
std::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 std::merge() (see Section 14.5).

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

Binary search algorithms (see Section 14.4) can also be used on a sorted vector. These searches are more efficient than a linear traversal algorithm such as find(). If your problem involves multiple searches on a vector, sorting the vector and then using an efficient search is a good strategy.

Most of the algorithms described in Part IV can be used with vectors, but some are more useful than others. For example, the maximum value in a vector can be determined as follows:

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

Table 10 summarizes some of the algorithms that are especially useful with vectors:

Table 10: Generic algorithms useful with vectors