Chapter 3: The C++ STL Arsenal

In contests, the STL is split into two camps: containers and algorithms. We only need the parts that get work done.

3.1 Vector: A Dynamic Array

vector is an upgrade to raw arrays. You do not have to know the size ahead of time; it grows automatically.

• Header: #include <vector>
• Declaration: vector<int> v; // an empty list of ints
• Common ops:
  • v.push_back(x): append x at the end (amortized O(1)).
  • v.size(): number of elements.
  • v[i]: random access by index (O(1)).
  • v.clear(): remove all elements.

Practical tips:

1. Initialize: vector<int> v(n, 0); builds a vector of length n filled with zeros.
2. Iterate: modern C++ prefers for (auto x : v).
3. Sort: sort(v.begin(), v.end());.

vector<int> v;
v.push_back(10);
v.push_back(5);
v.push_back(20);
 
sort(v.begin(), v.end()); // v becomes {5, 10, 20}
 
for (int x : v) cout << x << " "; // prints 5 10 20

3.2 String: The Better Char Array

Quit using fixed-size char s[100]. std::string grows dynamically and has convenient concatenation.

• Header: #include <string>
• Common ops:
  • s += 'a': append a character or string.
  • s.length() or s.size(): return length.
  • s.substr(pos, len): extract a substring starting at pos with length len.
  • s.find("abc"): locate the first occurrence of the substring (returns string::npos if missing).

Tip: strings support lexicographical comparisons, which is handy when sorting.

string s = "hello";
s += " world"; // s becomes "hello world"
cout << s.substr(0, 5); // prints "hello"

3.3 Set & Map: Sorted Containers with Logarithmic Ops

set and map typically rely on red-black trees, so insert/delete/find all run in O(log N).

3.3.1 Set

• Automatically removes duplicates and keeps elements sorted.
• Example: inserting 3, 1, 3, 2 results in {1, 2, 3}.
• Header: #include <set>
• Ops: s.insert(x), s.erase(x), s.count(x).

3.3.2 Map

This is like a super array whose key can be a string, a negative number, or even another container.

• Header: #include <map>
• Declaration: map<string, int> mp;
• Use case: counting word frequencies.

map<string, int> mp;
mp["apple"] = 5;
cmp["banana"] = 2;
mp["apple"]++; // updates "apple" to 6
 
cout << mp["apple"]; // prints 6

Caution: Accessing map is also O(log N), so avoid abusing it when you face ~10^7 operations.

3.4 Stack, Queue & Priority Queue: The Three Musketeers

3.4.1 Stack

• LIFO (last-in, first-out).
• Use cases: bracket matching, monotonic stacks, DFS.
• Methods: st.push(x), st.top(), st.pop().

3.4.2 Queue

• FIFO (first-in, first-out).
• Use case: BFS.
• Methods: q.push(x), q.front(), q.pop().

3.4.3 Priority Queue (Heap)

• top() always returns the largest (default) or smallest element. Implemented as a heap.
• Use cases: greedy algorithms, Dijkstra.

priority_queue<int> pq; // max-heap
pq.push(10);
pq.push(5);
pq.push(20);
 
cout << pq.top(); // 20
pq.pop();
cout << pq.top(); // 10

For a min-heap: priority_queue<int, vector<int>, greater<int>> pq;

3.5 Algorithms: One Line Beats Ten

<algorithm> has a ton of black magic.

1. sort:

   • sort(v.begin(), v.end()); // ascending
   • sort(v.begin(), v.end(), greater<int>()); // descending
   • Custom comparator: write a cmp function.

2. unique (deduplicate): usually combined with sort:

   sort(v.begin(), v.end());
   v.erase(unique(v.begin(), v.end()), v.end());

3. lower_bound / upper_bound (binary search):

   • Operate on sorted ranges.
   • lower_bound(begin, end, val): iterator to the first element >= val.
   • upper_bound(begin, end, val): iterator to the first element > val.
   • Index: int idx = lower_bound(v.begin(), v.end(), 5) - v.begin();

4. next_permutation:

   • Advances the sequence to the next lexicographical permutation.

   vector<int> p = {1, 2, 3};
   do {
       // use current permutation
   } while (next_permutation(p.begin(), p.end()));

3.6 Pair: Bundle Two Values

Sometimes you need to keep two values together, like a coordinate (x, y).

• Declaration: pair<int, int> p;
• Assignment: p = {3, 4}; or p = make_pair(3, 4);
• Access: p.first, p.second.
• Sorting: sort orders pairs by first first, then by second. Handy for interval problems.

🧠 Chapter Recap & Exercise

The STL is the bedrock of competitive programming. You do not have to memorize every function; using them often will engrain them naturally.

Homework: Search for NOIP 2006 entry problem P1059 Mingming's Random Numbers on Luogu.

• Task: Given N integers, deduplicate and sort them.
• Hint: You can solve it with set for concise code, or use vector + sort + unique to practice.

Next, we’ll dive into how to analyze the speed of your algorithms.