0
C++ Fundamentals

Lesson 05 · 18 min

vector — Your Default Array

size, push_back, indexing, sort, and the mistakes that cause TLE/WA.

std::vector

A vector<T> is a dynamic array: contiguous memory, O(1) index, amortized O(1) push_back.

Essentials

vector<int> a;           // empty
vector<int> b(n, 0);     // n zeros
a.push_back(3);
int n = (int)a.size();
a[i] = 5;                // must be in range [0, size)
sort(a.begin(), a.end());

Index safety

a[a.size()] is out of bounds. Valid indices: 0 .. size()-1.

2D vectors

vector<vector<int>> g(n, vector<int>(m, 0));

Common DSA moves

  • Frequency: vector<int> freq(26); for lowercase letters
  • Prefix: vector<long long> pref(n+1); pref[i+1]=pref[i]+a[i];

Don't

  • push_back in a hot inner loop without reserve if you know size (micro-opt)
  • Compare vectors with wrong length assumptions

Rules to remember

  • size() returns size_t — cast to int when mixing with int loops.
  • sort(a.begin(), a.end()) for ascending.
  • Empty check: a.empty() or a.size()==0.
  • Out-of-bounds [i] = undefined behavior — WA or crash.

Check yourself

1. Valid indices for vector of size 5?

Practice what you learned

Contains DuplicateEasyRotate ArrayMedium