The C++ standard library: containers and algorithms
You use STL containers knowing when to pick which, and write safe, fast code with algorithms and utility libraries instead of hand-written loops.
Level 201 · 20 lessons · 18 practice labs
Lessons
Containers in depth
- Sequence containers: vector, deque, list, array
- Associative containers: map, multimap, set
- unordered_map and your own hash function
- Container adaptors: stack, queue, priority_queue
- Iterator invalidation: a silent memory bug
- Short task: pick and measure the right container for five jobs
Algorithms
- Non-modifying algorithms: find_if, all_of, count
- Modifying algorithms: transform, remove_if, erase
- Sorting: sort, stable_sort, partial_sort, nth_element
- Searching sorted ranges: lower_bound and equal_range
- Numeric algorithms: accumulate, reduce, iota
- Set and heap algorithms
- Short task: the most frequent errors in a log
Utilities
- pair, tuple and structured bindings
- Function objects, std::function and bind
- Timing with chrono and the random library
- Walking a file tree with std::filesystem
- Pattern matching with std::regex
- Short task: a folder size report
Capstone
- Capstone: a queryable asset inventory built on the STL
Practice labs
- Keeping recent commands in a deque: Write a history class with std::deque that keeps the last ten commands and drops the oldest when a new one arrives.
- Storing several appointments per day: Store Lavinya Klinikleri's appointments by day in a multimap and return all appointments of a day in time order using equal_range.
- Choosing and measuring the right container for five jobs: Measure vector, list, deque, set and unordered_set on five access patterns, pick the fastest for each job and back the choice with timings.
- Processing support tickets by priority: Write a queue with priority_queue that pops tickets by priority and, on ties, by arrival order.
- Writing a hash function for a composite key: Write hash and equality functions for a key made of building and room number and measure that collisions in the unordered_map stay reasonable.
- Resolving job dependencies with a stack and a queue: Parse nested job groups with a stack, order ready jobs with a queue and give a clear error on a circular dependency.
- Filtering with the erase-remove idiom: Write a function that removes expired sessions from a vector in one pass with erase and remove_if.
- Finding a reference invalidated by a growing vector: Find the code that uses a reference to an old element after push_back, fix it with an index or reserve and pass the ASan test.
- Curing a crash when erasing from a map while iterating: Repair a cache clean-up loop that advances an invalid iterator by using the return value of erase and pass the tests with random removal patterns.
- Checking records with all_of and any_of: Write functions that check with all_of, any_of and find_if that all order amounts are positive and whether any refund exists.
- Finding a percentile of response times: Find the ninety-fifth percentile with nth_element without a full sort and the ten slowest requests with partial_sort.
- Looking up price bands in a sorted range: Fix a lower_bound and equal_range use that returns the wrong band for some prices because of a bad comparator and pass the boundary tests.
- Computing a basket total with accumulate: Compute the total and the most expensive item of a basket of product structs with accumulate and max_element.
- Diffing two access lists: Produce added, removed and common users from two sorted user lists with set_difference and set_intersection.
- Keeping the top K values of a stream: Keep the K largest of millions of readings in constant memory with push_heap and pop_heap and show with random tests the result equals a full sort.
- Returning several values with structured bindings: Write a function returning minimum, maximum and average as a tuple and unpack it at the call site with structured bindings.
- Producing a folder size report: Walk a tree with std::filesystem, compute each subfolder's total size and report while skipping and counting inaccessible entries.
- Extracting log fields with regex and timing it: Extract time and level fields from log lines with std::regex, measure with chrono and meet the time target by fixing the pattern that is recompiled per line.
About this course
You use STL containers knowing when to pick which, and write safe, fast code with algorithms and utility libraries instead of hand-written loops.
What you will learn
- Containers in depth
- Algorithms
- Utilities
- Capstone
Prerequisites
Finishing the level 101 courses of the same path, or knowing those topics, is enough.
Lab environment
Lessons run in your own Kali Linux terminal that opens in the browser. Nothing to install; the lab starts clean in every lesson.
Frequently asked questions
- Is this course right for my level?
- The course is at level 201; it assumes you know the topics of the lower-level courses.
- Is there anything to install?
- No. Every lesson runs in your own lab environment that opens in the browser.
- How do lessons work?
- Each lesson has 8 to 10 steps and a short quiz. Early steps show the command to type, later steps give less help; if two attempts fail, the solution opens.
- Can I try it for free?
- Yes. The first three lessons of every course are free.