Chapter 15 - Notes

The standard template library (STL) is a set of template classes and functions that contains:

• Containers for storing information (std::vector, std::set, set::map)

• Iterators for accessing the information stored

• Algorithms for manipulating the content of the containers.

Complexity

The term complexity refers to the performance of a particular action in the worst case. It can either refer to:

• Run-time complexity - how long does a particular action take to run

• Memory complexity - how much memory does a particular action use to run

Both are in proportion to the number of elements being operated on. In this chapter we will focus on run-time complexities.

• Constant complexity means that the performance of the container is unrelated to the number of elements contained by it.

  • e.g. the time to find an element in a container of 100 elements and 100,000 elements is the same

• Logarithmic complexity means that the performance is proportional to the logarithm of the number of elements contained in it.

  • e.g. the time to find an element in a container of 1,000 elements is twice as fast as a container with 1,000,000 elements

• Linear complexity means that the performance scales proportional to the number of elements.

  • e.g. the time to find an element in a container of 500 elements is twice as fast as a container with 1,000 elements

The complexities may be different for differing operations of a container. For example, the insertion complexity for a particular container may be constant, but search complexity may be linear.

Understanding these differences is key to knowing which is the right container to use for a given scenario.

Containers

Containers are STL classes that are used to store a collection of data.

There are two types types of container classes:

• Sequential containers

• Associative containers

Sequential Containers

These containers are used to hold data sequentially, such as arrays, vectors, or lists.

These containers generally have fast insertion times, but relatively slow find operations.

Container	Description
std::vector	Operates as a dynamic array that automatically resizes as you add elements to it. The elements are stored contiguously in memory.
std::deque	Similar to a vector, except that it allows fast insertion and removal of elements at the front.
std::list	Operates like a doubly link list, allowing for fast insertions and removals in the middle of the list.
std::forward_list	Similar to a std::list except that it is a singly linked, meaning you can iterate only in one direction.

Associative Containers

Associative containers store data in a sorted fashion, similar to a dictionary.

Container	Description
std::set	Stores unique values sorted on insertion with logarithmic complexity
std::unordered_set	Stores unsorted, unique values
std::map	Stores key-value pairs sorted by their unique keys with logarithmic complexity
std::unordered_map	Stores key-value pairs by their unique keys
std::multiset	Similar to a set, but supports multiple items having the same value.
std::unordered_multiset	Similar to unordered_set, but supports multiple items having the same value.

Container Adapters

Container adapters are variants of sequential or associative containers that have limited functionality intended for a specific use case:

Container	Description
std::stack	Stores elements in a last-in first-out (LIFO) fashion
std::queue	Stores elements in a first-in first-out (FIFO) fashion
std::priority_queue	Similar to a queue, except its elements are stored in a sorted order such that the one with the highest value is always at the front.

STL Iterators

The simplest example of an iterator is a pointer. Given a pointer to the first element in an array, you can increment to pointer to access the second element, and again to access the third element.

Iterators in STL are in a way a generalisation of pointers; they are template classes that give the programmer a handle that they can use to manipulate and perform operations on STL containers.

Since operations could as well by STL algorithms, which are also template functions, iterators are the bridge allowing these algorithm template functions to work seamlessly with the container template classes.

Basic Iterators

Input Iterators

Input iterators are ones that can be dereferences to reference an object in a collection. These iterators guarantee read access only.

Output Iterators

Output iterators allow the programmer to write to a collection. These iterators guarantee write access only.

Advanced Iterators

The two basic iterators types above are refined into advanced iterators, which you will find yourself using the most.

Forward Iterators

Forward iterators allow both input and output, but they may also be constant iterators that only read-only access.

These iterators can only be incremented; in other words, travel in one direction. This is typically used for singly-linked lists.

Bidirectional Iterators

This is similar to a forward iterators, except that it can be decremented to get to the previous element. This is typically used for doubly-linked lists.

Random Access Iterators

Similar to bidirectional iterators, except that it can be added or subtracted from to skip over multiple elements, or to find the relative separation or distance between two elements in a collection.

This is typically used for arrays.

STL Algorithms

The STL supplies some commonly used programming functions, such as finding, sorting, and reversing a container, in the <algorithm> header:

Algorithm	Description
std::find	Finds a value in a collection
std::find_if	Finds a value in a collection matching a specific criteria
std::reverse	Reverses a collection
std::remove_if	Removes all values from a collection matching a specific criteria
std::transform	Applies a specific transformation to all elements in a container

Example - Interaction between Containers and Algorithms Using Iterators

Use Automatic Type Deduction for Iterators

The type definition for iterators may be too terse for some. It is common to simply use auto for declaring iterators.

Choosing the Right Container