STL Containers

Sequence containers

• std::array<T, N>: fixed-size wrapper over stack-style storage
• std::vector<T>: dynamic contiguous storage, default first choice
• std::deque<T>: efficient push/pop at both ends
• std::list<T>: linked list, rarely the best option
• std::forward_list<T>: singly linked list

std::vector<int> values{1, 2, 3};
values.reserve(16);

For most dynamic sequences, std::vector is the default because contiguous storage is simple, cache-friendly, and broadly compatible with algorithms.

Associative containers

• std::set<T> / std::multiset<T>
• std::map<K, V> / std::multimap<K, V>

Tree-based and ordered by key.

std::map<std::string, int> counts;
counts["Ada"] = 1;

Unordered containers

• std::unordered_set<T>
• std::unordered_map<K, V>

Hash-based with average constant-time lookup.

std::unordered_map<std::string, int> counts;
counts["Ada"] = 1;

Choose unordered containers when fast lookup matters more than sorted traversal.

Container adapters

• std::stack<T>
• std::queue<T>
• std::priority_queue<T>

Adapters intentionally hide some underlying-container operations so the API matches the data-structure role more closely.

Common operations

std::vector<int> values{1, 2, 3};
values.push_back(4);
values.emplace_back(5);
values.erase(values.begin());

Iteration

for (auto it = values.begin(); it != values.end(); ++it) {
    std::cout << *it << '\n';
}

Selection rules

• Default to std::vector
• Use std::array when size is fixed at compile time
• Use std::unordered_map for fast key lookup when ordering is irrelevant
• Use ordered maps and sets when sorted traversal matters

Fast choice table

• growable list of values: std::vector
• fixed-size small aggregate: std::array
• key-value with sorted iteration: std::map
• key-value with fast average lookup: std::unordered_map
• FIFO processing: std::queue
• highest-priority item first: std::priority_queue

Iterator invalidation quick notes

• std::vector: insert/erase may invalidate iterators and references after the changed position; reallocation invalidates all of them.
• std::deque: middle insert/erase can invalidate many iterators.
• std::list and std::forward_list: iterators stay valid except for erased elements.
• Associative containers usually keep iterators stable across insertions.

When container choice affects references, iterators, or views held elsewhere in the program, invalidation rules often matter more than raw big-O complexity.

Common mistakes

• calling std::map::operator[] when you only want to check existence (it inserts a default value)
• reserving in a std::map or std::set (they do not support reserve)
• using std::list by default rather than std::vector (linked lists are rarely faster in practice due to cache effects)
• forgetting that emplace_back constructs in-place, while push_back copies or moves

Modern container-adjacent tools

void render(std::span<const int> pixels);
std::mdspan<float, std::extents<std::size_t, 4, 4>> matrix(view_ptr);

• std::span gives a lightweight view over contiguous data.
• std::mdspan is a C++23 multidimensional non-owning view.

Practical selection hints

• Prefer emplace_back when constructing elements directly in place.
• Call reserve() when you know approximate vector growth.
• Reach for flat_map style containers only through external libraries when profiling justifies them.

Common mistakes

• choosing std::list for performance without measuring
• forgetting reserve() for obviously growing vectors
• using ordered maps when hash lookup would fit better
• keeping iterators across operations that may invalidate them