Modern STL Programming: Algorithms, Containers, Iterators
With the arrival of C++20 Ranges, it's more important than ever to have a solid grasp of classic C++ STL concepts: algorithms, containers, and iterators. We'll look at the technical considerations that went into the design of the Standard Template Library, and how those considerations have evolved in the two decades between C++98 and C++20.
After motivating the STL's core concepts of non-owning iterators and half-open ranges, we’ll cover the different kinds of iterators in the STL, and look at the mechanisms by which the STL distinguishes iterator capabilities and the kinds of optimizations that it can perform. We'll do a deep dive on comparator-based algorithms such as
partial_sort. We'll also cover library iterator types such as
ostream_iterator; and show the usefulness of classic utility types such as
std::reference_wrapper. Students will be asked to write and evaluate their own STL-style algorithms, and practice using
On Day 2, we'll cover the sequence containers and their various semantic guarantees, such as contiguity or iterator-stability. Then we'll cover the associative containers, including the unordered containers. We'll present best practices for using the standard containers with user-defined comparators and hashers. We'll also cover the "particular skills" of various containers, such as how
std::list::sort differs from
The course is bookended by units on two C++ library facilities that are maybe not "classic STL" but are critically important for any programmer:
string_view and the smart pointers.
The course is organized as lectures interleaved with six hands-on lab exercises. The lab exercises require a C++14-or-later compiler and either
Prerequisites Attendees should have basic to intermediate knowledge of C++11, including at least one year of programming experience. This course focuses on the library, not the language; it's assumed you will be able to keep up with offhand mentions of language concepts such as "class template," "rvalue reference," and "lambda." No special knowledge of C++14, C++17, or C++20 is required.
- string and string_view (+ short lab)
- iterators and the notion of an algorithm (+ lab)
- standard algorithms: sorting, heaps, comparators (+ lab)
- iterator adaptors and output iterators
- proxy types, std::ref, std::pair
- sequence containers, iterator invalidation (+ lab)
- associative and unordered containers (+ lab)
- upgrading to smart pointers (+ lab)
Arthur O'Dwyer is the author of "Mastering the C++17 STL" (Packt 2017) and of professional training courses such as "Intro to C++" and "The STL From Scratch." (Ask me about training your new hires!) Arthur is occasionally active on the C++ Standards Committee, and maintains a blog mostly about C++.