STL Containers

Standard containers own elements and expose a common iterator-based vocabulary. Start with std::vector: it is dynamically sized, contiguous, cache-friendly, and provides O(1) random access and amortized O(1) insertion at the end.

#include <map>
#include <set>
#include <string>
#include <vector>

std::vector<int> scores{70, 90};
scores.push_back(85);

std::map<std::string, int> counts;
++counts["C++"];

std::set<int> unique{3, 1, 3}; // {1, 3}

std::list is a doubly linked sequence with stable iterators and constant-time insertion at a known position, but no random access and poor locality. std::deque supports efficient growth at both ends. std::array has fixed size.

Keys and adapters

std::map and std::set are ordered tree-based containers with O(log n) search. Their unordered_ counterparts use hashing and offer average O(1) lookup, subject to hash quality and rehashing. multimap and multiset allow duplicate keys. stack, queue, and priority_queue adapt underlying containers to restricted interfaces.

Understand invalidation: vector reallocation invalidates all element pointers, references, and iterators; erasing from a list invalidates only erased elements; unordered rehashing invalidates iterators. Use reserve when vector growth is predictable, try_emplace to construct map values only when needed, and find/contains when lookup must not insert. Choose a container from access pattern, ordering, ownership, and measured performance—not habit.