Data Structures
In order to solve problems, we need to work with data. At a basic level, this involves interacting with single values either on the stack or on the heap (and managing their lifetime). The next level is storing and interacting with many values of a given type. For this, the standard library provides several different containers with different characteristics. The basic container type is a vector, which stores values in contiguous (linear) memory and has very good traversal performance. Alternatively, one can use linked lists, which provide some flexibility for insertion and deletion at the cost of traversal performance. At the highest level, we have special-purpose containers such as sets and maps.
The goal of this chapter is to highlight some of the nuances of working with different kinds of data storage and high-level container classes so one can choose the most appropriate container for specific tasks and understand the performance implications of these choices...
