C++ Toolkit for DSA
The C++ features every later module uses — references, const, containers, standard algorithms, comparators — and the testing habits that catch bugs early.
What you will learn
The C++ features every later module uses — references, const, containers, standard algorithms, comparators — and the testing habits that catch bugs early. The ideas carry over to other languages; a cross-language note closes the module.
Prerequisites: basic C++ or another C-family language.
4.1 Functions, references, pointers, and const correctness
Explain pass-by-value, pass-by-reference, const T&, pointer validity, lifetime, and avoiding dangling references.
Pass large inputs as const vector<int>&: no copy, and the function promises not to modify it.
Pass by non-const reference only when the function's job is to modify the argument.
Never return a reference or pointer to a local variable — it dies when the function returns.
4.2 Arrays, strings, and vectors
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Teach size(), indexing, iterators, bounds, push_back, pop_back, resize, reserve, and invalidated iterators/references. Without the reserve, a push_back that triggers reallocation would invalidate first — using it afterwards is undefined behaviour.
#include <bits/stdc++.h>
using namespace std;
int main() {
vector<int> values = {4, 2, 7};
values.push_back(9);
sort(values.begin(), values.end());
string word = "algorithm";
cout << "values:";
for (int v : values) cout << ' ' << v;
cout << "\nsize=" << values.size() << " front=" << values.front() << " back=" << values.back() << '\n';
cout << "word.substr(0, 4)=" << word.substr(0, 4) << " find(\"rit\")=" << word.find("rit") << '\n';
values.pop_back();
values.resize(5, 0); // grows with zeros
cout << "after pop_back + resize(5, 0):";
for (int v : values) cout << ' ' << v;
cout << '\n';
try { cout << values.at(10); } catch (const out_of_range&) { cout << "at(10) throws out_of_range; operator[] would not check\n"; }
vector<int> v = {1, 2, 3};
v.reserve(100); // capacity fixed in advance: no reallocation below 100 elements
int* first = &v[0];
for (int i = 0; i < 50; ++i) v.push_back(i);
cout << "pointer still valid after reserve: " << boolalpha << (first == &v[0]) << '\n';
}values: 2 4 7 9
size=4 front=2 back=9
word.substr(0, 4)=algo find("rit")=4
after pop_back + resize(5, 0): 2 4 7 0 0
at(10) throws out_of_range; operator[] would not check
pointer still valid after reserve: true4.3 STL containers
vector, array, deque, list, forward_list.
stack, queue, priority_queue.
set, multiset, map, multimap.
unordered_set, unordered_map.
bitset, span where the C++ standard supports it.
Indexed sequence, append at end index O(1), append amortized O(1) Add/remove at both ends O(1) at both ends Sorted unique keys, ordered iteration
O(log n) per operation (balanced tree) Fast membership / lookup by key unordered_set / unordered_map expected O(1), worst O(n) Repeated min/max extraction top O(1), push/pop O(log n) Fixed-size bit flags
span is C++20; this course compiles as C++17, so it is not used in the programs.
4.4 STL algorithms and iterators
sort, stable_sort, lower_bound, upper_bound, binary_search, reverse, rotate, find, count, accumulate, min_element, max_element, next_permutation, unique, partition, and custom comparators. Explain iterator categories and why unique is commonly followed by erase.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
unique only moves the kept elements to the front and returns the new logical end; the container's size is unchanged until erase removes the tail. lower_bound/upper_bound need a sorted range and random-access iterators to be O(log n).
#include <bits/stdc++.h>
using namespace std;
void show(const string& label, const vector<int>& v) {
cout << label << ':';
for (int x : v) cout << ' ' << x;
cout << '\n';
}
int main() {
vector<int> a = {5, 1, 4, 1, 5, 9, 2, 6, 5};
sort(a.begin(), a.end());
show("sorted", a);
cout << "lower_bound(5) index=" << lower_bound(a.begin(), a.end(), 5) - a.begin()
<< " upper_bound(5) index=" << upper_bound(a.begin(), a.end(), 5) - a.begin()
<< " -> count of 5 = " << upper_bound(a.begin(), a.end(), 5) - lower_bound(a.begin(), a.end(), 5) << '\n';
auto newEnd = unique(a.begin(), a.end());
show("after unique (size unchanged)", a);
a.erase(newEnd, a.end());
show("after erase", a);
cout << "sum=" << accumulate(a.begin(), a.end(), 0LL) << " max=" << *max_element(a.begin(), a.end()) << '\n';
rotate(a.begin(), a.begin() + 2, a.end());
show("rotate left by 2", a);
vector<int> p = {1, 2, 3};
cout << "permutations of 1 2 3:";
do { cout << " " << p[0] << p[1] << p[2]; } while (next_permutation(p.begin(), p.end()));
cout << '\n';
vector<int> q = {7, 2, 9, 4, 3, 8};
auto mid = partition(q.begin(), q.end(),
…sorted: 1 1 2 4 5 5 5 6 9
lower_bound(5) index=4 upper_bound(5) index=7 -> count of 5 = 3
after unique (size unchanged): 1 2 4 5 6 9 5 6 9
after erase: 1 2 4 5 6 9
sum=27 max=9
rotate left by 2: 4 5 6 9 1 2
permutations of 1 2 3: 123 132 213 231 312 321
evens first, boundary at index 34.5 Lambda functions and comparators
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Comparator requirements: strict weak ordering; avoid comparators that return true for equal elements or change unpredictably. A comparator written with >= returns true for equal elements, which breaks irreflexivity; std::sort may then read out of bounds — a real crash, not just a wrong order.
#include <bits/stdc++.h>
using namespace std;
struct Item { int id; int score; };
int main() {
vector<Item> items = {{4, 80}, {2, 95}, {7, 80}, {1, 95}, {3, 60}};
sort(items.begin(), items.end(),
[](const Item& a, const Item& b) {
if (a.score != b.score) return a.score > b.score;
return a.id < b.id;
});
for (const Item& it : items) cout << "id=" << it.id << " score=" << it.score << '\n';
}id=1 score=95
id=2 score=95
id=4 score=80
id=7 score=80
id=3 score=604.6 Input/output and large data
Fast I/O, parsing, multiple test cases, overflow-safe integer types, and avoiding accidental copies.
Call ios::sync_with_stdio(false); cin.tie(nullptr); once at the start of main when reading large inputs.
Use '\n' rather than endl — endl flushes every line.
Read the constraints first: sums of 10⁵ values up to 10⁹ need long long.
for (auto x : bigVector) copies each element; prefer const auto& for strings and structs.
4.7 Debugging and testing
Compiler warnings, sanitizers, assertions, unit tests, randomized testing, stress testing against a brute-force oracle, and minimal failing test cases.
Every program in this course is compiled with -Wall -Wextra -Wshadow -Werror -fsanitize=address,undefined. The stress test pattern below is used throughout: compare a fast solution with an obviously-correct slow one on many random inputs.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
When a stress test fails, shrink the input (fewer elements, smaller values) until the smallest failing case remains — it usually makes the bug obvious.
Cross-language track: repeat core implementations in C, Java, Python, and JavaScript/TypeScript. Explain each language's built-in containers, integer behavior, recursion limits, and performance caveats.
priority_queue (max-heap) fixed width; signed overflow is UB native stack (often ~8 MB) PriorityQueue (min-heap) fixed width, wraps silently thread stack, StackOverflowError none built in (bisect on a list) heapq (min-heap) default limit 1000 frames
number is a double: exact integers only to 2⁵³−1; use BigInt beyond engine stack, RangeError manual realloc
#include <bits/stdc++.h>
using namespace std;
long long fastMaxSubarray(const vector<int>& a) { // Kadane, O(n)
long long best = a[0], cur = 0;
for (int x : a) { cur = max<long long>(x, cur + x); best = max(best, cur); }
return best;
}
long long bruteMaxSubarray(const vector<int>& a) { // all subarrays, O(n^2)
long long best = LLONG_MIN;
for (size_t i = 0; i < a.size(); ++i) {
long long s = 0;
for (size_t j = i; j < a.size(); ++j) { s += a[j]; best = max(best, s); }
}
return best;
}
int main() {
mt19937 rng(12345); // fixed seed: failures are reproducible
for (int t = 1; t <= 10000; ++t) {
int n = rng() % 8 + 1;
vector<int> a(n);
for (int& x : a) x = int(rng() % 21) - 10;
if (fastMaxSubarray(a) != bruteMaxSubarray(a)) {
cout << "mismatch on test " << t << '\n';
return 1;
}
}
cout << "10000 random tests: fast and brute-force answers agree\n";
}10000 random tests: fast and brute-force answers agreeQuiz
? After `auto e = unique(a.begin(), a.end());` on a sorted vector, what is `a.size()`?
+ Unchanged — `unique` returns a new logical end; `erase(e, a.end())` shrinks the vector. :: The run showed the size unchanged until erase.
- The number of distinct elements :: Only after erase.
- 0 :: No.
- It depends on the compiler :: The behaviour is specified.
? Why is a comparator using `>=` dangerous with `std::sort`?
+ It is not a strict weak ordering (it returns true for equal elements), so sort's behaviour is undefined and can crash. :: Comparators must be irreflexive.
- It sorts in descending order. :: That is what `>` does, safely.
- It is slower. :: Correctness, not speed.
- It is a compile error. :: It compiles.
? What does a stress test compare?
+ A fast solution against a simple brute-force one on many random inputs :: Mismatches reveal bugs; the fixed seed makes them reproducible.
- Two runs of the same program :: That only finds nondeterminism.
- Compile times :: No.
- Memory use only :: No.