Vector in C++ STL

std::vector is a dynamic array: contiguous in memory like a C array, but it knows its size, grows automatically and frees itself. It's the container you'll use most – in contests it replaces almost every array – so it's worth knowing deeply.

The STL in one picture

Algorithms don't know about containers – they work on iterator ranges. That's why one std::sort sorts vectors, arrays, deques and strings.

Creating and using vectors

#include <iostream>
#include <vector>

void print(const std::vector<int>& v) {
    for (int x : v) std::cout << x << ' ';
    std::cout << "(size " << v.size() << ")\n";
}

int main() {
    std::vector<int> a;                    // empty
    std::vector<int> b(5);                 // five zeros
    std::vector<int> c(4, 7);              // four sevens
    std::vector<int> d{3, 1, 4, 1, 5};     // from a list
    print(a); print(b); print(c); print(d);

    d.push_back(9);                        // add at the end
    d.pop_back();                          // remove from the end
    d[0] = 30;                             // no bounds check
    std::cout << d.front() << ' ' << d.back() << ' ' << d.at(2) << '\n';   // at() checks bounds
    std::cout << std::boolalpha << a.empty() << '\n';
    return 0;
}

(size 0)
0 0 0 0 0 (size 5)
7 7 7 7 (size 4)
3 1 4 1 5 (size 5)
30 5 4
true

size, capacity and reserve

#include <iostream>
#include <vector>

int main() {
    std::vector<int> v;
    std::size_t last_cap = v.capacity();
    for (int i = 0; i < 20; i++) {
        v.push_back(i);
        if (v.capacity() != last_cap) {             // the vector reallocated
            last_cap = v.capacity();
            std::cout << "size " << v.size() << " -> capacity " << last_cap << '\n';
        }
    }
    std::vector<int> w;
    w.reserve(1000);                                // allocate once up front
    std::cout << "reserved: size " << w.size() << ", capacity " << w.capacity() << '\n';
    return 0;
}

size 1 -> capacity 1
size 2 -> capacity 2
size 3 -> capacity 4
size 5 -> capacity 8
size 9 -> capacity 16
size 17 -> capacity 32
reserved: size 0, capacity 1000

size() is how many elements exist; capacity() is how many fit before the vector must reallocate. When full, it allocates a bigger block (here doubling) and moves the elements, so push_back is O(1) on average. If you know the final size, reserve avoids the reallocations. (Growth factors differ between library implementations.)

insert, erase and emplace_back

#include <algorithm>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

int main() {
    std::vector<int> v{10, 20, 30, 40, 50};
    v.insert(v.begin() + 2, 25);                 // insert before index 2
    v.erase(v.begin());                          // erase the first element
    v.erase(v.begin() + 1, v.begin() + 3);       // erase a range [1, 3)
    for (int x : v) std::cout << x << ' ';
    std::cout << '\n';

    std::vector<int> marks{45, 72, 38, 90, 33, 61};
    std::erase_if(marks, [](int m) { return m < 40; });   // C++20: remove all failing marks
    for (int m : marks) std::cout << m << ' ';
    std::cout << '\n';

    std::vector<std::pair<std::string, int>> scores;
    scores.emplace_back("Asha", 91);             // builds the pair in place
    scores.push_back({"Ravi", 74});              // builds a temporary, then moves it
    for (const auto& [name, s] : scores) std::cout << name << '=' << s << ' ';
    std::cout << '\n';
    return 0;
}

20 40 50 
45 72 90 61 
Asha=91 Ravi=74 

2D vectors

#include <iostream>
#include <vector>

int main() {
    int rows = 3, cols = 4;
    std::vector<std::vector<int>> grid(rows, std::vector<int>(cols, 0));   // 3 x 4 zeros
    for (int r = 0; r < rows; r++)
        for (int c = 0; c < cols; c++) grid[r][c] = r * cols + c;

    for (const auto& row : grid) {
        for (int x : row) std::cout << x << '\t';
        std::cout << '\n';
    }

    std::vector<std::vector<int>> adj(4);        // adjacency list: rows of different lengths
    adj[0] = {1, 2};
    adj[2] = {3};
    for (std::size_t u = 0; u < adj.size(); u++) std::cout << u << " has " << adj[u].size() << " neighbours\n";
    return 0;
}

0	1	2	3	
4	5	6	7	
8	9	10	11	
0 has 2 neighbours
1 has 0 neighbours
2 has 1 neighbours
3 has 0 neighbours

Practice

Summary