Chapter 3.1: STL Essentials

📝 Prerequisites: Chapters 2.1–2.3 (variables, loops, functions, vectors)

The Standard Template Library (STL) is C++'s built-in collection of ready-made data structures and algorithms. Instead of writing your own linked lists, hash tables, or sorting algorithms from scratch, you use the STL — it's fast, reliable, and tested by millions of programmers.

Learning to pick the right STL container for a problem is one of the most important skills in competitive programming.

What you'll learn in this chapter:

• sort — sort any sequence in one line, with custom rules
• pair — bundle two values together cleanly
• map / set — ordered key-value store and unique-element collection
• stack / queue — LIFO and FIFO containers for classic algorithms
• priority_queue — always get the max (or min) in O(log N)
• unordered_map / unordered_set — hash-based O(1) lookup
• auto and range-based for — write cleaner, shorter code
• Useful STL algorithms: binary_search, lower_bound, accumulate, and more

3.1.0 The STL Toolbox

Think of the STL as a toolbox. Each tool is designed for a specific job:

Quick reference — which container to reach for:

Picking the right tool = half the solution in competitive programming!

"Which Container Should I Use?" Decision Tree

Visual: STL Containers Overview

3.1.1 sort — The Only Sort You Need

We start with sort because you'll use it in almost every problem.

What it is and why it matters

Sorting rearranges a sequence of elements into order. Rather than implementing your own sorting algorithm (which is error-prone and takes time), C++'s sort is:

• Fast: O(N log N) — the theoretical best for comparison-based sorting
• Easy to use: one line of code
• Flexible: sorts by any rule you define

⚠️ Important: sort requires #include <algorithm> (included automatically via #include <bits/stdc++.h>).

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

int main() {
    // Sorting a vector — ascending (default)
    vector<int> v = {5, 2, 8, 1, 9, 3};
    sort(v.begin(), v.end());
    // v is now: {1, 2, 3, 5, 8, 9}

    for (int x : v) cout << x << " ";
    cout << "\n";

    // Sorting descending
    sort(v.begin(), v.end(), greater<int>());
    // v is now: {9, 8, 5, 3, 2, 1}

    // Sorting an array
    int arr[] = {4, 2, 7, 1, 5};
    int n = 5;
    sort(arr, arr + n);  // sorts arr[0..n-1]
    // arr is now: {1, 2, 4, 5, 7}

    return 0;
}

Custom Sort (Lambda Functions)

What if you want to sort by something other than the natural order? Use a lambda — a small inline function:

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

// Sort by absolute value
sort(v.begin(), v.end(), [](int a, int b) {
    return abs(a) < abs(b);  // return true if a should come BEFORE b
});
// v is now: {1, 2, -3, 5, -8}  (ordered by |value|)

The lambda [](int a, int b) { return ...; } is the comparison rule. It must return true if a should come before b in the sorted result.

🐛 Common mistake: Never return true when a == b — this violates the "strict weak ordering" rule and causes undefined behavior (crash or wrong answer). Always use < or >, never <= or >=.

// Sort a vector of pairs: by second element (descending), then first element (ascending)
vector<pair<int,int>> pts = {{3,5},{1,7},{2,5},{4,3}};
sort(pts.begin(), pts.end(), [](pair<int,int> a, pair<int,int> b) {
    if (a.second != b.second) return a.second > b.second;  // bigger second first
    return a.first < b.first;   // tie-break: smaller first first
});
// Result: {1,7}, {2,5}, {3,5}, {4,3}

3.1.2 pair — Storing Two Values Together

A pair bundles two values into one object. Think of it as a "mini-struct" for two values.

Why use pair? Often you need to keep two related values together — like (value, index), (x-coordinate, y-coordinate), or (score, name). pair does this cleanly.

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

int main() {
    // Create a pair
    pair<int, int> point = {3, 5};         // (x, y)
    pair<string, int> student = {"Alice", 95};  // (name, score)

    // Access elements: .first and .second
    cout << point.first << " " << point.second << "\n";    // 3 5
    cout << student.first << ": " << student.second << "\n"; // Alice: 95

    // Pairs support comparison: compares .first first, then .second
    pair<int,int> a = {1, 3};
    pair<int,int> b = {1, 5};
    cout << (a < b) << "\n";   // 1 (true) — same .first, so compare .second: 3 < 5

    // Very common pattern: sort by second element using pairs
    vector<pair<int,int>> v = {{3,9},{1,2},{4,1},{1,5}};
    sort(v.begin(), v.end());     // sorts by .first first, then .second
    // Result: {1,2}, {1,5}, {3,9}, {4,1}

    return 0;
}

⚡ Pro Tip: When you need to sort items by one value but keep track of their original index, store them as pair<value, index> and sort. After sorting, .second gives you the original index.

💡 make_pair vs brace initialization: Both make_pair(3, 5) and {3, 5} create a pair. The brace syntax {3, 5} is shorter and preferred in modern C++ (C++11 and later).

3.1.3 map — The Dictionary

A map stores key-value pairs, like a real dictionary: given a word (key), look up its definition (value). Each key appears at most once.

When to use map

• Counting frequencies: word → count, score → frequency
• Mapping IDs to names: student_id → name
• Storing properties: cow_name → milk_production

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

int main() {
    map<string, int> phoneBook;

    // Insert key-value pairs
    phoneBook["Alice"] = 555001;
    phoneBook["Bob"] = 555002;
    phoneBook["Charlie"] = 555003;

    // Lookup by key
    cout << phoneBook["Alice"] << "\n";  // 555001

    // Iterate (always in SORTED KEY order!)
    for (auto& entry : phoneBook) {
        cout << entry.first << " -> " << entry.second << "\n";
    }
    // Prints:
    // Alice -> 555001
    // Bob -> 555002
    // Charlie -> 555003

    // Erase a key
    phoneBook.erase("Charlie");
    cout << phoneBook.size() << "\n";  // 2

    return 0;
}

Common Operations with Time Complexity

🐛 The map Access Gotcha

This is one of the most common map bugs:

map<string, int> freq;

// DANGER: accessing a non-existent key CREATES IT with value 0!
cout << freq["apple"] << "\n";  // prints 0, but now "apple" is IN the map!
cout << freq.size() << "\n";    // 1 — even though we only "looked", not "inserted"!

// SAFE way 1: check count first
if (freq.count("apple") > 0) {
    cout << freq["apple"] << "\n";  // safe — key exists
}

// SAFE way 2: use .find()
auto it = freq.find("apple");
if (it != freq.end()) {          // .end() means "not found"
    cout << it->second << "\n";  // it->second is the value
}

Frequency Counting — The Most Common map Pattern

vector<string> words = {"apple", "banana", "apple", "cherry", "banana", "apple"};
map<string, int> freq;

for (const string& w : words) {
    freq[w]++;  // if "w" doesn't exist, it's created with 0, then incremented to 1
}

// freq: apple→3, banana→2, cherry→1
for (auto& p : freq) {
    cout << p.first << " appears " << p.second << " times\n";
}

💡 Why freq[w]++ works even for new keys: map default-initializes missing values. For int, the default is 0. So accessing a new key creates it with value 0, and ++ makes it 1. This is intentional and widely used for counting.

3.1.4 set — Unique Sorted Collection

A set stores unique elements in sorted order. Insert a duplicate — it's silently ignored.

When to use set

• Removing duplicates from a list
• Checking membership quickly: "have I seen this value before?"
• Getting the minimum/maximum of a dynamic collection

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

int main() {
    set<int> s;

    s.insert(5);
    s.insert(2);
    s.insert(8);
    s.insert(2);   // duplicate — ignored! set stays {2, 5, 8}
    s.insert(1);

    // s is now: {1, 2, 5, 8}  (automatically sorted, no duplicates)

    // Check membership
    cout << s.count(2) << "\n";   // 1 (exists)
    cout << s.count(7) << "\n";   // 0 (not there)

    // Erase
    s.erase(2);   // s = {1, 5, 8}

    // Iterate (always sorted)
    for (int x : s) cout << x << " ";
    cout << "\n";   // 1 5 8

    // Min and max
    cout << *s.begin() << "\n";   // 1 (smallest; * dereferences the iterator)
    cout << *s.rbegin() << "\n";  // 8 (largest; r = reverse)

    cout << s.size() << "\n";  // 3

    return 0;
}

Common Operations with Time Complexity

Deduplication with set

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
set<int> unique_set(v.begin(), v.end());  // construct set from vector
// unique_set = {1, 2, 3, 4, 5, 6, 9}

cout << "Unique count: " << unique_set.size() << "\n";   // 7

// Convert back to sorted vector if needed:
vector<int> deduped(unique_set.begin(), unique_set.end());

💡 set vs multiset: set stores each value at most once. If you need to store duplicates but still want sorted order, use multiset<int> — it allows repeated elements.

3.1.5 stack — Last In, First Out

A stack works like a pile of plates: you can only add to the top or remove from the top. The last item added is the first one removed (LIFO: Last In, First Out).

When to use stack

• Matching brackets/parentheses
• Undo/redo history
• Depth-first search (DFS) — covered in later chapters
• Reversing a sequence

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

int main() {
    stack<int> st;

    st.push(1);    // [1]         (top is on the right)
    st.push(2);    // [1, 2]
    st.push(3);    // [1, 2, 3]

    cout << st.top() << "\n";   // 3 (peek at top without removing)
    st.pop();                    // remove top → [1, 2]
    cout << st.top() << "\n";   // 2

    cout << st.size() << "\n";  // 2
    cout << st.empty() << "\n"; // 0 (not empty)

    return 0;
}

Common Operations with Time Complexity

🐛 Common Stack Mistake: Pop Without Checking

stack<int> st;
// st.top();  // CRASH! Can't peek at top of empty stack
// st.pop();  // CRASH! Can't pop from empty stack

// Always check before accessing:
if (!st.empty()) {
    cout << st.top() << "\n";
    st.pop();
}

Classic Stack Problem: Balanced Parentheses

string expr = "((a+b)*(c-d))";
stack<char> parens;
bool balanced = true;

for (char ch : expr) {
    if (ch == '(') {
        parens.push(ch);         // opening: push onto stack
    } else if (ch == ')') {
        if (parens.empty()) {    // closing with no matching opening
            balanced = false;
            break;
        }
        parens.pop();            // match found: pop the opening
    }
}

if (!parens.empty()) balanced = false;  // unmatched opening parens remain

cout << (balanced ? "Balanced" : "Not balanced") << "\n";

3.1.6 queue — First In, First Out

A queue works like a line at a store: you join at the back and leave from the front. The first person who joined is the first to be served (FIFO: First In, First Out).

When to use queue

• Simulating a line of customers, processes, tasks
• Breadth-first search (BFS) — one of the most important algorithms in competitive programming (Chapter 5.2)
• Processing items in the order they arrived

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

int main() {
    queue<int> q;

    q.push(10);   // [10]
    q.push(20);   // [10, 20]
    q.push(30);   // [10, 20, 30]

    cout << q.front() << "\n";  // 10 (first in line — will leave first)
    cout << q.back() << "\n";   // 30 (last in line — will leave last)

    q.pop();                     // remove from front → [20, 30]
    cout << q.front() << "\n";  // 20

    cout << q.size() << "\n";   // 2

    return 0;
}

Common Operations with Time Complexity

Note: You'll use queue extensively in Chapter 5.2 for BFS — one of the most important graph algorithms for USACO.

🐛 Common mistake: queue has no top() method (that's stack). Use front() to peek at the front element and back() to peek at the rear.

3.1.7 priority_queue — The Heap

A priority_queue is like a magic queue: no matter what order you insert things, it always gives you the largest element first (max-heap by default).

When to use priority_queue

• Always need the largest (or smallest) element quickly
• Finding the K largest numbers
• Dijkstra's shortest path algorithm (Chapter 5.4)
• Greedy algorithms where you always process the "best" item next

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

int main() {
    // Max-heap: always gives you the MAXIMUM
    priority_queue<int> maxPQ;

    maxPQ.push(5);
    maxPQ.push(1);
    maxPQ.push(8);
    maxPQ.push(3);

    // Pop in decreasing order
    while (!maxPQ.empty()) {
        cout << maxPQ.top() << " ";  // always the current max
        maxPQ.pop();
    }
    cout << "\n";  // prints: 8 5 3 1

    return 0;
}

🐛 The Min-Heap Gotcha

By default, priority_queue is a max-heap (gives largest first). For a min-heap (gives smallest first), you need a special syntax:

// MAX-heap (default) — gives LARGEST first
priority_queue<int> maxPQ;

// MIN-heap — gives SMALLEST first (note the extra template arguments!)
priority_queue<int, vector<int>, greater<int>> minPQ;

minPQ.push(5);
minPQ.push(1);
minPQ.push(8);
minPQ.push(3);

while (!minPQ.empty()) {
    cout << minPQ.top() << " ";
    minPQ.pop();
}
// prints: 1 3 5 8  (smallest first)

Common Operations with Time Complexity

💡 Priority queue with pairs: You can store pair<int, int> in a priority queue. It compares by .first first, then .second — useful for Dijkstra's algorithm where you store {distance, node}.

priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> minPQ;
// min-heap of (distance, node) pairs — used in Dijkstra

3.1.8 unordered_map and unordered_set — Hash-Based Speed

The regular map and set are sorted (using a balanced binary search tree internally), giving O(log N) operations. The unordered_ variants use a hash table for O(1) average time — faster, but no guaranteed ordering.

💡 Underlying Principle: Why is map O(log N) while unordered_map is O(1)?

• map / set internally use a red-black tree (a self-balancing binary search tree). Each insert, find, or delete traverses from root to leaf, with tree height ≈ log₂N, hence O(log N). Advantage: elements are always sorted, supporting lower_bound and range queries.
• unordered_map / unordered_set internally use a hash table. The hash function directly computes the storage location, averaging O(1). But element order is not guaranteed, and worst case can degrade to O(N) (with severe hash collisions).
• Contest experience: If you only need lookup/insert without ordered traversal, prefer unordered_map. But if you get TLE from worst-case unordered_map behavior (being hacked), switching back to map is the safest choice.

unordered_map<string, int> freq;
freq["apple"]++;
freq["banana"]++;
freq["apple"]++;

cout << freq["apple"] << "\n";   // 2 (same interface as map)

unordered_set<int> seen;
seen.insert(5);
seen.insert(10);
cout << seen.count(5) << "\n";   // 1 (found)
cout << seen.count(7) << "\n";   // 0 (not found)

Hack-Resistant unordered_map

In competitive programming, adversaries can craft inputs that cause many hash collisions, degrading unordered_map to O(N) per operation. A simple defense is to use a custom hash:

// Add this before main() to make unordered_map harder to hack
struct custom_hash {
    size_t operator()(long long x) const {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9LL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebLL;
        return x ^ (x >> 31);
    }
};
unordered_map<long long, int, custom_hash> safe_map;

For most problems, the default unordered_map is fine. Use the custom hash only when you suspect anti-hash tests.

When to use which

⚡ Pro Tip: unordered_map can be 5-10× faster than map for large inputs with string keys. But it has rare "worst case" behavior that can be exploited in competitive programming — use map if you're getting TLE with unordered_map and suspect a hack.

3.1.9 The auto Keyword and Range-Based For

C++ can often figure out the type of a variable automatically. The auto keyword tells the compiler: "you figure out the type."

auto x = 42;          // x is int
auto y = 3.14;        // y is double
auto v = vector<int>{1, 2, 3};  // v is vector<int>

map<string, int> freq;
auto it = freq.find("cat");  // type would be map<string,int>::iterator — very long!
// auto saves you from writing that

⚠️ auto pitfall: auto deduces the type at compile time — it doesn't make variables dynamically typed. Also, auto x = 1000000000 * 2; deduces int and may overflow; write auto x = 1000000000LL * 2; to get long long.

Range-Based For

Clean iteration over any container:

vector<int> nums = {10, 20, 30, 40, 50};

// Read-only iteration (copies each element — fine for int, wasteful for string)
for (int x : nums) {
    cout << x << " ";
}

// Reference: no copy, can modify elements
for (int& x : nums) {
    x *= 2;   // doubles each element in-place
}

// Const reference: no copy, read-only (best for large types like string)
for (const auto& x : nums) {
    cout << x << " ";
}

Rule of thumb for range-based for:

• Small types (int, char): for (int x : v) — copy is fine
• Large types (string, pair, structs): for (const auto& x : v) — avoid copying
• Need to modify: for (auto& x : v)

3.1.10 Useful STL Algorithms

These functions from <algorithm> and <numeric> work on any sequence:

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

int main() {
    vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

    // Sort ascending
    sort(v.begin(), v.end());
    // v = {1, 1, 2, 3, 4, 5, 6, 9}

    // Binary search (on SORTED sequence only!)
    cout << binary_search(v.begin(), v.end(), 5) << "\n";  // 1 (found)
    cout << binary_search(v.begin(), v.end(), 7) << "\n";  // 0 (not found)

    // lower_bound: first position where value >= target
    auto it = lower_bound(v.begin(), v.end(), 4);
    cout << *it << "\n";   // 4
    cout << (it - v.begin()) << "\n";  // index: 3

    // upper_bound: first position where value > target
    auto it2 = upper_bound(v.begin(), v.end(), 4);
    cout << (it2 - v.begin()) << "\n";  // index: 4 (first element > 4)
    // Elements in range [lo, hi]: upper_bound(hi+1) - lower_bound(lo)

    // Min and max
    cout << *min_element(v.begin(), v.end()) << "\n";  // 1
    cout << *max_element(v.begin(), v.end()) << "\n";  // 9

    // Sum of all elements
    long long total = accumulate(v.begin(), v.end(), 0LL);
    cout << total << "\n";  // 31

    // Count occurrences
    cout << count(v.begin(), v.end(), 1) << "\n";  // 2

    // Reverse
    reverse(v.begin(), v.end());

    // Fill with a value
    fill(v.begin(), v.end(), 0);  // all zeros

    return 0;
}

3.1.11 Putting It All Together: Word Frequency Counter

Let's build a complete mini-program that uses map, vector, and sort together.

Problem: Read N words, count how many times each word appears, then print:

1. All words and their counts in alphabetical order
2. The most frequently appearing word

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    // Step 1: Count word frequencies using a map
    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string word;
        cin >> word;
        freq[word]++;   // if word is new, creates entry with 0, then increments
    }

    // Step 2: Print all words in alphabetical order (map iterates in sorted key order)
    cout << "All words:\n";
    for (auto& entry : freq) {
        // entry.first = word, entry.second = count
        cout << entry.first << ": " << entry.second << "\n";
    }

    // Step 3: Find the most frequent word
    // max_element on the map: compare by value (.second)
    auto best = max_element(
        freq.begin(),
        freq.end(),
        [](const pair<string,int>& a, const pair<string,int>& b) {
            return a.second < b.second;  // compare by count
        }
    );

    cout << "\nMost frequent: \"" << best->first << "\" (appears "
         << best->second << " times)\n";

    return 0;
}

Sample Input:

10
the cat sat on the mat the cat sat on

Sample Output:

All words:
cat: 2
mat: 1
on: 2
sat: 2
the: 3

Most frequent: "the" (appears 3 times)

Complexity Analysis:

• Time: O(N log N) — each freq[word]++ is O(log N), N times total; max_element traverses the map in O(M), where M is the number of distinct words
• Space: O(M) — map stores M distinct words

🤔 Why does iterating over map give alphabetical order? map internally uses a balanced BST (binary search tree), which keeps keys sorted. So when you iterate, you always get keys in sorted order automatically — no extra sorting needed!

💡 Alternative for finding max: Instead of max_element on the map, you could also transfer entries to a vector<pair<string,int>>, sort by .second descending, and take the first element. Both approaches are O(M) after counting.

Chapter Summary

📌 Key Takeaways

❓ FAQ

Q1: What is the difference between vector and a plain array? When to use which?

A: vector can grow dynamically (push_back), knows its own size (.size()), and can be safely passed to functions. Plain arrays have fixed size but are slightly faster (global arrays auto-initialize to 0). In contests, use vector for most cases; global large arrays (like int dp[100001]) are sometimes more convenient as C arrays.

Q2: When to choose map vs unordered_map?

A: If you only need lookup/insert/delete, use unordered_map (O(1)) for speed. If you need ordered traversal or lower_bound/upper_bound, use map (O(log N)). In contests without special requirements, map is safer (cannot be hacked).

Q3: Is priority_queue a max-heap or min-heap by default?

A: Max-heap. pq.top() returns the maximum element. For a min-heap, declare as priority_queue<int, vector<int>, greater<int>>.

Q4: When is a custom struct better than pair?

A: pair's .first/.second have poor readability — three months later you may forget what .first means. struct lets you give members meaningful names (like .weight, .value). When data has 3 or more fields, struct is necessary.

Q5: Why does sort on a vector<pair<int,int>> sort by .first first?

A: pair has a built-in operator< that compares .first first; if equal, it compares .second. This is called lexicographic order — the same way words are sorted in a dictionary. You can rely on this behavior without writing a custom comparator.

Q6: What's the difference between s.count(x) and s.find(x) != s.end() for a set?

A: For set and map, both are O(log N) and functionally equivalent for checking existence. count returns 0 or 1 (sets have no duplicates), while find returns an iterator you can use to access the element directly. Prefer find when you also need to read the value; prefer count for a simple yes/no check.

🔗 Connections to Later Chapters

• Chapter 3.4 (Monotonic Stack & Queue): monotonic stack for next-greater-element problems; monotonic deque for sliding window max/min
• Chapter 3.6 (Stacks & Queues): deep dive into stack and queue algorithm applications — bracket matching, BFS
• Chapter 3.8 (Maps & Sets): advanced usage of map/set — frequency counting, multiset
• Chapter 3.3 (Sorting): sort with custom comparators used with vector and pair
• priority_queue appears frequently in Chapter 4.1 (Greedy) and Chapter 5.3 (Kruskal MST)
• The STL containers in this chapter are the foundational tools for all subsequent chapters in this book

Practice Problems

🌡️ Warm-Up Problems

Warm-up 3.1.1 — Set Membership Read N integers, then read Q queries. For each query, read one integer and print YES if it appeared in the original N integers, NO otherwise.

5
10 20 30 40 50
3
20
35
50

YES
NO
YES

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    set<int> s;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        s.insert(x);
    }

    int q;
    cin >> q;
    while (q--) {
        int x;
        cin >> x;
        cout << (s.count(x) ? "YES" : "NO") << "\n";
    }

    return 0;
}

Warm-up 3.1.2 — Character Frequency Read a string (no spaces). Print each character that appears in it along with its count, in alphabetical order.

Sample Input: hello Sample Output:

e: 1
h: 1
l: 2
o: 1

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

int main() {
    string s;
    cin >> s;

    map<char, int> freq;
    for (char c : s) {
        freq[c]++;
    }

    for (auto& entry : freq) {
        cout << entry.first << ": " << entry.second << "\n";
    }

    return 0;
}

Warm-up 3.1.3 — Reverse with Stack Read a string (no spaces). Use a stack to print the string in reverse.

Sample Input: hello → Sample Output: olleh

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    for (char c : s) {
        st.push(c);
    }

    while (!st.empty()) {
        cout << st.top();
        st.pop();
    }
    cout << "\n";

    return 0;
}

Warm-up 3.1.4 — Queue Simulation Simulate a line of exactly 5 people. Their names are: Alice, Bob, Charlie, Dave, Eve. They join in that order. Serve them one at a time (pop from front) and print each name as they're served.

Expected Output:

Serving: Alice
Serving: Bob
Serving: Charlie
Serving: Dave
Serving: Eve

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

int main() {
    queue<string> line;
    line.push("Alice");
    line.push("Bob");
    line.push("Charlie");
    line.push("Dave");
    line.push("Eve");

    while (!line.empty()) {
        cout << "Serving: " << line.front() << "\n";
        line.pop();
    }

    return 0;
}

Warm-up 3.1.5 — Top 3 Largest Read N integers. Using a priority_queue, find and print the 3 largest values (in descending order).

Sample Input:

7
5 1 9 3 7 2 8

Sample Output:

9
8
7

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

int main() {
    int n;
    cin >> n;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < 3 && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

🏋️ Core Practice Problems

Problem 3.1.6 — Unique Elements Read N integers. Print only the unique values, in the order they first appeared (not sorted). If a value appears more than once, print it only on its first occurrence.

8
3 1 4 1 5 9 2 6

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    unordered_set<int> seen;
    bool first = true;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        if (seen.count(x) == 0) {   // haven't seen x yet
            seen.insert(x);
            if (!first) cout << " ";
            cout << x;
            first = false;
        }
    }
    cout << "\n";

    return 0;
}

7
apple banana apple cherry banana apple cherry

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    map<string, int> freq;
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        freq[w]++;
    }

    string bestWord;
    int bestCount = 0;

    // Map iterates in sorted (alphabetical) order — so first word we see with max count wins
    for (auto& entry : freq) {
        if (entry.second > bestCount) {
            bestCount = entry.second;
            bestWord = entry.first;
        }
    }

    cout << bestWord << "\n";
    return 0;
}

6 9
1 8 3 6 4 5

1 8
3 6
4 5

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, t;
    cin >> n >> t;

    set<int> seen;
    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    for (int i = 0; i < n; i++) {
        int complement = t - arr[i];  // we need arr[i] + complement = t
        if (seen.count(complement)) {
            // complement came before arr[i], print in order: complement arr[i]
            cout << complement << " " << arr[i] << "\n";
        }
        seen.insert(arr[i]);
    }

    return 0;
}

Problem 3.1.9 — Bracket Matching Read a string containing only (, ), [, ], {, }. Print YES if all brackets are properly matched and nested, NO otherwise.

Sample Input 1: {[()]} → Output: YES Sample Input 2: ([)] → Output: NO Sample Input 3: ((() → Output: NO

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

int main() {
    string s;
    cin >> s;

    stack<char> st;
    bool ok = true;

    for (char ch : s) {
        if (ch == '(' || ch == '[' || ch == '{') {
            st.push(ch);    // opening: push
        } else {
            // closing bracket
            if (st.empty()) {
                ok = false;  // no matching opening
                break;
            }
            char top = st.top();
            st.pop();

            // Check if it matches
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                ok = false;
                break;
            }
        }
    }

    if (!st.empty()) ok = false;  // leftover unmatched opening brackets

    cout << (ok ? "YES" : "NO") << "\n";
    return 0;
}

Problem 3.1.10 — Top K Elements Read N integers and K. Print the K largest values in descending order.

Sample Input:

8 3
4 9 1 7 3 5 2 8

Sample Output:

9
8
7

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    priority_queue<int> pq;
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pq.push(x);
    }

    for (int i = 0; i < k && !pq.empty(); i++) {
        cout << pq.top() << "\n";
        pq.pop();
    }

    return 0;
}

🏆 Challenge Problems

Challenge 3.1.11 — Inventory System Process M commands on a store inventory. Each command is one of:

• ADD name quantity — add quantity units of product name
• REMOVE name quantity — remove quantity units (if removing more than available, set to 0)
• QUERY name — print current quantity of name (0 if never added)

6
ADD apple 10
ADD banana 5
QUERY apple
REMOVE apple 3
QUERY apple
QUERY grape

10
7
0

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int m;
    cin >> m;

    map<string, long long> inventory;

    while (m--) {
        string cmd;
        cin >> cmd;

        if (cmd == "ADD") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] += qty;
        } else if (cmd == "REMOVE") {
            string name;
            long long qty;
            cin >> name >> qty;
            inventory[name] -= qty;
            if (inventory[name] < 0) inventory[name] = 0;
        } else {  // QUERY
            string name;
            cin >> name;
            // Use count to avoid creating an entry for missing items
            if (inventory.count(name)) {
                cout << inventory[name] << "\n";
            } else {
                cout << 0 << "\n";
            }
        }
    }

    return 0;
}

Challenge 3.1.12 — Sliding Window Maximum Read N integers and a window size K. Print the maximum value in each window of K consecutive elements.

Sample Input:

8 3
1 3 -1 -3 5 3 6 7

Sample Output:

3
3
5
5
6
7

(Windows: [1,3,-1]→3, [3,-1,-3]→3, [-1,-3,5]→5, [-3,5,3]→5, [5,3,6]→6, [3,6,7]→7)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    vector<int> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];

    deque<int> dq;  // stores indices, front = index of current maximum

    for (int i = 0; i < n; i++) {
        // Remove indices that are out of the current window
        while (!dq.empty() && dq.front() < i - k + 1) {
            dq.pop_front();
        }

        // Remove indices of elements smaller than arr[i] from the back
        // (they can never be the maximum while arr[i] is in the window)
        while (!dq.empty() && arr[dq.back()] <= arr[i]) {
            dq.pop_back();
        }

        dq.push_back(i);

        // Print maximum for windows that are full (starting from index k-1)
        if (i >= k - 1) {
            cout << arr[dq.front()] << "\n";
        }
    }

    return 0;
}

Challenge 3.1.13 — Haybales Range Count (USACO Bronze style)

N haybales are placed at various positions on a number line. Process Q queries: for each query (L, R), print how many haybales have positions in the range [L, R] inclusive.

5 4
3 1 7 5 2
1 3
2 6
4 8
1 10

3
3
2
5

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, q;
    cin >> n >> q;

    vector<int> pos(n);
    for (int i = 0; i < n; i++) cin >> pos[i];

    sort(pos.begin(), pos.end());  // must sort for binary search to work

    while (q--) {
        int l, r;
        cin >> l >> r;

        // lower_bound(l): first position >= l
        // upper_bound(r): first position > r
        // Elements in [l, r] = count between these two iterators
        auto lo = lower_bound(pos.begin(), pos.end(), l);
        auto hi = upper_bound(pos.begin(), pos.end(), r);

        cout << (hi - lo) << "\n";  // distance between iterators = count
    }

    return 0;
}

Looking Ahead: Beyond Basic STL

This chapter covered the core STL containers you'll use in 90% of problems. As you progress, you'll encounter more specialized structures:

• deque<T> — double-ended queue; supports O(1) push/pop at both front and back. Used in the sliding window maximum problem (Challenge 3.1.12) and monotonic deque (Chapter 3.4).
• multiset<T> — like set but allows duplicate elements. Useful when you need sorted order with repeats.
• bitset<N> — fixed-size sequence of bits; extremely fast for subset/membership problems.
• Trie (prefix tree) — stores strings by sharing common prefixes, enabling O(L) lookup where L is string length.

Visual: Trie Data Structure

A trie (prefix tree) stores strings by sharing common prefixes. Words "bat", "car", "card", "care", "cat" share prefixes efficiently: "ca" is stored once, branching to "r" and "t". Double-ringed nodes mark word endings. Tries are used for autocomplete, spell checking, and string matching. For string hashing alternatives, see Chapter 3.7 (Hashing Techniques).