Vector (STL):

Vectors (or std::vector) are a C++ implementation of the dynamic array data structure. Their interface emulates the behavior of a C array (i.e., capable of fast random access) but with the additional ability to automatically resize itself when inserting or removing an object.

A vector is a template class that is a part of the C++ Standard Template Library. They can store any type, but are limited to storing only one type per instance. Therefore, they could not store data in the form of both char and int within the same vector instance. Vectors can, however, store pointers to several class objects provided they are all from the same class. Vectors provide a standard set of methods for accessing elements, adding elements to the start or end, deleting elements and finding how many elements are stored.

Comparison with arrays

In C++, arrays are contiguous pieces of memory. They are somewhat like blocks aligned together, each block is then given a number, and to look at the contents of each block one only has to supply the number of the block. All the elements of an array must be of the same type.

A vector is similar to an array but with extended functionality. One of the features of a vector is that if you use the at() function, an exception will be thrown if you try to access an element that doesn't exist. A vector is a class template, a generic array of whatever type you want it to be. This gives vectors a great deal of flexibility, as they can be used as an array of anything. For instance, you can even have a vector of vectors. Vectors can automatically detect out of bounds errors (see Bounds checking) by using the at() method, or skip bounds checking by using operator[]. When using the latter they are very fast for random access. Vectors also have a number of useful functions which can tell you certain properties of the vector. For a full description of each function see functions further down the page.

Usage

A C++ program that is to use vectors must #include <vector>. Header <vector.h> is non-standard and deprecated. GCC accepts both, but gives a compiler warning when <vector.h> is used.

where "type" is the data type the vector is to store, and "instance" is the variable name of the vector.

"Type" can be a primitive or any user defined class or struct. However care must be taken to avoid object slicing.

Functions

The vector class models the Container concept, which means it has begin(), end(), size(), max_size(), empty(), and swap() methods.

Vector usage example

#include <iostream>
#include <vector>
using namespace::std;
 
 
int main(){
 
 vector<int> myVector;   // declare a vector of integers named "myVector"
 vector<int>::iterator Iter;   // creates an iterator necessary to traverse vector
 // print a message if the vector is initially empty
 if( myVector.empty() )
 {
      cout << endl << "The vector is currently empty.";
 }
 cout << endl;
 cout << "Adding 1 to the end of the vector." << endl;
 myVector.push_back(1);	// add 1 to the end of the vector
 cout << "Adding 2 to the end of the vector." << endl;
 myVector.push_back(2);	// add 2 to the end of the vector
 cout << "Adding 3 to the end of the vector." << endl;
 myVector.push_back(3);	// add 3 to the end of the vector
 cout << "Adding 4 to the end of the vector." << endl;
 myVector.push_back(4);	// add 4 to the end of the vector
 // show the size of the vector
 cout << endl << "Current vector size = " << myVector.size() << endl;
 int atTheEnd;
 atTheEnd = myVector.back();	// assign the last element to variable "atTheEnd"
 cout << "The last element, " << atTheEnd << ", is being removed." << endl << endl;
 myVector.pop_back();	// remove the element at the end of the vector
 // show the size of the vector again
 cout << "Current vector size: " << myVector.size() << endl;
 // printing the contents of a vector
 // requires traversing through it with an iterator (declared above as "Iter")
 cout << "myVector =";
 for (Iter = myVector.begin(); Iter != myVector.end(); Iter++ )
 {
      cout << " " << *Iter;
 }
 cout << endl;
 cout << endl;
 // if the vector isn't empty
 // use the clear() function to empty it
 if( !myVector.empty() )
 {
      myVector.clear();
 }
 // print out a successful message if cleared correctly
 if( myVector.empty() )
 {
      cout << "The vector is now empty again." << endl;
 }
 cout << endl;
 
}

The vector is currently empty.
Adding 1 to the end of the vector.
Adding 2 to the end of the vector.
Adding 3 to the end of the vector.
Adding 4 to the end of the vector.

Vector visualization

Semantically picturing the vector push_back( data ) operation. Note the size of the vector increases from 6 to 7 after the operation.

Semantically picturing the vector pop_back() operation. Note the size of the vector decreases from 7 to 6 after the operation.

Semantically picturing the vector resize( int ) operation. Note the size of the vector increases to 9, and the new elements are filled with a default value.

Useful metaphor

It is often helpful to use examples from everyday life as metaphors for the different methods of data storage. In this way, one could think of a vector as people on a crowded subway train. Anytime a person steps onto the train, it represents the v.push_back(data) function, with those persons representing the recurring data type. Upon reaching their destination, the first person to enter would be standing furthest from the platform. This person would be referred to by the v.front() operation. Closest to the exit platform would be the v.back() reference—the last person to have entered. Although very similar to a traditional Last-In-First-Out data structure (such as a stack), the vector class differs slightly in that it also has an insert function. This insert function would be analogous to somebody from a different car of the train entering from the sides.

Pros and cons

The most convenient part of the vector data structure is its ability to quickly and easily allocate the necessary memory needed for specific data storage without explicit memory management. This makes them particularly useful for storing data in lists whose length may not be known prior to setting up the variable, but where removal from the array (other than perhaps at the end) is rare.

Like other STL containers, vectors may contain both primitive data types and complex, user-defined classes or structs. Unlike other STL containers, such as deques and lists, vectors allow the user to denote an initial capacity for the container, which, if used correctly can allow for faster execution of the program.

One major benefit of vectors is that they also allow random access; that is, an element of a vector may be referenced in the same manner as elements of arrays are by array indices whereas linked-lists and sets do not support random access or pointer arithmetic. Array-style pointer arithmetic can also be used with vectors - for instance the address of the (zero-indexed) 7th element in a vector v is &v[6].

Erasing elements from a vector or even clearing it entirely does not necessarily free any of the memory associated with that element. The rationale here is that a good estimate of the future size of the vector is the maximum size of the vector since its creation.

Vectors are also inefficient at removing or inserting elements other than at the end. Such operations have O(n) (see Big-O notation) complexity compared with O(1) for linked-lists. This is offset by the speed of access - access to a random element in a vector is of complexity O(1) compared with O(n) for general linked-lists and O(log n) for link-trees.

Vector (STL)

Contents