vector and why it beats raw arrays

The problem vector solves

A raw array has a size fixed at compile time. If you need more, you write malloc, copy, free, and track capacity yourself. Get any step wrong and you get a leak or a corrupted heap.

vector is that code, written once, correct, and handed to you.

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;

    for (int i = 1; i <= 5; i++)
        v.push_back(i * i);

    cout << "size " << v.size() << "\n";     // 5
    for (int x : v) cout << x << " ";
    cout << "\n";                            // 1 4 9 16 25

    cout << v[2] << " " << v.front() << " " << v.back() << "\n";  // 9 1 25
    return 0;
}

The memory is heap memory, but you never call new or delete. When v goes out of scope its destructor frees the block. This is the C++ idea called RAII: the object's lifetime controls the resource's lifetime.

Creating one

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> a;                  // empty
    vector<int> b(5);               // 5 elements, all 0
    vector<int> c(5, 7);            // 5 elements, all 7
    vector<int> d = {3, 1, 4, 1, 5};// from a list
    vector<int> e = d;              // a full copy of d

    vector<vector<int>> grid(3, vector<int>(4, 0));   // 3x4 of zeros

    cout << b[0] << " " << c[0] << " " << d[2] << "\n";   // 0 7 4
    cout << grid.size() << "x" << grid[0].size() << "\n"; // 3x4
    return 0;
}

vector<int> b(5) zero-initialises, unlike a local int b[5] which holds garbage. That alone removes a common source of wrong answers.

⚠️

vector<int> v(5) makes five elements. vector<int> v{5} makes one element with the value 5. Round brackets mean "size", curly braces mean "contents". This bites everyone once.

size, capacity and the cost of push_back

A vector keeps two numbers: size (how many elements you have) and capacity (how many fit before it must move to a bigger block).

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    for (int i = 0; i < 10; i++) {
        v.push_back(i);
        cout << "size " << v.size() << " capacity " << v.capacity() << "\n";
    }
    return 0;
}

On g++ the capacity goes 1, 2, 4, 8, 16 — it doubles each time it runs out. When it doubles, it allocates a new block, copies everything across, and frees the old one.

So one push_back is usually O(1), and occasionally O(n) when it reallocates. Averaged over many pushes, the total work for n pushes is proportional to n, because 1 + 2 + 4 + ... + n is less than 2n. That is what amortised O(1) means, and it is a standard interview question.

If you know the count in advance, skip the reallocations:

C++

#include <iostream>
#include <vector>
using namespace std;

int main() {
    vector<int> v;
    v.reserve(1000000);          // one allocation, capacity 1000000
    for (int i = 0; i < 1000000; i++) v.push_back(i);
    cout << v.size() << " " << v.capacity() << "\n";
    return 0;
}

reserve changes capacity only. size is still 0 until you push. resize(n) changes the size, creating or removing elements.

Complexity you must remember

Operation	Cost	Note
`v[i]`	O(1)	direct address arithmetic
`push_back`	amortised O(1)	occasional reallocation
`pop_back`	O(1)
`insert` at front or middle	O(n)	everything after must shift
`erase` at middle	O(n)	same reason
`size()`	O(1)	it is stored, not counted
find by value	O(n)	scan every element

Elements are stored contiguously, exactly like a C array. That is why v[i] is as fast as a[i] and why the CPU cache loves vectors — the next element is already in the cache line.

[] versus at()

C++

#include <iostream>
#include <vector>
#include <stdexcept>
using namespace std;

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

    cout << v[10] << "\n";       // undefined behaviour, no check

    try {
        cout << v.at(10) << "\n";
    } catch (const out_of_range &e) {
        cout << "caught: " << e.what() << "\n";
    }
    return 0;
}

v[i] does no bounds checking, exactly like a C array — fast and unsafe. v.at(i) checks and throws std::out_of_range. Use at while debugging, [] in a tight loop you have already verified.

⚠️

v.size() returns an unsigned type. So for (int i = 0; i < v.size() - 1; i++) is a trap: on an empty vector, 0 - 1 becomes a huge unsigned number and the loop runs billions of times. Guard with if (!v.empty()) or write i + 1 < v.size().

Erasing correctly

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> v = {1, 2, 3, 4, 5, 6};

    // remove all even numbers, the standard way
    v.erase(remove_if(v.begin(), v.end(),
                      [](int x) { return x % 2 == 0; }),
            v.end());

    for (int x : v) cout << x << " ";
    cout << "\n";     // 1 3 5
    return 0;
}

This is the erase-remove idiom. remove_if does not shorten the vector — it shuffles the elements you want to keep to the front and returns an iterator to the new end. erase then chops off the tail. Doing it in one pass is O(n); erasing one by one in a loop is O(n^2) and also invalidates your iterator, which is a common crash.

Passing vectors around

C++

#include <iostream>
#include <vector>
using namespace std;

void readOnly(const vector<int> &v) { cout << v.size() << "\n"; }
void modify(vector<int> &v)         { v.push_back(99); }

int main() {
    vector<int> v = {1, 2, 3};
    readOnly(v);
    modify(v);
    cout << v.back() << "\n";   // 99
    return 0;
}

Never pass a vector by value unless you want a copy. A vector of a million ints is 4 MB, and passing it by value copies all of it on every call.

💡

Prefer vector over raw arrays in every C++ program you write from now on, including contest code. It knows its own size, cleans up after itself, and v.size() in a loop removes a whole family of off-by-one bugs.