Vector class in STL

Sun Sep 13 2026

10 mins

What is a vector

A vector in C++ is a dynamic sequence container implemented by the STL in the <vector> library. This means that it is a data structure that stores a collection of elements (of the same type) in a linear order and automatically manages its own memory.

Usage & methods

Declaration

vector<element_type> vector_name;
vector <vector <element_type>> vector_name; // 2D arrays

Initialization

vector<int> v = {10, 20, 30};
vector <char> c = {'a', 'b'};
vector <long> d(5, 10); // creates a vector of 5 elements all set to 10

Insert

There are two insert methods, depending where you want to insert the element:

• push_back(val) - inserts element at the end
• insert(iterator, val) - inserts element at the given iterator position

vector <int> v = {1, 2, 3};
v.push_back(4);
v.insert(v.begin(), 0);

the output is:

0 1 2 3 4

Access elements & updating elements

Can be accessed using the [] operator or the .at() method. The advantage of the latter is the bounds checking (throws std::out_of_range if the index is invalid).

We update elements using the index and the assignment operator (=).

Deleting elements

It depends on the position that we want to delete:

• erase(iterator) - it erases the element at position of the iterator in O(n) time
• pop_back() - removes the last element in O(1) time

vector<int> a = {1, 2, 3, 4};

v.pop_back(); // we delete 4
v.erase(find(v.begin(), v.end(), 1)); // we delete 1

Traversing vector

We can visit every element of a vector in multiple ways using an index based loop, range based loop or using iterators. Let’s explore every way below:

// index based loops - for
for(int i = 0; i < vec.size(); i++)
    // vec[i] is the current element

// range based loops
for(int x : vec)
    // x is every element

// iterators
for(auto it = vec.begin(); it != vec.end(); ++it)
    // *it is the current val of the element
    // best for generic use

Useful methods

• vec.begin() - returns an iterator pointing to the first element
• vec.end() - returns an iterator to the past the end element (a theoretical position after the end of the vector; does not contain valid data)
• vec.size() - returns the size of the vector
• vec.capacity() - returns the number of elements the vector can hold before reallocation
• vec.empty() - whether or not the vector is empty
• vec.reserve(n) - pre-allocates memory for n elements
• vec.clear() - empties the entire vector. The size will be 0
• vec.shrink_to_fit() - requests the container to release unused memory. vec.size() == vec.capacity() after the operation

Sorting methods provided by the STL

STL doesn’t provide a stand alone sorting method for the vector class because it separates containers (which store data, in this case the vector class) from algorithms (which manipulate data, such as sorting) using iterators. This design principle gives the STL modularity, making highly general methods that can be used by most of the containers.There are four major sorting algorithms that we’ll talk about. By default they all sort in ascending order.

I) std::sort

This is the standard algorithm. It uses introsort which begins as quick sort, but switches to heapsort if recursion depth goes too deep, preventing the worst case scenario for quick sort O(n²). It guarantees a O(N*logN) time complexity, being quite unstable (if two elements are considered equal, their original order is not always preserved).

 vector<int> v = {5, 2, 8, 1};

// ascending
std::sort(v.begin(), v.end());
// result is {1, 2, 5, 8}

// descending
std::sort(v.begin(), v.end(), [](int a, int b) {
    return a > b; });
// or std::sort(v.begin(), v.end(), std::greater<int>());
// result is {8, 5, 2, 1}

II) std::stable_sort

This algorithm uses a varation of merge sort. It guarantees if two elements are equal, they remain in the original order. It has a time complexity of O(N* logN) if enough auxiliary memory is available, else it has a O(N* log²N) complexity

std::vector<std::pair<int, char>> v = {{1, 'B'}, {2, 'A'}, {3, 'B'}, {4, 'A'}};

// Sort by category (the 'char')
std::stable_sort(v.begin(), v.end(), [](auto a, auto b) {
    return a.second < b.second;
});
// Result: {{2, 'A'}, {4, 'A'}, {1, 'B'}, {3, 'B'}}

III) std::partial_sort

This uses a heap sort variant. It organizes data so that the top M elements (M distance between the first iterator and the middle iterator) are placed at the beginning of the vector in sorted order. It has a time complexity of O(N * logM).

std::vector<int> v = {9, 2, 7, 3, 1, 8, 5, 4, 6};

// Sort only the 3 smallest elements to the front
std::partial_sort(v.begin(), v.begin() + 3, v.end());
// Result: {1, 2, 3,  ?, ?, ?, ?, ?, ?}

IV) std::nth_element

This methods partially sorts the vector so that the element at the Nth position is exactly the element that would be there if the vector was fully sorted. All elements before it, are strictly less or equal, and all element after are greater. It has a time complexity of O(N)

std::vector<int> v = {9, 2, 7, 3, 1, 8, 5, 4, 6};

// Find the median (the 4th index in a 0-indexed 9-element array)
std::nth_element(v.begin(), v.begin() + 4, v.end());

// v[4] is now guaranteed to be 5.
// Elements 0-3 are guaranteed to be <= 5 (e.g., {1, 3, 2, 4}).
// Elements 5-8 are guaranteed to be >= 5 (e.g., {8, 7, 9, 6}).

Searching methods provided by the STL

Such as the sorting case, STL doesn’t provide stand alone searching methods for the vector class. Instead, it provides general methods that work for every container using the help of iterators. There are four general methods.

I) std::find

This is the unsorted approach, working for a vector that is not sorted.

• it has a time complexity of O(N)
• it returns an iterator to the first matching element, or otherwise .end()

vector<int> v = {1, 2, 10, 4};

auto it = std::find(v.begin(), v.end(), 10);

if(it != v.end()) // checking if it exists

II) std::binary_search

It works for already sorted vectors, drastically reducing the search times.

• it has a time complexity of O(logN)
• it returns a bool if exists

vector<int> v = {1, 2 , 3};

if(std::binary_search(v.begin(), v.end(), 3))
    // true

III) std::lower_bound & std::upper_bound

It searches a sorted range and returns the first/last iterator to the element.

• it has a time complexity of O(logN)
• it returns an iterator to the position

std::vector<int> v = {10, 20, 30, 30, 50};
auto it = std::lower_bound(v.begin(), v.end(), 30);
// 'it' points to the first '30' (index 2).