CppCon 2019

Containers are at the heart of the Standard Library and are used in almost all non-trivial C++ programs, but a misunderstanding of the relationship between their algorithmic complexity and actual behavior can dramatically affect program performance. One of the most compelling advantages of C++ is that it allows programs to be precisely crafted so as to take full advantage of the hardware while still providing sophisticated high-level abstractions that represent the domain in elegant, expressive and natural ways. Knowing how to choose the correct container for each task and how to use that container most effectively is a vital part of that craft, and can have a profound impact on the behavior of a program.

From a user’s perspective many popular computer programs are no faster today than they were 30 years ago despite the enormous increase in measured performance of the hardware. I believe that this is due in part to a misconception that efficiency does not matter in most situations because processors are so fast and numerous, and memory is so large. This talk will proceed with the assumption that performance almost always matters, and so attention to efficiency is an essential aspect of good programming. We will examine the Standard Library containers and consider both the abstractions they are meant to express and the practical limitations they impose. We will then explore some containers that are not yet in the Standard Library which promise efficiency improvements in various situations. Finally we will look at a number of common cases and compare the naïve implementation with one that considers the actual behavior of containers on modern processors.