C++ STL Complete Interview Notes

C++ STL (Standard Template Library) — Complete Interview Notes

0. Why STL?
1. Vector — Dynamic Array
2. List — Doubly Linked List
3. Deque — Double Ended Queue
4. Pair — (from <utility> , part of STL utility library)
5. Stack — LIFO (Last In First Out)
6. Queue — FIFO (First In First Out)
7. Priority Queue
8. Map — Key-Value Pairs
9. Set — Unique, Sorted Values
10. Algorithms
11. Iterators & Functors — Quick Recap
12. Time Complexity Cheat Sheet ⭐ (High-yield interview table)
13. Quick-Fire Interview Definitions
14. Interview Focus Areas Flagged for Your Prep
C++ STL (Standard Template Library) — Complete Interview Notes

From Zero to Advanced | Containers + Algorithms + Iterators + Code + Interview Angle

0. Why STL?

STL gives ready-made, well-tested containers and algorithms so you don’t have to implement data structures (sorting, queues,
stacks, etc.) from scratch during coding tests/interviews — saving huge amounts of time.

Example: Instead of writing merge sort/quick sort from scratch, just call sort() . Instead of implementing a queue for BFS, use
STL’s queue .

STL has 4 main parts: 1. Containers (most important for DSA — main focus of these notes) 2. Algorithms (2nd most
important) 3. Iterators 4. Functors (function objects, used with containers/algorithms)

1. Vector — Dynamic Array

Why not just use arrays?

C++ arrays have a fixed/constant size — cannot grow or shrink at runtime.

Vector = a dynamic, resizable array — can grow/shrink during runtime.

#include <vector>
vector<int> v; // empty vector, size = 0
cout << [Link](); // 0

How a vector grows internally (important interview concept)

Vector has two properties: size (number of elements currently stored) and capacity (how many elements it can currently
hold before needing to resize).
When a vector is full and a new element is pushed, a new vector of double the capacity is created internally, the old
data is copied over, and then the new element is inserted.
This doubling strategy is why push_back has amortized O(1) time complexity.

vector<int> v;
v.push_back(1); // size=1, capacity=1
v.push_back(2); // size=2, capacity=2
v.push_back(3); // size=3, capacity=4 (doubled from 2)
cout << [Link](); // 3
cout << [Link](); // 4

Core Vector Functions

 Function Purpose

push_back(x) Insert x at the end

Similar to push_back but constructs the object in-place (avoids

emplace_back(x)
an extra copy) — matters more with complex objects like pair

pop_back() Removes the last element

Access element at index i (square-bracket notation preferred in

v[i] or [Link](i)
practice)

front() Returns first element

back() Returns last element

size() Number of elements

capacity() Current allocated capacity

clear() Removes all elements (size → 0, capacity unchanged)

empty() Returns true / false whether vector is empty

erase() Removes element(s) — costly, O(n) worst case

insert() Inserts element(s) at a given position — costly, O(n) worst case

vector<int> v = {1, 2, 3, 4, 5}; // initializer-list style

vector<int> v2(3, 10); // size 3, every element = 10 → {10,10,10}
vector<int> v3(v); // v3 initialized as a copy of v

for (int val : v) cout << val << " "; // range-based for loop

// front/back
cout << [Link](); // 1
cout << [Link](); // 5

Interview trap: push_back vs emplace_back — push_back expects the object already constructed in the required type;
emplace_back constructs the object in place, avoiding an unnecessary copy — most noticeable with types like pair .

erase() and insert() — using iterators

vector<int> v = {1, 2, 3, 4, 5};

[Link]([Link]()); // removes index 0 → {2,3,4,5}

[Link]([Link]() + 2); // removes index 2

// erase a RANGE — [start, end) — end is NOT included

[Link]([Link]() + 1, [Link]() + 3); // removes indices 1 and 2

[Link]([Link]() + 2, 100); // inserts 100 at index 2, shifts rest right

[Link](); // removes everything, size=0, capacity unchanged
cout << [Link](); // 1 (true) if empty

Interview fact: erase / insert are O(n) (costly) because elements need to shift; push_back / pop_back are O(1) (cheap).

Vector Iterators

[Link]() → points to index 0.

[Link]() → does NOT point to the last element (common misconception!). It points to the memory location just after
the last element (garbage/undefined value if dereferenced).
[Link]() → reverse begin, points to the last element.
[Link]() → reverse end, points to the position just before the first element.
 vector<int> v = {1, 2, 3, 4, 5};

vector<int>::iterator it = [Link]();
for (it = [Link](); it != [Link](); it++) {
cout << *it << " "; // dereference iterator with *
}

// Reverse traversal
for (auto it = [Link](); it != [Link](); it++) {
cout << *it << " ";
}

// Modern C++ shortcut using `auto` (avoids writing the long iterator type)
for (auto it = [Link](); it != [Link](); it++) cout << *it << " ";

Interview one-liner: “ [Link]() points one-past-the-last-element, not to the last element itself — dereferencing it gives
undefined/garbage data.”

2. List — Doubly Linked List

list is a sequential container like vector, but internally implemented as a doubly linked list.
Supports insertion/removal from both ends: push_back , push_front , pop_back , pop_front , emplace_back ,
emplace_front .

#include <list>
list<int> l;
l.push_back(1); // {1}
l.push_back(2); // {1, 2}
l.push_front(3); // {3, 1, 2}
l.push_front(5); // {5, 3, 1, 2}

for (int val : l) cout << val << " "; // 5 3 1 2

l.pop_back(); // removes 2 → {5, 3, 1}

l.pop_front(); // removes 5 → {3, 1}

Most functions ( size , erase , clear , begin , rbegin , rend , insert , front , back ) work the same as in vector .

Vector vs List — key interview comparison: | | Vector | List | |—|—|—| | Internal implementation | Dynamic array | Doubly
linked list | | Random access ( v[i] ) | ✅ O(1) | ❌ Not supported | | Insert/delete at front | ❌ Costly (O(n)) | ✅ O(1) | | Insert/delete
at back | ✅ Amortized O(1) | ✅ O(1) |

3. Deque — Double Ended Queue

Very similar to list conceptually — operations available at both ends: push_back , push_front , pop_back ,
pop_front , emplace_back , emplace_front .

#include <deque>
deque<int> d;
d.push_back(1);
d.push_front(2);

Careful — don’t confuse two different meanings of “deque”: - deque (the container) = Double Ended Queue. -
“dequeue” (the generic verb) = removing/popping an element from any queue.

List vs Deque — key interview comparison: | | List | Deque | |—|—|—| | Internal implementation | Doubly linked list |
Dynamic array-based | | Random access ( d[i] ) | ❌ Not supported (error) | ✅ Supported (O(1)) |

deque<int> d = {1, 2, 3};

cout << d[1]; // valid — 2

list<int> l = {1, 2, 3};

// cout << l[1]; // ERROR — list doesn't support random access

4. Pair — (from <utility> , part of STL utility library)

 Used to group two values together (can be of different types).

pair<int, int> p = {1, 5};

cout << [Link]; // 1
cout << [Link]; // 5

pair<string, int> p2 = {"Shraddha", 21};

Pair of Pairs (nested pairs)

pair<int, pair<int, int>> p = {1, {3, 5}};

cout << [Link]; // 1
cout << [Link]; // 3
cout << [Link]; // 5

Vector of Pairs

vector<pair<int,int>> vp = {{1, 2}, {3, 4}};

for (auto p : vp) {
cout << [Link] << " " << [Link] << endl;
}

// Inserting into a vector of pairs

vp.push_back({4, 5}); // must construct the pair explicitly for push_back
vp.emplace_back(4, 5); // emplace_back builds the pair in-place — no need to pre-construct

Interview one-liner: “ push_back requires an already-constructed object (like a pre-made pair); emplace_back constructs the
object in-place at insertion time, which is why we can just pass 4, 5 directly without wrapping them in {} .”

5. Stack — LIFO (Last In First Out)

Visualize as a stack of books/plates — insert and remove only from the top.

#include <stack>
stack<int> s;
[Link](1);
[Link](2);
[Link](3); // top = 3

cout << [Link](); // 3

[Link](); // removes top element (3)

cout << [Link](); // true/false
cout << [Link]();

// Classic pattern: pop until empty

while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}
// Output: 3 2 1 — REVERSE of insertion order (1,2,3 → pops as 3,2,1)

swap() — swaps contents of two stacks

stack<int> s1, s2;

// ... fill s1 with elements
[Link](s2); // now s1's elements move into s2 and vice versa

Interview one-liner: “Stack is LIFO — last element inserted is the first one removed. push , top , and pop are all O(1).”

6. Queue — FIFO (First In First Out)

Visualize as a real-world line/queue (e.g., at a bank, ticket counter) — insertion happens from the back/rear, removal happens
from the front.
 #include <queue>
queue<int> q;
[Link](1);
[Link](2);
[Link](3); // back = 3, front = 1

cout << [Link](); // 1

[Link](); // removes front element (1)

while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}
// Output: 1 2 3 — SAME order as insertion

size() , empty() , swap() work exactly the same as with stack .

Stack vs Queue — quick comparison: | | Stack | Queue | |—|—|—| | Order | LIFO | FIFO | | Insert operation | push() (top) |
push() (back) | | Remove operation | pop() (top) | pop() (front) | | Access | top() | front() (and back() ) |

7. Priority Queue

Internally implemented using a Max Heap (by default) or Min Heap.

Max Heap: the largest element is always at the top (root).
Min Heap: the smallest element is always at the top.
Visualize like a stack, but the element at the “top” always has the highest priority (by default = largest value).

#include <queue>
priority_queue<int> pq; // max-heap by default
[Link](5);
[Link](3);
[Link](10);
[Link](4);

cout << [Link](); // 10 (largest)

while (![Link]()) {
cout << [Link]() << " ";
[Link]();
}
// Output: 10 5 4 3 — always sorted DESCENDING order when popped

Min-Heap version (reverse order)

priority_queue<int, vector<int>, greater<int>> pq;

// `greater<int>` is a functor (function object) used as a custom comparator
[Link](5); [Link](3); [Link](10); [Link](4);
// pops in ascending order: 3 4 5 10

Time complexity (important): | Operation | Stack / Queue | Priority Queue | |—|—|—| | push/pop/top | O(1) | O(log n) —
because internally a tree (heap) is being maintained |

8. Map — Key-Value Pairs

Visualize as a table with two columns: Key and Value.

Key properties (critical, frequently asked): 1. Keys are always unique (no duplicate keys allowed) — think of it like a roll
number or employee ID. 2. Data is automatically stored in sorted order (by key), because map is internally implemented as a
self-balancing binary search tree.
 #include <map>
map<string, int> m;
m["TV"] = 100;
m["Laptop"] = 100;
m["Headphones"] = 50;

// If you assign to an existing key, it OVERWRITES the old value (doesn't create a duplicate)
m["TV"] = 150;

for (auto p : m) {
cout << [Link] << " " << [Link] << endl;
}
// Prints in ASCENDING (lexicographic) order of keys: Headphones, Laptop, TV

Map Functions

Function Purpose

[Link]({key, value}) or [Link](key, value) Insert a new key-value pair

Returns 1 if the key exists, 0 if it doesn’t (map has unique keys,

[Link](key)
so it’s always 0 or 1)

m[key] Access/read the value for a key

[Link](key) Removes the entry for that key

[Link](key) Returns an iterator to the key-value pair if found, else [Link]()

[Link]() , [Link]() Same as other containers

[Link]({"Camera", 25});
cout << [Link]("Laptop"); // 1 (exists)

[Link]("TV"); // removes the "TV" entry

auto it = [Link]("Camera");
if (it != [Link]()) cout << "Found";
else cout << "Not found";

Types of Maps

Type Key uniqueness Order Internal structure

Self-balancing BST → O(log n)

map Unique keys Sorted (ascending by key)
operations

multimap Duplicate keys allowed Sorted Self-balancing BST → O(log n)

Hash table → amortized O(1)

unordered_map Unique keys Random/unspecified order
operations

multimap<string, int> mm;

[Link]({"TV", 100});
[Link]({"TV", 200}); // both entries kept! (duplicates allowed)
// mm["key"] square-bracket notation NOT allowed in multimap — must use insert/emplace

unordered_map<string, int> um;

um["Laptop"] = 100;
um["Fridge"] = 200;
// Order when printed is NOT guaranteed / sorted

Interview one-liner: “ map and set are typically implemented as self-balancing BSTs (like Red-Black trees) giving O(log n)
operations; unordered_map / unordered_set use hash tables giving amortized O(1) operations but no ordering guarantee.”

Practical note: unordered_map / unordered_set are used far more frequently in practice/interviews than map / set due to
their faster average time complexity — use map / set specifically when you need sorted order.

9. Set — Unique, Sorted Values

Similar to a mathematical set — stores only unique values in sorted order.

 #include <set>
set<int> s;
[Link](1);
[Link](2);
[Link](3);
[Link](1); // duplicate — ignored, size stays same

for (int val : s) cout << val << " "; // 1 2 3 (sorted, unique)
cout << [Link](); // 3

Same core functions as map : count() , erase() , find() , size() , empty() .

lower_bound() and upper_bound() (set-specific, frequently tested)

Function Returns

Iterator to the first element ≥ x (i.e., minimum value that is at

lower_bound(x)
least x )

upper_bound(x) Iterator to the first element > x (strictly greater than x )

set<int> s = {1, 2, 3, 4, 5, 6};

auto lb = s.lower_bound(4); // points to 4 (since 4 exists and is ≥ 4)

cout << *lb; // 4

auto ub = s.upper_bound(4); // points to 5 (first value strictly > 4)

cout << *ub; // 5

// If lower_bound target doesn't exist in the set, e.g. looking for a value
// not present but within range → returns the next larger element.
// If no valid answer exists (target larger than all elements) → returns [Link]()
// dereferencing [Link]() gives garbage/0.

Types of Sets

Type Duplicates Order

set ❌ No Sorted (ascending)

multiset ✅ Yes Sorted

Unordered/random —
unordered_set ❌ No lower_bound / upper_bound don’t
apply (data isn’t sorted)

Interview trap: lower_bound / upper_bound only make logical sense on sorted data — hence they work on
set / multiset / map but not on unordered_set / unordered_map .

10. Algorithms

sort()

#include <algorithm>
int arr[5] = {3, 5, 1, 8, 2};
sort(arr, arr + 5); // ascending order by default

vector<int> v = {3, 5, 1, 8, 2};

sort([Link](), [Link]()); // ascending

The end pointer/iterator passed is always one past the last valid element ( arr + n , or [Link]() ), consistent with the
STL convention.

Sorting in descending order using a comparator

sort(arr, arr + 5, greater<int>()); // NOTE: the () after greater<int> is required!

Common mistake (explicitly called out): forgetting the () after greater<int> — greater<int> alone refers to the type,
greater<int>() creates an actual functor/comparator object to pass into sort .

Custom Comparators (very important, commonly tested)

A comparator is a boolean function that defines the sorting logic — returns true if the first argument should come before the
second.

bool comparator(pair<int,int> p1, pair<int,int> p2) {

// Sort by SECOND value ascending
if ([Link] < [Link]) return true;
if ([Link] > [Link]) return false;
// If second values are equal, sort by FIRST value ascending
if ([Link] < [Link]) return true;
return false;
}

vector<pair<int,int>> vp = {{3,1}, {2,1}, {7,1}, {5,2}};

sort([Link](), [Link](), comparator);
// Sorted by 'second' first; ties broken by 'first'

Interview one-liner: “A custom comparator is a boolean function passed as the third argument to sort() that defines your
own ordering logic — essential when default ascending/descending order isn’t what you need, e.g., sorting pairs by their second
value.”

reverse()

vector<int> v = {1, 2, 3, 4, 5};

reverse([Link](), [Link]()); // reverses the whole vector

reverse([Link]() + 1, [Link]() + 3); // reverses only a sub-range

next_permutation() / prev_permutation()

Generates the next/previous permutation in lexicographic order.

string s = "abc";
next_permutation([Link](), [Link]()); // s becomes "acb"

string s2 = "bca";
prev_permutation([Link](), [Link]()); // s2 becomes "bac"

(Worth knowing how to implement this manually from scratch too — commonly asked as a “no-STL-allowed” interview problem.)

min() / max() / swap()

cout << max(4, 5); // 5

cout << min(6, 10); // 6

int a = 5, b = 10;
swap(a, b); // a=10, b=5

*max_element() / *min_element()

vector<int> v = {3, 5, 1, 8, 2};

cout << *max_element([Link](), [Link]()); // 8
cout << *min_element([Link](), [Link]()); // 1

(Returns an iterator — must dereference with * to get the value.)

binary_search()

vector<int> v = {1, 2, 3, 4, 5}; // must be SORTED

cout << binary_search([Link](), [Link](), 4); // 1 (true) — found
cout << binary_search([Link](), [Link](), 10); // 0 (false) — not found

Returns a boolean (found / not found) — not the index. (In real interviews you’ll usually be asked to implement binary search
manually, but STL’s version is handy to know.)

Bit Manipulation Helpers (GCC built-ins)

 int n = 15; // binary: 1111
cout << __builtin_popcount(n); // 4 (counts number of set/1 bits)

long ln = 15;
cout << __builtin_popcountl(ln); // for `long` — note the trailing 'l'

long long lln = 15;

cout << __builtin_popcountll(lln); // for `long long` — trailing 'll'

Interview note: These __builtin_* functions are GCC-compiler-specific (not portable across all C++ compilers), so widely
used in competitive programming but less common in production/industry code.

11. Iterators & Functors — Quick Recap

Concept Meaning

Acts like a pointer to a container’s memory location; used to

Iterator traverse containers, and passed into functions like erase ,
insert , sort , reverse

begin() Points to the first element

end() Points to one-past-the-last element (NOT the last element)

rbegin() Points to the last element (for reverse traversal)

rend() Points to one-before-the-first element

An object that behaves like a function — e.g., greater<int>()

Functor (Function Object)
used as a custom comparator in sort() or priority_queue

Lets the compiler automatically deduce the iterator’s type,

auto keyword
avoiding long/verbose type declarations

12. Time Complexity Cheat Sheet ⭐ (High-yield interview table)

Insert/Delete
Container Insert/Delete (end) Random Access Internal Structure
(middle/front)

vector Amortized O(1) O(n) O(1) Dynamic array

list O(1) O(1) ❌ Not supported Doubly linked list

deque O(1) O(1) at front/back only O(1) Dynamic array-based

Underlying container
stack O(1) (top) — ❌
(deque by default)

Underlying container
queue O(1) (front/back) — ❌
(deque by default)

Max/Min Heap (binary

priority_queue O(log n) — ❌
tree)

map / set O(log n) O(log n) — Self-balancing BST

multimap / multiset O(log n) O(log n) — Self-balancing BST

unordered_map /
Amortized O(1) Amortized O(1) — Hash table
unordered_set

13. Quick-Fire Interview Definitions

 Term One-line definition

Standard Template Library — provides ready-made containers

STL and algorithms in C++

Vector Dynamic, resizable array; doubles capacity when full

Sequential container implemented as a doubly linked list;

List
supports front & back operations

Double-ended queue; array-based, supports random access

Deque
unlike list

Pair Groups two values (possibly of different types) together

Stack LIFO structure — insert/remove only from the top

Queue FIFO structure — insert at back, remove from front

Heap-based structure where the highest-priority (by default

Priority Queue
largest) element is always accessible at the top

Map Stores unique key-value pairs in sorted order (by key); BST-based

Unordered Map Same as map but unsorted; hash-table based; faster on average

Set Stores unique values in sorted order

Iterator A pointer-like object used to traverse/access container elements

A function object (like greater<int>() ) passed to customize

Functor
behavior of algorithms

Comparator A boolean function defining custom sort/ordering logic

emplace_back constructs objects in-place; push_back requires

emplace_back vs push_back
an already-constructed object

14. Interview Focus Areas Flagged for Your Prep

Given your priority list (Word Pattern, Missing/Repeated Number, Subarray Sum = K, Valid Parentheses, Kth Largest Element,
Number of Islands/BFS), map these directly to STL containers:

1. Kth Largest Element → use priority_queue (min-heap of size K, or max-heap + pop K-1 times).
2. Number of Islands / BFS → use queue for the BFS traversal.
3. Valid Parentheses → classic stack application (push open brackets, pop/match on close brackets).
4. Subarray Sum Equals K → use unordered_map for prefix-sum frequency counting (O(1) average lookups).
5. Word Pattern → use unordered_map for bidirectional character-to-word mapping.
6. Find Missing AND Repeated Number → can be solved via unordered_map / set counting approach (though optimal
O(1)-space solutions use math/XOR — good to know both).

General interview tips: - Always clarify out loud whether you need sorted order (→ map / set ) or just fast lookup (→
unordered_map / unordered_set ). - Remember [Link]() / [Link]() point one past the last element — a very common off-by-
one/logic trap. - Practice writing a custom comparator from memory — it’s one of the most commonly tested “write it live” STL
skills.

End of notes. Recommended next step: solve 2–3 problems per container (especially priority_queue , unordered_map , and
stack ) to build muscle memory for STL syntax under time pressure.