C++ STL

vector

Complete lesson for vector using LEARNCODEGURU’s 6-level learning model — from basics to advanced practice, with C++ OOP and STL where relevant.

Basics — vector

Section: C++ STL. C++ std::vector — the default dynamic array: access, insert, erase, size vs capacity, and Array vs Vector.

What is a vector?

std::vector is a **dynamic array** that can grow and shrink at runtime.
Elements are stored in a **contiguous** block of memory (like a C array).
Supports **fast random access** with [] or bounds-checked at().
It is the **default sequence container** for most C++ programs.
Header: #include
**Real-life:** a resizable shopping list — add items anytime without fixing the length first.

Idea	Meaning
Dynamic size	Grows with `push_back` / shrinks with `pop_back`/`erase`
Contiguous	Elements sit side-by-side in memory
Random access	`v[i]` is O(1)
RAII	Frees its buffer automatically when destroyed

Why use vector?

No manual new[] / delete[] — safer than raw dynamic arrays.
Knows its own size() — no separate length variable.
Works with STL algorithms (sort, find, …) via iterators.
Cache-friendly contiguous layout — usually faster than linked lists.

Benefit	What you gain
Safety	Automatic cleanup; `at()` bounds check
Flexibility	Grow/shrink without rewriting buffers
Performance	O(1) index; good locality
STL-ready	Iterators + algorithms

Differences between Array and Vector

Compare a **C-style array** (int a[5]) with **std::vector**.
Also note: std::array is a fixed-size STL wrapper — closer to C arrays than to vector.

Feature	Array (C-style)	Vector (`std::vector`)
Size	Fixed at compile time (or fixed allocation)	Dynamic — can grow/shrink
Declaration	`int a[5];`	`vector v;`
Header	None (built-in)
Memory	Stack (local) or static / manual heap	Heap buffer managed by vector
Knows its length?	No (`sizeof` tricks are fragile)	Yes — `size()`
Bounds check	None with `a[i]`	`at(i)` throws; `[]` unchecked
Pass to functions	Decays to pointer — size lost	Passed by value/ref — keeps size
Copy / assign	No direct array assign	Copy/move supported
STL algorithms	Need pointer/size or begin/end	Native iterators `begin()`/`end()`
Growth	Cannot grow	`push_back`, `resize`, `reserve`
Insert / erase middle	Manual shifting	`insert` / `erase` (O(n))
RAII cleanup	Manual if heap-allocated	Automatic destructor
When to use	Fixed small sizes, low-level code	Default choice for most lists of data

Creating and initializing a vector

Empty, sized, filled, or braced-initialized.
Type is in the angle brackets: vector, vector, …

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

int main() {
    vector<int> a;                    // empty
    vector<int> b(5);                 // 5 zeros
    vector<int> c(5, 100);            // 5 copies of 100
    vector<int> d = {10, 20, 30};     // initializer list
    vector<string> names = {"Ann", "Bob"};

    cout << d.size() << "\n"; // 3
    return 0;
}

Accessing elements

v[i] — fast, **no** bounds check.
v.at(i) — bounds-checked; throws out_of_range if invalid.
front() / back() — first and last elements.
Range-for is the cleanest way to visit every element.

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

int main() {
    vector<int> v = {10, 20, 30};
    cout << v[0] << " " << v.at(1) << "\n";
    cout << v.front() << " " << v.back() << "\n";
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

Adding and removing elements

push_back(x) / emplace_back(...) — add at the end (amortized O(1)).
pop_back() — remove last element.
insert(pos, value) — insert before iterator (O(n) — shifts).
erase(pos) / erase(first, last) — remove (O(n) — shifts).
clear() — remove all elements (capacity may remain).

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

int main() {
    vector<int> v = {10, 20, 30};
    v.push_back(40);
    v.insert(v.begin() + 1, 15); // 10 15 20 30 40
    v.erase(v.begin());          // remove 10
    v.pop_back();                // remove 40
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

size() vs capacity()

size() — how many elements you currently have.
capacity() — how many elements fit before the buffer must grow.
When capacity is exceeded, vector **reallocates** (usually ~2×) and moves/copies elements.
reserve(n) — request capacity upfront to reduce reallocations.
shrink_to_fit() — request capacity closer to size (non-binding).

Member	Meaning
`size()`	Number of elements in use
`capacity()`	Allocated slots in the buffer
`empty()`	`size() == 0`
`reserve(n)`	Ensure capacity ≥ n
`resize(n)`	Change size (add default / erase)

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

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

Iterators with vector

begin() / end() give a half-open range for algorithms.
Random-access iterators — you can do it + n.
Prefer range-for unless you need the iterator position.

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

int main() {
    vector<int> v = {4, 1, 3, 2};
    sort(v.begin(), v.end());
    for (auto it = v.begin(); it != v.end(); ++it)
        cout << *it << " ";
    cout << "\n";
    return 0;
}

Key points to remember

vector = dynamic contiguous array — default container choice.
Prefer push_back growth; mid insert/erase are O(n).
Use at() when you want bounds checking.
Know size vs capacity; reserve for known sizes.
Arrays are fixed; vectors are flexible and STL-friendly.

Advanced — vector

Complexity cheat sheet

Know these costs for interviews and design.

Operation	Complexity
`v[i]`, `at(i)`, `front`, `back`	O(1)
`push_back` / `pop_back`	Amortized O(1)
`insert` / `erase` in middle	O(n)
`reserve` (no reallocation of elements beyond move)	O(n) if grows
Traverse all	O(n)

Iterator invalidation

Reallocation (growth) invalidates **all** iterators and references.
insert/erase invalidate iterators at/after the point of change.
Do not hold iterators across a push_back unless you reserved enough capacity.

2D vectors

vector> models a matrix / jagged table.
Rows can have different lengths (unlike a fixed 2D C array).

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

int main() {
    vector<vector<int>> m = {
        {1, 2, 3},
        {4, 5, 6}
    };
    cout << m[1][2] << "\n"; // 6
    return 0;
}

emplace_back vs push_back

emplace_back constructs in place from constructor args.
push_back typically takes an already-built object (may copy/move).
For heavy types, emplace_back can avoid an extra temporary.

Passing vectors to functions

Pass by const vector& to read without copying.
Pass by vector& to modify in place.
Return by value is fine — moves/elision make it efficient.

#include <vector>
using namespace std;

int sum(const vector<int>& v) {
    int s = 0;
    for (int x : v) s += x;
    return s;
}

Design tips

Default to vector; switch only with a measured reason.
reserve when you know the approximate final size.
Prefer algorithms + iterators over hand-written index loops when clearer.
Do not use vector for bit tricks unless you understand its proxy quirks.

Tricky Interview Points

Q1) What is std::vector?

Answer A dynamic contiguous array in the STL that can resize at runtime and provides random-access iterators.

Q2) Array vs vector — main difference?

Answer Arrays have fixed size; vectors can grow/shrink, know their size(), and manage memory automatically.

Q3) size() vs capacity()?

Answer size is the number of elements; capacity is how many fit before reallocation.

Q4) Time complexity of push_back?

Answer Amortized O(1); occasional reallocations make some calls O(n).

Q5) [] vs at()?

Answer [] is unchecked and faster; at() checks bounds and throws std::out_of_range.

Q6) Why is vector preferred over list usually?

Answer Better cache locality and O(1) random access; mid-insert on list is rarely worth the cost.

Q7) What happens when vector grows past capacity?

Answer It allocates a larger buffer, moves/copies elements, and frees the old buffer — iterators are invalidated.

Q8) How do you preallocate space?

Answer Call reserve(n) before many push_backs.

Q9) Is vector memory contiguous?

Answer Yes — &v[0] (when non-empty) addresses a contiguous block like a C array.

Q10) Can you use C algorithms on a vector?

Answer Yes via &v[0] or v.data() for a pointer, or preferably STL algorithms with begin/end.

Q11) Complexity of insert in the middle?

Answer O(n) because elements after the insertion point must shift.

Q12) How is vector related to RAII?

Answer Its destructor frees the heap buffer automatically when the vector goes out of scope.

Simple Programs

Create, push, print

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

int main() {
    vector<int> v = {10, 20, 30};
    v.push_back(40);
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

insert and erase

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

int main() {
    vector<int> v = {1, 3, 4};
    v.insert(v.begin() + 1, 2);
    v.erase(v.begin() + 3);
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

size vs capacity demo

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

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

sort a vector

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

int main() {
    vector<int> v = {5, 1, 4, 2};
    sort(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << "\n";
    return 0;
}

2D vector sum of a row

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

int main() {
    vector<vector<int>> m = {{1, 2}, {3, 4, 5}};
    int s = 0;
    for (int x : m[1]) s += x;
    cout << s << "\n"; // 12
    return 0;
}

at() bounds check

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

int main() {
    vector<int> v = {1, 2, 3};
    try {
        cout << v.at(10) << "\n";
    } catch (const out_of_range& e) {
        cout << "Exception: " << e.what() << "\n";
    }
    return 0;
}

Problem Solving Tricks

vector = dynamic contiguous array — default container.
Array fixed size; vector grows with push_back.
size() = elements; capacity() = allocated room.
reserve(n) before many push_backs.
at() checks bounds; [] does not.
Mid insert/erase is O(n).
Reallocation invalidates iterators.
Pass as const vector& to avoid copies.
Use sort(v.begin(), v.end()) from .
v.data() gives a pointer to the contiguous buffer.
Prefer vector over raw new[]/delete[].
2D: vector> for jagged matrices.

Practice Programs List

Create a vector from user input until -1; print size and elements.
Insert a value at index 2; erase the last element.
Print size and capacity after each of 20 push_backs.
reserve(100), then push 100 ints; note capacity behaviour.
Sort ascending and descending with a lambda.
Build a 3×3 vector matrix and print the diagonal.
Write a function that takes const vector& and returns the max.
Demonstrate at() throwing for a bad index.
Fill a table in comments: Array vs Vector (5 rows).
Compare &v[0] address stability before/after many push_backs without reserve.
Remove all even numbers using erase in a loop (carefully) or remove+erase idiom.
List three real apps where vector is the natural fit.