STL Containers¶

In one sentence

The STL gives you ready-made boxes for data. Pick the box by how you take things out: by index (vector), newest first (stack), oldest first (queue), or from either end (deque).

1. What problem does it solve?¶

Example — 450A · Jzzhu and Children (homework from 11 Jan, rating 1000)

\(n\) children stand in a line; child \(i\) wants at least \(a_i\) candies. Repeat: give \(m\) candies to the child at the front. If that child now has enough, they go home; otherwise they walk to the back of the line. Which child goes home last?

Limits: \(n, m, a_i \le 100\).

Input          Output
5 2
1 3 1 4 2      4

The story is a data structure: "take from the front, put at the back" is exactly a queue. If we try to use a plain array instead, we have to shift every element left each time the front child leaves, and we have to remember where the "back" is. A std::queue does both for us in \(O(1)\).

2. How the containers behave¶

2.1 Four boxes, four rules¶

vector  [ 5 | 8 | 2 | 7 ]      read any v[i]; add/remove at the back
                      ^ back

stack   [ 5 | 8 | 2 | 7 ]      only the top is visible
                      ^ top    push -> on top, pop -> removes 7   (Last In, First Out)

queue   [ 5 | 8 | 2 | 7 ]      in at the back, out at the front
          ^ front     ^ back   pop -> removes 5                  (First In, First Out)

deque   [ 5 | 8 | 2 | 7 ]      in and out at both ends
          ^ front     ^ back

Operation	`vector`	`stack`	`queue`	`deque`
add	`push_back(x)`	`push(x)`	`push(x)` (back)	`push_front(x)`, `push_back(x)`
look	`v[i]`, `back()`	`top()`	`front()`	`front()`, `back()`, `d[i]`
remove	`pop_back()`	`pop()`	`pop()` (front)	`pop_front()`, `pop_back()`
size / empty	`size()`, `empty()`	same	same	same
cost of each operation above	\(O(1)\)	\(O(1)\)	\(O(1)\)	\(O(1)\)

Two facts that trip people up:

pop() returns nothing. Read the value first with top() / front(), then pop().
stack and queue have no [i]. If you need to look inside, you wanted a vector or deque.

2.2 Trace on the example¶

Store the child number in the queue (not the candies), and keep a[i] as "candies still needed". Here \(m = 2\), a = [1, 3, 1, 4, 2].

step	front	still needs → after 2 candies	goes	queue after
start				1 2 3 4 5
1	1	1 → −1	home	2 3 4 5
2	2	3 → 1	back	3 4 5 2
3	3	1 → −1	home	4 5 2
4	4	4 → 2	back	5 2 4
5	5	2 → 0	home	2 4
6	2	1 → −1	home	4
7	4	2 → 0	home	(empty)

The last child to go home is 4.

Cost. Every visit removes \(m \ge 1\) candies from one child, so child \(i\) is visited at most \(a_i\) times: at most \(100 \cdot 100\) queue operations.

3. Lesson notes (11 January)¶

During our last lecture on Jan 11, we learned about some powerful tools in C++: the STL Containers. Here is a lecture note summary.

1. Pointers & References¶

We briefly looked at how computer memory works using Pointers (*) and References (&). * Concept: Memory addresses are like "house numbers" for your data. * Note: While this is cool to know, for USACO, you don't need to worry too much about managing memory manually. We have better tools for that!

2. Common STL Containers¶

We focused on the Standard Template Library (STL). These are pre-built data structures that save you a lot of time. Here is the code syntax for each:

`std::vector`¶

Concept: A dynamic array (can grow/shrink).

Code Example:

std::vector<int> v;
v.push_back(5);    // Add 5 to the end
cout << v[0];      // Access element at index 0
cout << v.back();  // Access the last element
v.size();          // Get the size

`std::stack`¶

Concept: LIFO (Last In, First Out).

Code Example:

std::stack<int> s;
s.push(10);      // Add to top
cout << s.top(); // Look at the top element
s.pop();         // Remove the top element

`std::queue`¶

Concept: FIFO (First In, First Out).

Code Example:

std::queue<int> q;
q.push(20);      // Add to the back
cout << q.front(); // Look at the front element (first one in)
q.pop();         // Remove the front element

`std::deque`¶

Concept: Double-ended Queue (can add/remove from both sides).

Code Example:

std::deque<int> d;
d.push_front(1); // Add to front
d.push_back(2);  // Add to back
cout << d.front() << " " << d.back(); // Access the front/back element
d.pop_front();   // Remove from front
d.pop_back();    // Remove from back

3. Using vector to simulate a stack¶

We learned that std::vector is very flexible. We can use it just like a stack using these three functions:

std::vector<int> v;

v.push_back(10); // Add to the end (top of stack)
v.back();        // Look at the last element (top of stack)
v.pop_back();    // Remove the last element

4. Check if the container is empty¶

We can use .empty() for any data structure in STL to check if it is empty or not. The return value has the bool type: true/false.

std::vector<int> v;
std::deque<int> d;
std::queue<int> q;
std::stack<int> s;
std::set<int> st;

v.empty();
d.empty();
q.empty();
s.empty();
st.empty();

4. Worked solution — Jzzhu and Children¶

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    // the queue holds child numbers, a[i] is what child i still needs
    queue<int> q;
    for (int i = 1; i <= n; i++) {
        q.push(i);
    }

    int last = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        a[u] -= m;
        if (a[u] > 0) {
            q.push(u);
        } else {
            last = u;
        }
    }

    cout << last << "\n";
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int T = 1;
    for (int i = 0; i < T; i++) {
        solve();
    }
    return 0;
}

5. Which container?¶

The problem says…	Use
"the \(i\)-th element", sort, scan left to right	`vector`
"undo the last action", matching brackets, "most recent"	`stack` (or a `vector` with `push_back` / `back` / `pop_back`)
"line", "wait your turn", "go to the back", BFS	`queue`
"take from either end"	`deque`

6. Common mistakes¶

top() / front() / back() on an empty container

This is undefined behaviour: the program may crash or print garbage. Always check !q.empty() first; the while (!q.empty()) loop does it for you.

Expecting pop() to give you the value

int x = q.pop(); does not compile. Write int x = q.front(); q.pop();.

Storing the wrong thing in the queue

In Jzzhu and Children the answer is a child number. If you push the candy counts, you lose track of who is who. Push indices and look the data up in an array.

v[i] past the end

vector<int> v(n) has indices \(0 \dots n - 1\). If you read into a[1..n], create it with size n + 1.

7. Practice¶

Problem	Set	Rating	Idea
266A · Stones on the Table	homework 11 Jan	800	compare neighbours
734A · Anton and Danik	homework 11 Jan, 1-vector_sort · B	800	two counters
344A · Magnets	homework 11 Jan	800	compare with the previous item
450A · Jzzhu and Children	homework 11 Jan	1000	queue of indices (this page)
677A · Vanya and Fence	1-vector_sort · A	800	one pass over a vector
231A · Team	1-vector_sort · F	800	count per row
58A · Chat room	1-vector_sort · H	1000	match "hello" as a subsequence

Credits & licenses

§3 is the lesson note from 11 January, unchanged apart from heading levels.
The example choice, container diagrams, trace table, worked solution, mistakes and practice list are ours. Problem statements are summarised; the originals are on Codeforces.

STL Containers¶

1. What problem does it solve?¶

2. How the containers behave¶

2.1 Four boxes, four rules¶

2.2 Trace on the example¶

3. Lesson notes (11 January)¶

1. Pointers & References¶

2. Common STL Containers¶

std::vector¶

std::stack¶

std::queue¶

std::deque¶

3. Using vector to simulate a stack¶

4. Check if the container is empty¶

4. Worked solution — Jzzhu and Children¶

5. Which container?¶

6. Common mistakes¶

7. Practice¶

`std::vector`¶

`std::stack`¶

`std::queue`¶

`std::deque`¶