📦 Containers, Iterators, and the STL Shape

Why it matters

The C++ standard library is small in surface area but dense in design. There are six interesting containers, a handful of free-function algorithms, and one big idea — iterators — connecting them. The genius of the design is that std::sort doesn’t know about std::vector, and std::vector doesn’t know about std::sort. They communicate through an iterator pair. The same sort works on arrays, vectors, deques, and your own homegrown sequences, with no inheritance, no virtual dispatch, no runtime cost.

Once you see iterators, the STL stops being a memorized list of functions and becomes a coherent toolbox. The previous six lessons set up the machinery (value semantics, RAII, move). This lesson is what they were machinery for.

The container menu

There are roughly seven containers worth knowing by name. The rest are specializations or wrappers.

The defaults to reach for:

• std::vector when you don’t have a strong reason for something else. Cache-friendly, supports random access, amortizes growth via doubling.
• std::unordered_map when you need key→value lookup. It’s a hash table. Don’t use plain std::map unless you specifically need the sorted iteration.
• std::string for text, std::string_view for referring to text without owning it.

The rest fill specific niches. You’ll know when you need them.

std::vector is the workhorse

90% of what you’d reach for an array for in another language. Lesson 03 showed its memory layout: a fixed-size header on the stack pointing at a heap-allocated array of elements.

#include <iostream>
#include <vector>
#include <string>

int main() {
std::vector<int> v;                  // empty, 0 elements, 0 capacity
v.reserve(8);                        // ask for capacity (no construction yet)
std::cout << "after reserve(8): size=" << v.size() << " capacity=" << v.capacity() << "\n";

for (int i = 0; i < 5; i++) v.push_back(i * i);
std::cout << "after 5 push_backs: size=" << v.size() << " capacity=" << v.capacity() << "\n";

v.emplace_back(100);                 // construct directly in place — no temp
std::cout << "v[5] = " << v[5] << "\n";

// Element access: 4 ways, only one of which is bounds-checked.
std::cout << "v[0]      = " << v[0]      << "  (unchecked)\n";
std::cout << "v.at(0)   = " << v.at(0)   << "  (throws on OOB)\n";
std::cout << "v.front() = " << v.front() << "  (first element)\n";
std::cout << "v.back()  = " << v.back()  << "  (last element)\n";
return 0;
}

after reserve(8): size=0 capacity=8
after 5 push_backs: size=5 capacity=8
v[5] = 100
v[0]      = 0  (unchecked)
v.at(0)   = 0  (throws on OOB)
v.front() = 0  (first element)
v.back()  = 100  (last element)

g++ -std=c++23 -O2 snippet.cpp && ./a.out

Two methods worth knowing apart:

• push_back(T) — moves or copies an existing T into the next slot.
• emplace_back(args...) — constructs a T in place from args, skipping the temporary. For cheap types (int, double) the difference is zero. For types whose construction allocates, emplace_back can be measurably faster.

std::string and std::string_view

std::string is essentially std::vector<char> with extra methods. It owns its bytes. Most implementations use SSO (Small String Optimization) — short strings (~15 chars on most platforms) live inline in the string header, avoiding a heap allocation. Past that threshold, it spills to the heap.

std::string_view is a non-owning view: a pointer + length. Cheap to copy, cheap to pass. Use it for read-only parameters where you don’t need to keep the string around past the function call.

#include <iostream>
#include <string>
#include <string_view>

void show(std::string_view sv) {           // no copy, no allocation
std::cout << "  view: '" << sv << "' (length " << sv.size() << ")\n";
}

int main() {
std::string owned = "hello, world";
std::string_view sv = owned;             // view into owned's bytes

show(owned);                             // implicit conversion to view
show("a string literal");                // also a view — no copy
show(sv.substr(0, 5));                   // substr on a view doesn't allocate

std::cout << "owned.size()=" << owned.size() << "  capacity=" << owned.capacity() << "\n";
return 0;
}

  view: 'hello, world' (length 12)
view: 'a string literal' (length 16)
view: 'hello' (length 5)
owned.size()=12  capacity=15

g++ -std=c++23 -O2 snippet.cpp && ./a.out

The trap: string_view doesn’t own its bytes. If the underlying string dies, the view dangles. Never return a string_view to a local std::string; never store one past the lifetime of what it views. The compiler won’t catch this — it’s the price of zero-cost.

unordered_map is the hash table

When people say “I want a Python dict” in C++, they want std::unordered_map. Average O(1) lookup, ammortized O(1) insert.

#include <iostream>
#include <unordered_map>
#include <string>

int main() {
std::unordered_map<std::string, int> counts{
  {"apple", 3}, {"banana", 1}, {"cherry", 7},
};

counts["apple"]++;                          // operator[] inserts if absent (with value 0)
counts.insert({"date", 2});                 // insert: returns {iterator, bool}

if (auto it = counts.find("cherry"); it != counts.end()) {
  std::cout << "cherry x" << it->second << "\n";
}

std::cout << "size = " << counts.size() << "\n";
for (const auto& [k, v] : counts) {         // structured binding — C++17
  std::cout << "  " << k << " -> " << v << "\n";
}
return 0;
}

cherry x7
size = 4
apple -> 4
banana -> 1
cherry -> 7
date -> 2
# (iteration order is unspecified — depends on the hash and bucket layout)

g++ -std=c++23 -O2 snippet.cpp && ./a.out

Two gotchas:

• m[key] inserts if the key is absent (with a default-constructed value). If you want “look up but don’t insert,” use m.find(key) or m.contains(key) (C++20).
• Iteration order is unspecified. Hash maps don’t promise any order. Use std::map if you need keys in sorted order.

Iterators: the universal cursor

An iterator is a generalization of a pointer. It has, at minimum, three operations:

• *it — dereference to get the current element.
• ++it — advance to the next.
• it == other — compare for equality.

A range in the STL is conventionally a pair of iterators: [begin, end). begin points at the first element; end points one past the last. Half-open intervals, like every other range API in computing, because they compose better.

#include <iostream>
#include <vector>

int main() {
std::vector<int> v{10, 20, 30, 40};

// Three equivalent ways to walk it:
std::cout << "iterator:\n";
for (auto it = v.begin(); it != v.end(); ++it) {
  std::cout << "  " << *it << "\n";
}

std::cout << "indexed:\n";
for (std::size_t i = 0; i < v.size(); i++) {
  std::cout << "  " << v[i] << "\n";
}

std::cout << "range-for:\n";
for (int x : v) {
  std::cout << "  " << x << "\n";
}
// The third form is sugar for the first.
return 0;
}

iterator:
10
20
30
40
indexed:
10
20
30
40
range-for:
10
20
30
40

g++ -std=c++23 -O2 snippet.cpp && ./a.out

Iterators are typed. A std::vector<int>::iterator is not the same type as a std::list<int>::iterator. They both satisfy the iterator concept — and that’s how generic algorithms work.

Iterator categories: what you can do with this cursor

The STL classifies iterators by what operations they support, in order of increasing power:

Algorithms list their iterator requirement in the docs. std::sort needs random-access iterators; you can’t sort a std::list with it. (You’d use list.sort(), the member function.) std::find only needs input iterators, so it works on everything.

Reading this hierarchy is how you predict what’s possible. “Can I lower_bound on this?” → yes if it’s a sorted random-access range. “Can I reverse it?” → yes if it’s bidirectional. The compiler will reject mismatches; the error messages are spectacular, which is what concepts (lesson 10) were invented to fix.

auto + iterator declarations

You will almost never spell an iterator type by hand. auto is mandatory:

std::map<std::string, int> m = …;

// Awful:
std::map<std::string, int>::const_iterator it = m.find("key");

// Fine:
auto it = m.find("key");

This is the most common everyday use of auto. The type is determined by the container; you don’t need to repeat it.

Const iterators and cbegin

Every container also offers cbegin() / cend() — iterators that don’t let you mutate the elements they point at. Use them in code that’s documenting “I only read this”:

for (auto it = v.cbegin(); it != v.cend(); ++it) {
  // *it is const T&
}

Equivalent: for (const auto& x : v) …. Pick the spelling that reads clearest in context.

When the STL says “this is faster” — verify

The standard mandates complexity (Big-O) for every container operation, not constant factors. std::list has O(1) splice; std::vector has O(n) mid-insert. On paper, list should win for “lots of mid-insertions.”

In practice, std::vector almost always wins on real workloads because cache locality dominates Big-O for small-to-medium n. Bjarne Stroustrup’s famous benchmark: even for n=10,000, a std::vector<int> beats a std::list<int> on insert-in-sorted-position because the linear shift on a contiguous array is faster than the constant-time link manipulation that thrashes the cache.

Don’t pick a container by Big-O alone. Benchmark. The standard library is full of structures (std::list, std::deque, std::map) that are theoretically better than std::vector and std::unordered_map for specific operations, and lose in practice because of how modern CPUs work.

Key takeaways

• The container menu is short: std::vector by default, std::unordered_map for key-value, std::string + std::string_view for text.
• std::vector wins more often than its Big-O suggests because of cache locality. Profile before reaching for a fancier container.
• string_view is non-owning. Don’t store it past the lifetime of what it points at.
• Containers expose iterators as begin() / end(). A range is a pair [begin, end). Algorithms work on the iterator-pair interface.
• Iterator categories (input < forward < bidirectional < random-access < contiguous) decide which algorithms can use a given range.
• auto is the spelling for iterator declarations. Don’t type std::vector<int>::const_iterator.

What’s next

Lesson 08 fills in the second half of the STL story: the algorithms that consume iterator ranges, and the C++20 ranges that replace the clumsy iterator-pair API with composable views.