> ## Documentation Index
> Fetch the complete documentation index at: https://docs.hnuicpc.tech/llms.txt
> Use this file to discover all available pages before exploring further.

# STLs 1

> Tutorial for Sheet 5 — Master the C++ Standard Template Library: vectors, sets, maps, and more.

<iframe width="100%" height="400" src="https://www.youtube.com/embed/ho_QjHK3mg8" title="Level 0 Session 5 Recording" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture" allowfullscreen />

## What is the STL?

The **Standard Template Library** is a collection of ready-to-use data structures and algorithms in C++. Mastering the STL is essential for competitive programming — it saves you from writing boilerplate code.

## Vector

A dynamic array that can grow and shrink.

```cpp theme={null}
vector<int> v;
v.push_back(10);        // Add to end: [10]
v.push_back(20);        // [10, 20]
v.push_back(30);        // [10, 20, 30]

v.pop_back();           // Remove last: [10, 20]
v.size();               // 2
v.empty();              // false

v[0];                   // 10
v.front();              // 10
v.back();               // 20

v.clear();              // Remove all elements
```

### Iterating

```cpp theme={null}
// Index-based
for (int i = 0; i < v.size(); i++) cout << v[i] << " ";

// Range-based for
for (int x : v) cout << x << " ";

// Iterator
for (auto it = v.begin(); it != v.end(); it++) cout << *it << " ";
```

## Set

A collection of **unique** elements, automatically **sorted**. Operations are O(log n).

```cpp theme={null}
set<int> s;
s.insert(5);            // {5}
s.insert(3);            // {3, 5}
s.insert(5);            // {3, 5} — duplicate ignored
s.insert(1);            // {1, 3, 5}

s.erase(3);             // {1, 5}
s.count(5);             // 1 (exists)
s.count(3);             // 0 (doesn't exist)
s.find(5);              // Iterator to 5

// First and last elements
*s.begin();             // 1 (smallest)
*s.rbegin();            // 5 (largest)
```

### Multiset

Like `set`, but allows **duplicates**:

```cpp theme={null}
multiset<int> ms;
ms.insert(5);
ms.insert(5);
ms.insert(3);           // {3, 5, 5}

ms.count(5);             // 2
ms.erase(ms.find(5));    // Remove ONE occurrence: {3, 5}
ms.erase(5);             // Remove ALL occurrences of 5: {3}
```

<Warning>
  In `multiset`, `erase(value)` removes **all** occurrences. To remove just one, use `erase(find(value))`.
</Warning>

## Map

A collection of **key-value** pairs, sorted by key. Operations are O(log n).

```cpp theme={null}
map<string, int> mp;
mp["Ahmed"] = 95;
mp["Sara"] = 88;
mp["Omar"] = 92;

// Access
cout << mp["Ahmed"];     // 95

// Check if key exists
if (mp.count("Sara")) cout << "Found";
if (mp.find("Omar") != mp.end()) cout << "Found";

// Iterate
for (auto& [key, value] : mp) {
    cout << key << ": " << value << "\n";
}

// Size
mp.size();               // 3

// Erase
mp.erase("Sara");
```

### Frequency counting with map

```cpp theme={null}
string s;
cin >> s;

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

for (auto& [ch, cnt] : freq) {
    cout << ch << " appears " << cnt << " times\n";
}
```

## Stack

LIFO (Last In, First Out):

```cpp theme={null}
stack<int> st;
st.push(1);              // [1]
st.push(2);              // [1, 2]
st.push(3);              // [1, 2, 3]

st.top();                // 3
st.pop();                // [1, 2]
st.size();               // 2
st.empty();              // false
```

## Queue

FIFO (First In, First Out):

```cpp theme={null}
queue<int> q;
q.push(1);               // [1]
q.push(2);               // [1, 2]
q.push(3);               // [1, 2, 3]

q.front();               // 1
q.back();                // 3
q.pop();                 // [2, 3]
```

## Summary table

| Container  | Ordered? | Duplicates? | Access     | Insert/Delete        |
| ---------- | -------- | ----------- | ---------- | -------------------- |
| `vector`   | By index | Yes         | O(1)       | O(1) amortized (end) |
| `set`      | Sorted   | No          | O(log n)   | O(log n)             |
| `multiset` | Sorted   | Yes         | O(log n)   | O(log n)             |
| `map`      | By key   | No (keys)   | O(log n)   | O(log n)             |
| `stack`    | LIFO     | Yes         | O(1) top   | O(1)                 |
| `queue`    | FIFO     | Yes         | O(1) front | O(1)                 |

## Practice

<Card title="Sheet 5: STLs 1" icon="list-check" href="/level-0/sheets/sheet-5" horizontal>
  Practice problems for this tutorial.
</Card>