std::vector — The Workhorse Container

std::vector is the container you reach for first. Use array, list, deque, etc. only when you have a measured reason.

Memory Model

A vector holds three pointers internally:

┌──────────┬──────────┬──────────┬──────────┬─────┬─────┐
│   1      │   2      │   3      │  (free)  │ ... │ ... │
└──────────┴──────────┴──────────┴──────────┴─────┴─────┘
^                                ^                      ^
begin()                          end()                  begin() + capacity()

• size() = number of elements you've put in
• capacity() = how many elements fit before reallocating
• When size == capacity and you push another, the vector allocates a bigger block (typically 1.5× or 2× larger), copies/moves everything, frees the old block

That's why push_back is amortised O(1): occasionally expensive, but cheap per operation overall.

Reserve to Avoid Reallocations

If you know roughly how many elements you'll add:

vector<int> v;
v.reserve(1000);            // pre-allocate; no reallocations under 1000
for (int i = 0; i < 1000; i++) v.push_back(i);

A measurable speed-up in tight loops.

Construction Recipes

vector<int> v1;                     // empty
vector<int> v2(5);                  // [0,0,0,0,0]
vector<int> v3(5, 7);               // [7,7,7,7,7]
vector<int> v4 = {1, 2, 3};         // initialiser-list
vector<int> v5(v4);                 // copy
vector<int> v6(v4.begin()+1, v4.end()); // range copy
// 2D — vector of vectors
vector<vector<int>> grid(rows, vector<int>(cols, 0));
// From any iterable / range
string s = "hello";
vector<char> cs(s.begin(), s.end());

Adding & Removing

v.push_back(42);            // append
v.emplace_back(args...);    // construct in place — slightly faster
v.pop_back();               // remove last (no return value)
v.insert(v.begin(), 99);            // O(n) — shifts everything
v.insert(v.begin() + 2, 3, 0);       // insert 3 zeros at index 2
v.erase(v.begin() + 1);              // remove index 1
v.erase(v.begin(), v.begin() + 3);   // erase first 3
v.clear();                           // remove all (capacity may stay)

Access

v[0];           // first element — no bounds check
v.at(0);        // bounds-checked — throws std::out_of_range
v.front();      // first — UB on empty
v.back();       // last  — UB on empty
v.data();       // raw T* — for C APIs

In tight inner loops use []. In code processing user input, use at() or check yourself.

Iteration — Three Styles

// 1. Range-based for (preferred)
for (int x : v)            cout << x;
for (int& x : v)           x *= 2;             // modify
for (const int& x : v)     cout << x;          // big elements: avoid copy
// 2. Indexed
for (size_t i = 0; i < v.size(); ++i) cout << v[i];
// 3. Iterators (for STL algorithms)
for (auto it = v.begin(); it != v.end(); ++it) cout << *it;

STL Algorithms — The Real Power

#include <algorithm>
#include <numeric>
sort(v.begin(), v.end());                              // ascending
sort(v.begin(), v.end(), greater<int>{});               // descending
sort(v.begin(), v.end(), [](int a, int b){ return abs(a) < abs(b); }); // custom
reverse(v.begin(), v.end());
int sum  = accumulate(v.begin(), v.end(), 0);
int prod = accumulate(v.begin(), v.end(), 1, multiplies<int>{});
bool ok = all_of (v.begin(), v.end(), [](int x){ return x > 0; });
bool any = any_of(v.begin(), v.end(), [](int x){ return x > 100; });
int  cnt = count(v.begin(), v.end(), 5);
auto it = find(v.begin(), v.end(), 42);
if (it != v.end()) cout << "found at " << (it - v.begin());
auto mx = *max_element(v.begin(), v.end());
auto mn = *min_element(v.begin(), v.end());

> One mental shift from C: algorithms operate on iterator ranges, not containers. (begin, end) shows up everywhere — get used to it.

Removing Elements That Match a Predicate

The classic erase-remove idiom:

v.erase(remove_if(v.begin(), v.end(),
                  [](int x){ return x < 0; }),
        v.end());

remove_if shifts unwanted elements to the back and returns an iterator to "new end"; erase chops them.

C++20 simplified this:

erase_if(v, [](int x){ return x < 0; });    // C++20

Iterator Invalidation ⚠️

Modifying a vector can invalidate iterators/pointers:

Operation	Invalidates
push_back (causes realloc)	All iterators/pointers
insert / erase	Iterators at and after the point
reserve (capacity grows)	All iterators/pointers

for (int x : v) {
    if (x == 0) v.push_back(99);   // ❌ may invalidate the iterator
}

Either reserve up front, or build a separate vector of additions.

Passing Vectors to Functions

void print(const vector<int>& v);    // read-only, no copy   ← default choice
void grow (vector<int>& v);           // can modify caller
void take (vector<int>  v);           // owns a copy — only when you really need one
void take (vector<int>&& v);          // takes ownership via move

Comparison & Equality

Vectors of the same type support ==, !=, <, > (lexicographic):

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

When NOT to Use vector

Use instead	Reason
std::array	Fixed size known at compile time, on the stack
std::deque	Need fast insertion at both ends
std::list	Need O(1) splice / no element invalidation
std::set	Sorted, unique, fast lookup
std::unordered_map	Hash-based lookup	Cheat-Sheet	Need	Code
Make	vector v; or vector v{1,2,3};
Append	v.push_back(x);
Pop last	v.pop_back();
Size	v.size();
Iterate	for (auto& x : v)
Sort	sort(v.begin(), v.end());
Find	find(v.begin(), v.end(), x);
Reverse	reserve(v.begin(), v.end());
Sum	accumulate(v.begin(), v.end(), 0);
Erase matching	erase_if(v, pred);
Pre-allocate	v.reserve(n);

You now own the most-used container in C++. Next: classes — the foundation of OOP and the STL itself.