# 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&#x20;
* Algorithms for manipulating the content of the containers.&#x20;

## Complexity&#x20;

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.&#x20;
  * 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.&#x20;
  * 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.&#x20;
  * 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.&#x20;

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&#x20;

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

These containers generally have **fast insertion times,** but relatively **slow `find` operations**.&#x20;

| 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.                                   |
| <p></p><p><code>std::list</code></p> | 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&#x20;

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&#x20;

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

| 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&#x20;

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.&#x20;

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&#x20;

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

#### Output Iterators&#x20;

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

### Advanced Iterators&#x20;

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

#### Forward Iterators&#x20;

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

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

#### Bidirectional Iterators&#x20;

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.&#x20;

#### Random Access Iterators&#x20;

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.&#x20;

This is typically used for arrays.

## STL Algorithms&#x20;

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&#x20;

## 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.  &#x20;

## Choosing the Right Container&#x20;
