Implementation companion

C++ DSA toolkit

Choose the right standard-library container, remember its guarantees, and avoid the C++ errors that make a correct algorithm fail in practice.

Need to install C++17 first?

Container decision table

Container	Model	Access / lookup	Insert / remove	Search	Choose it when…
array<T,N>	Fixed contiguous sequence	O(1)	—	O(n)	Size known at compile time
vector<T>	Dynamic contiguous sequence	O(1)	O(1) amortized	O(n)	Default sequence; excellent locality
deque<T>	Chunked double-ended sequence	O(1)	O(1) both ends	O(n)	Stable fast front and back growth
list<T>	Doubly linked list	O(n)	O(1) at known iterator	O(n)	Use only when iterator splicing matters
forward_list<T>	Singly linked list	O(n)	O(1) after iterator	O(n)	Lower link overhead; forward-only
stack<T>	LIFO adaptor	top O(1)	push/pop O(1)	O(n)	DFS, parsing, undo
queue<T>	FIFO adaptor	front O(1)	push/pop O(1)	O(n)	BFS and scheduling
priority_queue<T>	Binary heap adaptor	top O(1)	push/pop O(log n)	O(n)	Repeated min/max selection
set/map	Ordered balanced tree	O(log n)	O(log n)	O(log n)	Sorted traversal and worst-case bounds
unordered_set/map	Hash table	O(1) expected	O(1) expected	O(1) expected	Fast lookup without ordering

Hash-container bounds are expected/amortized; adversarial collisions can make an operation O(n). Tree containers keep keys ordered and guarantee O(log n).

Prefer vector first

It is compact, cache-friendly, supports random access, and solves most sequence problems cleanly.

Store indices when possible

Indices make ownership simpler and serialize naturally; raw owning pointers demand explicit cleanup.

Know invalidation

vector growth invalidates every iterator and pointer; erase invalidates positions at and after the erased item.

Everyday STL skeleton

Containers in one program

Use adaptors for restricted interfaces and direct containers when you need iteration.

#include <bits/stdc++.h>
using namespace std;

int main() {
    vector<int> a{4, 1, 7};
    a.push_back(3);
    sort(a.begin(), a.end());

    unordered_map<string, int> frequency;
    for (string word : {"tree", "heap", "tree"}) ++frequency[word];

    queue<int> bfsFrontier;
    stack<int> dfsFrontier;
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(8);
    minHeap.push(2);
    cout << minHeap.top(); // 2
}

19 linesUTF-8 · C++ study reference

Custom min-heap comparator

priority_queue comparator

C++ comparators express lower priority, which is why min-heaps often use >.

struct Edge {
    int to;
    int weight;
};

// Return true when a should appear after b in the heap.
struct BySmallerWeight {
    bool operator()(const Edge& a, const Edge& b) const {
        return a.weight > b.weight;
    }
};

priority_queue<Edge, vector<Edge>, BySmallerWeight> pq;
pq.push({3, 12});
pq.push({5, 4});
// pq.top() is {5, 4}

16 linesUTF-8 · C++ study reference

Compile and debug

Useful compiler flags

Warnings catch suspicious conversions; sanitizers expose memory and undefined-behaviour bugs.

g++ -std=c++17 -Wall -Wextra -Wshadow -Wconversion -pedantic     -O2 main.cpp -o main
./main

# During debugging, replace -O2 with:
g++ -std=c++17 -Wall -Wextra -g     -fsanitize=address,undefined main.cpp -o main

5 linesUTF-8 · C++ study reference

Implementation checklist

Write the invariant and edge cases before the loop.
Use const references for read-only non-trivial arguments.
Use long long when sums or path costs may exceed int.
Test empty, one-element, duplicate, sorted, and reverse-sorted inputs.
State both algorithmic complexity and any STL guarantee you rely on.

Frequent C++ traps

Unsigned size_t underflow when looping backward.
Keeping a vector iterator after push_back reallocates.
Calling top, front, back, or pop on an empty container.
Using <= high with an overflowing midpoint formula.
Forgetting to discard stale entries in heap-based Dijkstra.