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 template class, 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 . Header is non-standard and deprecated. GCC accepts both, but gives a compiler warning when is used.

A vector is initialized using: std::vector instance; 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.

• informative
• vector::front - Returns reference to first element of vector.
• vector::back - Returns reference to last element of vector.
• vector::size - Returns number of elements in the vector.
• vector::empty - Returns true if vector has no elements.
• vector::capacity - Returns current capacity (allocated memory) of vector.
• standard operations
• vector::insert - Inserts elements into a vector (single & range), shifts later elements up. O(n) time.
• vector::push_back - Appends (inserts) an element to the end of a vector, allocating memory for it if necessary. Amortized O(1) time.
• vector::erase - Deletes elements from a vector (single & range), shifts later elements down. O(n) time.
• vector::pop_back - Erases the last element of the vector, O(1) time. Does not usually reduce the memory overhead of the vector Amortized O(1) time.
• vector::clear - Erases all of the elements. (For most STL implementations this is O(1) time and does not reduce capacity)
• allocation/size modification
• vector::reserve - Changes capacity (allocates more memory) of the vector, if needed. In many STL implementations capacity can only grow, and is never reduced. O(n) if the vector expands. O(1) if not.
• vector::resize - Changes the vector size. O(n) time.
• iteration
• vector::begin - Returns an iterator to start traversal of the vector.
• vector::end - Returns an iterator that points just beyond the end of the vector.

Vector usage example

1. include
2. include

using namespace::std;

int main(){

vector myVector;   // declare a vector of integers named "myVector"

vector::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 output will be the following:

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.

Current vector size = 4
The last element, 4, is being removed.

Current vector size = 3
myVector = 1 2 3

The vector is now empty again.

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.

References

• William Ford, William Topp. Data Structures with C++ and STL, Second Edition. Prentice Hall, 2002. ISBN 0-13-085850-1. Chapter 4: The Vector Class, pp.195–203.

External links

• SGI STL specification of vector
• C++ reference: vector
• C++ Header description