# Containers and Their Costs — C++

Source: https://www.skillbyai.com/en/cpp/s-containers

> Choose the right STL container from its operations and complexity.

## The right container for the job

The **Standard Template Library (STL)** provides generic containers. **`std::vector<T>`** is a dynamic array: contiguous, cache-friendly, O(1) indexing and amortised O(1) `push_back`, O(n) insertion in the middle; it should be your **default container**. **`std::array<T, N>`** is a fixed-size array with value semantics, replacing C arrays. **`std::string`** is a vector-like container of characters. **`std::deque`** supports fast insertion at both ends. **`std::list`** is a doubly linked list; it is rarely the best choice because of poor memory locality. **Ordered associative** containers, **`std::map`** and **`std::set`** (usually red-black trees), keep keys sorted with O(log n) operations. **Unordered** containers, **`std::unordered_map`** and **`std::unordered_set`** (hash tables), give average O(1) lookups without ordering. Adaptors include **`std::stack`**, **`std::queue`** and **`std::priority_queue`** (a max-heap by default). Remember that operations on a container can **invalidate iterators, pointers and references**: a vector reallocation invalidates all of them.

## Container families

Sequence containers keep order of insertion; associative containers organise by key.

![Two groups: a row of adjacent boxes and a chain of linked boxes on the left; a small balanced tree and a grid of buckets on the right.](assets/figures/cpp/section-5-map.svg) — Figure 5.1 — Sequence, ordered associative and unordered associative containers.

## Common containers in use

vector by default; map when you need order; unordered_map for fast lookup.

```cpp
#include <map>
#include <queue>
#include <string>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> marks{72, 45, 90};
    marks.push_back(66);                         // amortised O(1)
    marks.reserve(1000);                         // avoid repeated reallocations

    std::map<std::string, int> ranked{{"Ravi", 2}, {"Asha", 1}};   // sorted by key
    for (const auto& [name, rank] : ranked) { /* Asha, then Ravi */ }

    std::unordered_map<std::string, int> stock;
    stock["pen"] += 10;                          // operator[] inserts 0 if missing
    if (auto it = stock.find("pad"); it == stock.end()) { /* not found */ }
    bool has_pen = stock.contains("pen");        // C++20

    std::priority_queue<int> pq;                 // max-heap
    pq.push(5); pq.push(42); pq.push(17);
    int top = pq.top();                          // 42

    std::priority_queue<int, std::vector<int>, std::greater<>> min_pq;   // min-heap
}
```

## operator[] on a map inserts

`if (counts[key] > 0)` silently inserts `key` with value 0 when it is missing, growing the map and breaking const-correctness. Use `find`, `contains` or `at` (which throws if missing) for lookups.

**Quiz:** Which container should be your default choice for a sequence of elements in C++?

- [x] std::vector
- [ ] std::list
- [ ] std::map
- [ ] std::deque

*Answer:* std::vector. vector is contiguous, cache-friendly and efficient for most workloads.