Chapter Overview

In this chapter, we will focus on the container classes in the STL. In short, a container is an object that contains a collection of other objects, or elements. The STL provides a complete suite of container types that form the foundation of the STL itself.

A quick overview of the STL container types

The STL provides a comprehensive set of container types, including sequential containers, associative containers, and container adapters. Here's a brief overview:

Sequential containers

The sequential containers provide an interface where the elements are arranged in sequence. While we may use the elements sequentially, some of these containers use contiguous storage, and others do not. The STL includes these sequential containers:

• The array is a fixed-size sequence that holds a specific number of elements in contiguous storage. Once allocated, it cannot change size. This is the simplest and fastest contiguous storage container.

• The vector is like an array that can shrink and grow. Its elements are stored contiguously, so changing size may involve the expense of allocating memory and moving data. A vector may keep extra space in reserve to mitigate that cost. Inserting and deleting elements from anywhere other than the back of a vector will trigger realignment of the elements to maintain contiguous storage.

• The list is a doubly-linked list structure that allows elements to be inserted and deleted in constant $O(1)$ time. Traversing the list happens in linear $O(n)$ time. A single-linked variant is available as forward_list, which only iterates forward. A forward_list uses less space and is somewhat more efficient than a doubly-linked list, but lacks some capability.

• The deque (commonly pronounced, deck) is a double-ended queue. It's a sequential container that can be expanded or contracted on both ends. A deque allows random access to its elements, much like a vector, but does not guarantee contiguous storage.

Associative containers

An associative container associates a key with each element. Elements are referenced by their key, rather than their position in the container. STL associative containers include these containers:

• The set is an associative container where each element is also its own key. Elements are ordered, usually by some sort of binary tree. Elements in a set are immutable and cannot be modified, but they can be inserted and removed. Elements in a set are unique, duplicates are not allowed. A set iterates in order according to its sorting operators.

• The multiset is like a set with non-unique keys, where duplicates are allowed.

• The unordered_set is like a set that does not iterate in order. Elements are not sorted in any specific order, but are organized according to their hash values for fast access.

• The unordered_multiset is like an unordered_set with non-unique keys, where duplicates are allowed.

• The map is an associative container for key/value pairs, where each key is mapped to a specific value (or payload). The types of the key and value may be different. Keys are unique but values are not. A map iterates in order of its keys, according to its sorting operators.

• The multimap is like a map with non-unique keys, where duplicate keys are allowed.

• The unordered_map is like a map that does not iterate in order.

• The unordered_multimap is like an unordered_map with non-unique keys, where duplicates are allowed.

Container adapters

A container adapter is a class which encapsulates an underlying container. The container class provides a specific set of member functions to access the underlying container elements. The STL provides these container adapters:

• The stack provides a LIFO (last-in, first-out) interface where elements may be added and extracted from only one end of the container. The underlying container may be one of vector, deque, or list. If no underlying container is specified, the default is deque.

• The queue provides a FIFO (first-in, first-out) interface where elements may be added at one end of the container and extracted from the other end. The underlying container may be one of deque or list. If no underlying container is specified, the default is deque.

• The priority_queue keeps the greatest value element at the top, according to a strict weak ordering. It provides a constant time lookup of the greatest value element, at the expense of logarithmic time insertion and extraction. The underlying container may be one of vector or deque. If no underlying container is specified, the default is vector.

In this chapter we will cover the following recipes: