STL Containers & Iterators

Scope: The Standard Template Library provides battle-tested data structures, algorithms, and iterators. This lesson covers the container families — sequence and associative — how to choose between them, and the iterator concept that connects containers to algorithms.

The STL at a glance

The STL is divided into three cooperating parts: containers store data, iterators move through it, and algorithms operate on ranges of it. Containers manage their own memory through RAII — you saw std::vector in the composite types lesson; here is the full family.

Choosing a container

Container	Strengths	Best for
`std::vector`	contiguous, fast index, fast append	the default; most collections
`std::deque`	fast append/remove at both ends	queues, ring buffers
`std::list`	fast insert anywhere (if you hold the position)	rarely needed; poor cache behavior
`std::map`	sorted key → value lookup	lookup by key, ordered iteration
`std::unordered_map`	average O(1) lookup by key	fast lookups, order not needed
`std::set` / `std::unordered_set`	unique keys with membership tests	"have I seen this?" checks

Rule of thumb: reach for std::vector first. Only switch when a specific operation (frequent middle insertion, fast key lookup, uniqueness) is your actual bottleneck.

std::vector

std::vector is the default container: elements are stored contiguously, so indexing is instant and cache-friendly, and appending is amortized constant time. It grows in reserved chunks, not one element at a time.

#include <vector>

std::vector<double> prices;
prices.push_back(9.99);          // append
prices.push_back(12.50);
std::cout << prices[1] << "\n";  // 12.5 — instant index access
std::cout << prices.size();      // 2

prices[0] = 8.49;                // modify in place
for (double p : prices) {        // range-for iteration
    std::cout << p << " ";
}

Preallocate when the final size is known: std::vector<int> v(1000); avoids repeated reallocation. Indexing with [] is unchecked; use at() when you want an exception on out-of-range access.

Associative containers

Associative containers store key → value pairs and look them up by key instead of by position. std::map keeps keys sorted (a balanced tree); std::unordered_map uses a hash table with average O(1) lookup.

#include <map>
#include <string>

std::map<std::string, int> population;
population["Tokyo"] = 37_000_000;
population["Oslo"]  = 1_000_000;
std::cout << population["Tokyo"] << "\n";   // 37000000

if (population.count("Oslo")) {              // 0 or 1 — membership test
    std::cout << "Oslo is listed\n";
}
for (const auto &[city, count] : population) {   // structured bindings (C++17)
    std::cout << city << ": " << count << "\n";   // iterates in sorted key order
}

Careful: population["NewYork"] inserts a default value when the key is missing. For read-only probes use find or count first.

Iterators

An iterator is a lightweight object that points at an element and can move to the next. It generalizes the pointer you learned about: begin() returns the first element, end() one past the last.

std::vector<int> v{10, 20, 30};
for (auto it = v.begin(); it != v.end(); ++it) {
    std::cout << *it << " ";    // dereference like a pointer
}

Range-for under the hood

The range-based for is literally sugar over this loop — the compiler expands for (int x : v) into iterator code. Because every container provides begin()/end(), the same syntax works everywhere, including on your own classes if you implement those members.

Practice

Read ten numbers into a vector, print them sorted, and print the median.
Use std::map<std::string, int> to count word frequencies in a sentence.
Compare map and unordered_map on insertion/searches of 10,000 keys and report the time difference.
Iterate a vector with an explicit iterator and with range-for; confirm both print the same sequence.