The Standard Template Library (STL)

After this lesson, you will be able to: Use the STL containers (vector, map, unordered_map, set, string) and standard algorithms fluently.

The STL is what makes C++ productive. If you can't reach for std::sort, std::unordered_map, std::find_if without thinking, you're slower than you should be.

Prerequisites:References and const

The containers you actually use

90% of real C++ code is these four + std::string.

tsx

#include <vector>
#include <unordered_map>
#include <set>
#include <string>
#include <algorithm>

std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};
nums.push_back(5);              // amortized O(1)
nums.size();                    // O(1)
int& first = nums.front();      // O(1)
std::sort(nums.begin(), nums.end());  // O(n log n)
std::sort(nums.begin(), nums.end(), std::greater<int>{});  // descending

// unordered_map (hash map), go-to associative container
std::unordered_map<std::string, int> counts;
counts["apple"] = 3;            // O(1) amortized
counts["apple"]++;              // O(1)
if (counts.contains("banana"))  /* C++20 */ ;

// map (red-black tree, sorted), slower but keys ordered
std::map<std::string, int> sortedCounts;
// iterating yields keys in sorted order

// set (sorted unique values)
std::set<int> unique = {1, 2, 3, 2, 1};   // contains {1, 2, 3}

// string is just a container of chars
std::string s = "hello";
s += ", world";
bool found = s.find("world") != std::string::npos;

Iterators + algorithms

Algorithms work on iterator pairs; containers expose .begin() / .end().

tsx

#include <algorithm>
#include <numeric>

std::vector<int> nums = {3, 1, 4, 1, 5, 9, 2, 6};

// Sort, reverse, find
std::sort(nums.begin(), nums.end());
std::reverse(nums.begin(), nums.end());
auto it = std::find(nums.begin(), nums.end(), 4);
if (it != nums.end()) std::cout << "Found at " << (it - nums.begin()) << "\n";

// Predicates with lambdas
int cnt = std::count_if(nums.begin(), nums.end(),
    [](int x) { return x > 3; });

auto evens = std::vector<int>{};
std::copy_if(nums.begin(), nums.end(), std::back_inserter(evens),
    [](int x) { return x % 2 == 0; });

// Numeric algorithms
int sum = std::accumulate(nums.begin(), nums.end(), 0);

// Transform (map equivalent)
std::vector<int> squared;
std::transform(nums.begin(), nums.end(), std::back_inserter(squared),
    [](int x) { return x * x; });

Container choice cheat sheet

std::vector, default for sequence. Contiguous, cache-friendly, fast iteration. std::array, fixed-size, on stack, faster than vector for tiny known sizes. std::unordered_map, default for key-value. O(1) avg, hash-based. std::map, when you need keys in sorted order (rare). std::deque, push to both ends. Rarely the right answer; usually use vector. std::list, almost never. Cache-hostile linked list.

Common mistakes

Using std::list (almost never the right choice, caches hate it). Iterating with index when range-based for works. Forgetting `[]` on unordered_map silently INSERTS a default-constructed value. Use `.find()` or `.contains()` to check existence. Storing references in containers (illegal; use pointers or std::reference_wrapper).

←References and const Correctness

Back to C++

Smart Pointers and RAII→