STL Containers and Algorithms

7 pages · ~5 min✓ Reviewed

Builds on Exceptions and Error Handling. Next up: Strings and string_view.

C++Page 1

Sequence Containers: vector, deque, list

1. vector

Contiguous dynamic array: O(1) access, amortized O(1) push_back
Insert/erase in the middle is O(n) (elements shift)
Capacity grows geometrically, about 1.5x to 2x
reserve(n): preallocates capacity, size() unchanged
resize(n): changes size, new elements value-initialized

2. deque and list

	Access	Ends	Middle	Memory
vector	O(1)	back O(1)	O(n)	contiguous
deque	O(1)	both O(1)	O(n)	chunked blocks
list	none	both O(1)	O(1) at iterator	linked nodes

deque: push_front and push_back O(1), but not contiguous
list: doubly linked, no random access, no operator[]
splice moves nodes between lists in O(1)

3. Example and Mistakes

cpp

vector<int> v{3,1,2};
v.push_back(4); v.emplace_back(5);
cout << v.back() << '\n';
v.pop_back();
v.erase(v.begin() + 1);
cout << v.size() << '\n';

v: {3,1,2,4,5} then {3,2,4}

output

5
3

Mistakes

v[i] is unchecked; v.at(i) throws out_of_range. vector<bool> is a packed bitset, not a real container of bool.

C++Page 2

Associative Containers: map, unordered_map, set

1. Tree vs Hash

	map / set	unordered_*
Built on	red-black tree	hash table
Ops	O(log n)	O(1) avg, O(n) worst
Order	sorted keys	none
Keys	unique; multimap/multiset allow dupes	unique
Custom key	comparator	hash + `==`

2. Calls and Example

Call	Effect
`m[k]`	inserts default value
`find(k) != end()`, `count(k)`	test, no insert
`at(k)`	throws if missing
`insert(pair)`	no-op if key exists
`emplace`

C++Page 3

priority_queue and Container Adaptors

1. priority_queue Basics

Binary heap adaptor over vector
top() O(1); push / pop O(log n)
Max-heap by default: largest on top
Template args: type, container, comparator

cpp

priority_queue<int, vector<int>, greater<int>> pq;
pq.push(5); pq.push(1); pq.push(3);
cout << pq.top();

min-heap: greater<int> as 3rd argument

output

2. Custom Order with a Lambda

cpp

auto cmp = [](const P& a, const P& b){
    return a.d > b.d;
};
priority_queue<P, vector<P>, decltype(cmp)> pq(cmp);

pass cmp to the constructor too

Inverted logic

less means lower priority, so a.d > b.d puts the smallest d on top.

3. stack, queue and Mistakes

stack and queue are adaptors over deque
Only push, pop, top (or front/back) exposed
No iterators, no traversal
top() / pop() on empty is undefined behavior: check empty()
pop() returns void: read top() first

C++Page 4

Iterators and Invalidation

1. Iterator Basics

An iterator is a pointer-like handle
begin() is the first element; end() is one past the last, never dereference it
Categories: input, forward, bidirectional, random-access

2. What Invalidates

Container	Insert	Erase
`vector`	`push_back` may reallocate: all iterators, refs, pointers	Change point onward
`deque`	Middle: all. Ends: iterators, not refs	Middle: all
`list` `map` `set`	Never	Erased one only
`unordered_*`	Rehash: iterators	Erased one only

3. Safe Erase

cpp

for (auto it = v.begin(); it != v.end();) {
  if (pred(*it)) it = v.erase(it);
  else ++it;
}

erase returns the next valid iterator

Mistakes

Erasing inside a range-for, or erase(it++) on a vector. Use erase-remove: v.erase(remove(v.begin(), v.end(), x), v.end());

C++Page 5

<algorithm> Essentials and Lambdas

1. Sort and Search

Call	Result	Cost
`sort`	not stable, random-access only	O(n log n)
`stable_sort`	keeps equal order	O(n log n)
`binary_search`	`bool`	O(log n)
`lower_bound`	first element `>= x`	O(log n)
`upper_bound`	first element `> x`	O(log n)

list has no random access: use list::sort
Binary search on an unsorted range is undefined

2. Common Calls

find, find_if, count_if, reverse, iota
max_element, min_element, next_permutation
unique: sorted input, then erase the tail
accumulate is in <numeric>: typed init 0LL

C++Page 6

Complexity Cheat Sheet

1. Containers

Container	Access	Insert/erase	Find
`vector`	O(1)	end O(1) amortized, middle O(n)	O(n)
`deque`	O(1)	both ends O(1), middle O(n)	O(n)
`list`	O(n)	at iterator O(1)	O(n)
`map`/`set`	none	O(log n), ordered	O(log n)
`unordered_map`/`set`	none	O(1) avg, O(n) worst	O(1) avg

2. Heap, Sort, Search

Call	Cost
`priority_queue` top	O(1)
`push` / `pop`	O(log n)
Heap from n items (range ctor)

C++Page 7

Check yourself

Spot the bug: for (auto it = v.begin(); it != v.end(); ++it) if (*it == 2) v.erase(it);

erase invalidates it, so the following ++it is undefined behavior
Fix: it = v.erase(it) in the if branch, ++it only in the else
Or use the erase-remove idiom

What does this print?

1
operator[] inserts a default value 0 for a missing key
Use find or count to look up without inserting

map<string,int> m;
if (m["a"] == 0) {}
cout << m.size();

What is wrong with accumulate(v.begin(), v.end(), 0) on a vector<long long> holding two 3000000000s?

The init 0 is an int, so the running sum is an int and overflows
Pass 0LL so the sum is long long