Vector (C++)

In C++‘s STL, vectors are dynamic arrays that can change in size. It can only store values of the same data type (i.e., a vector declared with int can only store integers).

#include <vector>
 
std::vector<type> name(int size);
std::vector<std::vector<type>> name (int size, vector<int>(int size));

Vectors are implemented with ordinary arrays that are re-allocated if they’re at full capacity. Memory is allocated for a new vector with a greater capacity than is needed (usually $2\times$) and memory is freed. For larger $n$, this can get expensive, so we should specify its size at definition wherever possible.

Just like arrays, it has $\Omega (1)$ access time and $O(n)$ search time and suffers from the same problems with element deletion.

Constructor

To initialise a 1D vector with an initial size (and optionally a default value), we can use the following code:

vector<int> vec(size, 0);

The compiler will often take a well-reasoned default value.

To initialise a 2D vector with an initial size, we extend the same syntax as above:

vector<vector<int>> vec(rows, vector<int>(cols, DEFAULT_VAL));

Methods

Structure manipulations:

• push_back(): adds an element to the rear of the list. On average, this has a time complexity of $O(1)$.
• clear(): wipes the contents of the vector.
• resize(n): resize the vector to store $n$ elements.

Element access:

• begin() and end(): returns iterator of the beginning or end indices of the vector. It also supports rbegin() and rend().
• at(): memory-safe way to access vector elements. It throws an error if the element is out of bounds.

Other useful methods include:

• size(), which gives us the size of the vector.
• empty() is a Boolean.