C++ Dynamic Arrays
## General info
- Automatically resizes when it runs out of space
- When full, allocates new array and copies old elements to new one
## Cost
- Total cost is amortized to O(1) since you rarely need to resize
- Read/write i-th element or add/remove from the end: O(1)
- Inserting/removing from the middle uses O(n) because you need to shift over the elements
## Methods
| Method | Example usage | Description |
| ------------------- | ----------------------------------------------- | -------------------------------- |
| `push_back(val)` | `v.push_back(5);` | Add element to end |
| `pop_back()` | `v.pop_back();` | Remove last element |
| `size()` | `[Link]();` | Get number of elements |
| `empty()` | `[Link]();` | Check if vector is empty |
| `clear()` | `[Link]();` | Remove all elements |
| `at(i)` | `[Link](2)` | Access element with bounds check |
| `front()` | `[Link]();` | First element |
| `back()` | `[Link]();` | Last element |
| `insert()` | `[Link]([Link]()+1, 10);` | Insert element at position |
| `erase()` | `[Link]([Link]()+1);` | Remove element at position |
| `begin()` / `end()` | `for(auto it = [Link](); it != [Link](); ++it)` | Iterators for loops |
C++ Hash Maps
- `insert({key, value})` — Insert a key-value pair.
- `operator[]` — Access or insert by key: `map[key]`.
- `find(key)` — Returns iterator to key or `end()` if not found.
- `erase(key)` — Remove a key.
- `size()` — Number of elements.
- `clear()` — Remove all elements.
- `empty()` — Check if map is empty.
- `count(key)` — Returns 1 if key exists, 0 otherwise.
- `begin()` / `end()` — Iterators for looping.
- `bucket_count()` — Number of buckets in the hash table.
- `rehash(n)` — Set number of buckets to at least `n`.
- `reserve(n)` — Pre-allocate space for `n` elements.
- `max_size()` — Maximum possible number of elements.