The STL — Containers

Course 2 · Ch 2
The STL — Containers
c3-2's own "C has no standard containers" gap, finally resolved

c3-2 built a linked list and a hash table entirely by hand, because C offers nothing. This chapter is the direct payoff: the same shapes, already written, tested, and optimized, as class templates.

std::vector

#include <vector> std::vector<int> nums; nums.push_back(10); nums.push_back(20); std::cout << nums[0] << /* 10 */ std::endl;

A growable array. c3-2's own linked list required a manual malloc/free pair per node; std::vector manages its own memory internally via RAII — the caller never calls free at all.

std::vector Under the Hood

Contiguous memory, not a linked list — growing occasionally reallocates a larger block and moves every element over. Despite this, push_back is amortized O(1) — a real, important performance characteristic: individual calls are occasionally more expensive (during a reallocation), but averaged over many calls, the cost per call stays constant.

std::map

#include <map> std::map<std::string, int> ages; ages["Alice"] = 30; std::cout << ages["Alice"] << std::endl;

A direct resolution of c3-2's own hand-built hash table. std::map specifically is typically a balanced tree internally, not a hash table — giving O(log n) operations and genuine key ordering as a side benefit. std::unordered_map is the hash-table-based sibling — closer to c3-2's own separate-chaining structure — giving O(1) average operations but no ordering.

std::string

A real, growable string type — contrasted directly with c1-8's own char arrays: no manual null-termination tracking, no manual sizing, and .length()/.size() are O(1), unlike c1-8's own O(n) strlen scan. Concatenation uses +, via exactly cpp1-6's own operator overloading mechanism.

std::string greeting = "Hello, " + name + "!";

RAII All the Way Down

Every one of these containers is itself an RAII wrapper — exactly cpp1-5's own mechanism. A vector's destructor frees every element's memory automatically when the vector goes out of scope. Nothing here is new magic — it's cpp1-5's own idea, already written for you by the standard library.

ConceptC (c3-2)C++ STL
Growable lista hand-built linked list, manual free per nodestd::vector — RAII-managed, contiguous memory
Key-value storea hand-built hash table, separate chainingstd::map (ordered) / std::unordered_map (hash-based)
String lengthstrlen — O(n), scans for '\0'.length() — O(1), stored directly
std::vector is the default container choice
Reach for std::vector unless there's a specific reason for something else — std::map for real key lookups, std::unordered_map when ordering genuinely doesn't matter and average-case speed does. This matches the real-world idiomatic default in C++.
A push_back that triggers reallocation invalidates existing iterators/pointers
An operation that causes std::vector to reallocate moves every element to a new block of memory — any iterator, pointer, or reference into the old memory is left dangling. Continuing to use one afterward is undefined behavior, a genuinely real and easy-to-hit trap. Iterators get full treatment in cpp2-3.

Coding Challenges

Challenge 1

Create a std::vector, push_back five values onto it, and print each one using a plain indexed loop with operator[].

📄 View solution
Challenge 2

Create a std::map storing three people's ages, then look up and print one specific person's age by name.

📄 View solution
Challenge 3

Explain why std::vector's push_back is described as "amortized O(1)" rather than simply "O(1)," and what specifically happens during the occasional more expensive call that the amortized average accounts for.

📄 View solution

Chapter 2 Quick Reference

  • std::vector<T> — a growable, RAII-managed, contiguous array; resolves c3-2's linked-list gap
  • std::map<K, V> — ordered, tree-based; std::unordered_map — hash-based, closer to c3-2's own structure
  • std::string — O(1) length, no manual null-termination, + for concatenation via operator overloading
  • Every STL container is itself an RAII wrapper — cpp1-5's own idea, pre-written
  • Reallocation-triggering operations invalidate existing iterators/pointers/references — a real, common trap
  • Next chapter: iterators and algorithms — std::sort, std::find, and generic operations over any container