## Chapter 23 - The Standard Template Library - Containers

## Chapter Goals

- To understand the purpose and use of the containers in the Standard Template Library

- The fundamental sequential containers - vector, list, deque
- The adapter containers - stack, queue, and priority queue
- The ordered container - set
- The associative container - map

## 23.1 The Standard Template Library (STL)

- Library of collection classes and associated functions
- Found in most nontrivial applications
- Simplifies creation of new applications
- Promote reliability and portability
- Containers represented by class templates w/small interfaces
- Functionality extended by generic algorithms, used w/many types of containers

## 23.1.1 STL Container Categories

3 categories of containers:

1. Fundamental (or sequential)
   - vector, list, deque (pronounced "deck")
2. Adapters
   - Layered on top of the fundamental containers
   - stack, queue, priority queue
3. Associative
   - set, map

## 23.2 The Fundamental Containers

- Overlap of operations among these containers (see table, next slide)
- The 3 containers often interchangeable:

  >     vector<int>::iterator current
  >        = a_container.begin();
  >     while (current != a_container.end())
  >     {
  >        // Number is even if remainder is
  >        // zero after division by two
  >        if (0 == *current % 2)
  >           current = a_container.erase(current);
  >        else
  >           ++current;
  >     }

## 23.2 The Fundamental Containers (cont.)

Operation | Vector | List | Queue
--- | --- | --- | ---
`container()` | O(1) | O(1) | O(1)
`container(size)` | O(1) | O(n) | O(1)
`container(size, value)` | O(n) | O(n) | O(n)
`at(int)` | O(1) |  | O(1)
`back()` | O(1) | O(1) | O(1)
`begin()` | O(1) | O(1) | O(1)
`capacity()` | O(1) |  |
`clear()` | O(1) | O(1) | O(1)
`empty()` | O(1) | O(1) | O(1)

## 23.2 The Fundamental Containers (cont.)

Operation | Vector | List | Queue
--- | --- | --- | ---
`end()` | O(1) | O(1) | O(1)
`erase(iterator)` | O(n) | O(1) | O(n)
`erase(iterator, iterator)` | O(n) | O(1) | O(n)
`front()` | O(1) | O(1) | O(1)
`insert( iterator, value)` | O(n) | O(1) | O(n)
`pop_back()` | O(1) | O(1) | O(1)
`pop_front()` |  | O(1) | O(1)
`push_back(value)` | O(1)+ | O(1) | O(1)+
`push_front(value)` |  | O(1) | O(1)+

## 23.2 The Fundamental Containers (cont.)

Operation | Vector | List | Queue
--- | --- | --- | ---
`rbegin()` | O(1) | O(1) | O(1)
`rend()` | O(1) | O(1) | O(1)
`resize()` | O(n) |  | O(n)
`size()` | O(1) | O(1) | O(1)
`operator[]()` | O(1) |  | O(1)
`operator=(container)` | O(n) | O(n) | O(n)

O(1)+ - means amortized constant time

## 23.2 The Fundamental Containers (cont.)

C'tors
  Default creates an empty container
  Integer arg. creates container with size elements, initialized to default value
  - 2nd form allows explicit initialization. Same for all elements
  Can be initialized with another collection
`at`
  checks for index validity, unlike `operator[]`
`front`, `back`
  return the first and last elements
`empty`
  returns `true` if container has no elements

## 23.2 The Fundamental Containers (cont.)

`erase`
  removes specified element(s), returns iterator to next element
`insert`
  inserts element prior to the iterator
`push_front`, `push_back`
  insert values at the front and back
`pop_front`, `pop_back`
  remove them
`rbegin`, `rend`
  return `reverse_iterator`s

## 23.2 The Fundamental Containers (cont.)

- Generic algorithms extend classes (next chapter)
- Similar, not identical, behavior
- Not all operations are supported in all containers
- Common operations may have different complexity (see chptr. 15)
- To choose an appropriate container:
  - Which operations are req'd?
  - How often each operation will be performed (relatively)?

## 23.2.1 Vectors

- Indexed container
- Declared in `<vector>`
- Subscripting (`operator[]`) is the fundamental operation
- `push_back` - adds elements at back (resizing as needed)
- E.g., the Sieve of Eratosthenes, to discover prime numbers (ex. P16.15)
  - Start w/a vector of `bool`s, initialized to `true`
  - Increasing from 2, for each that is still `true`, strike out all multiples of that number

## 23.2.1 Vectors - Sieve of Eratosthenes

## Advanced Topic 23.1

Implementation of Vector

- Built on an array, allocated from the heap
- Store a pointer, the size and the capacity
- Usually larger than needed
- When needed `vector` will
  - get a new buffer, at least double the previous size
  - copy elements over
- `push_front` and `pop_front` would be O(n) tasks, so, not implemented

## 23.2.2 Lists

- Declared in `<list>`
- Implemented as linked lists (see chptr. 16)
- Not indexed
- Allows O(1) insertion/removal from front and back
- Supports insertion into the middle via iterators
- The only container of the three that does it in constant time

## 23.2.2 Lists (cont.)

Operations unique to `list`:

Operation | Description
--- | ---
`merge(list)` | Merge the current (sorted) list with the (sorted) argument list
`remove(value)` | Remove all instances of the given value
`remove(pred)` | Remove values for which pred returns true
`reverse()` | Reverse order of elements
`sort()` | Place the values into sorted order
`sort(comp)` | Place values in order using `comp`
`splice(iter, list)` | Splices argument list into the list at given location
`unique()` | Remove duplicate copies of values from sorted list
`unique(pred)` | Remove duplicate values from list sorted w/pred

## 23.2.2 Lists - Example

Simple inventory mgt. system; products have unique IDs. Tasks:
- Process an order for a product #
- Process the shipment of a given product.

## 23.2.2 Lists - Example

## 23.2.3 Deque

- double-ended queue
- Indexed, like vector
- Provides O(1) insertions at front or back
- O(n) insertion at middle
- W/out link fields, takes up less room than a list

## 23.2.3 Deque - Example

Example: time-driven simulation of the line in front of a tellers' counter at a bank.

- Each minute there's a .9 probability that a new customer arrives
  - Add to the end of customer deque
- Each transaction takes from 2-8 minutes (random)
- Calculate the avg. time a customer stands in line
- Each minute, examine and update the status of every teller in the teller deque, working off the front of the customer deque

## 23.2.3 Deque - Example

## Advanced Topic 23.3

Implementation of Deque

- Not specified by the standard
- circular buffer commonly used
- Like vector, but also store the start index
- Can insert/remove from the front w/out moving all of the other elements

## 23.3 The Stack and Queue Adapters

- Linear data structures that support LIFO or FIFO access (sect. 16.3)
- Not actually containers, but adapters (wrappers) built on containers
- Found in `<stack>` and `<queue>`
- Adapter: a class that uses another container to maintain elements, but changes the interface
- Operations for the adapter are ultimately passed to the underlying class
- Slightly simplified implementation of `stack` (next slide)

## 23.3 (cont.) - `stack` implementation

>     template <class T, class C = deque<T> >
>     class stack
>     {
>     public:
>        int size() const;
>        void push(const T& x);
>        T& top();
>        void pop();
>     protected:
>        C values;
>     };

## 23.3 (cont.) - `stack` implementation

>     template <typename T, typename C>
>     int stack<T, C>::size() const
>     {
>        return values.size();
>     }

>     template <typename T, typename C>
>     void stack<T, C>::push(const T& x)
>     {
>        values.push_back(x);
>     }

## 23.3 `stack` implementation (cont.)

>     template <typename T, typename C>
>     T& stack<T, C>::top()
>     {
>        return values.back();
>     }

>     template <typename T, typename C>
>     void stack<T, C>::pop()
>     {
>        values.pop_back();
>     }

## 23.3 `stack` implementation (cont.)

- `values` attribute is the actual container
- `stack` takes two type arguments
- The 2nd argument is the type of the underlying container
- The default value depends on the first argument
- The default container for both `stack` and `queue` is a `deque`
- For `stack` it can also be `vector`
- A `queue` can also be built on a `list`

## 23.3 (cont.) - `stack` Example

Reverse Polish Notation (RPN, or postfix) calculator

- Arguments written before operators
  - `3 + 4 * 7` would be `3 4 7 * +`
- Calculation is easy:

- Each argument read is pushed onto a stack
- If a (binary) operator is read:
  - Pop top two values
  - Perform appropriate operation
  - Push result back onto stack
- Add 2 commands:
  1. `p` - print the top of the stack
  2. `q` - quit the program

## 23.3 (cont.) - `stack` Example

## 23.4 Sets

- optimized for fast insertion, removal, and testing
- Not linear. Often a balanced BST
- Finding an item takes O(log n) time
- Elements of a set are unique
  - `multiset` removes this restriction
- Declared in the `<set>` header file

## 23.4 Set Operations

Operation | Description
--- | ---
`set()` | Construct an empty set
`set(iterator, iterator)` | Construct a set from the given range of values
`begin()` | Return iterator for set
`count(value)` | Return number of instances of value
`empty()` | Return `true` if set is empty
`end()` | Return ending iterator for set
`erase(iterator)` | Erase position from set

## 23.4 Set Operations (cont.)

Operation | Description
--- | ---
`erase(value)` | Erase value from set
`find()` | Return iterator for value
`insert(value)` | Insert value into set
`rbegin()` | Return iterator for values in reverse order
`rend()` | Return ending iterator for values in reverse order
`size()` | Return number of elements in set

## 23.4 Sets (cont.)

- Elements are maintained in sequence (sorted order)
- Fast lookups
- Need to compare elements, unlike the fundamental containers
- Template parameters:

  >     template <typename T, typename CMP = less<T> >
  >     class set
  >     {
  >        . . .
  >     };

- Second argument is the trait that compares two elements
- The default value is the standard `less` function object (`operator<`)

## 23.4 Sets (cont.)

2 ways to form sets of a new object type. Using the `Employee` class for our example.

1. Override `operator<`, allowing the normal declaration:

   >     bool operator< (const Employee& a, const Employee& b)
   >     {
   >        return a.salary() < b.salary();
   >     }

   >     set<Employee> workers; // Will be sorted by salary

## 23.4 Sets (cont.)

2. Provide an explicit function object; name it as the second template argument

   >     class SortByName
   >     {
   >     public:
   >        bool operator() (const Employee& a, const Employee& b) const;
   >     };

   >     bool SortByName::operator(const Employee& a, const Employee& b)
   >     {
   >        return a.get_name() < b.get_name();
   >     }

   >     set<Employee, SortByName> workers; // Now sorted by name

## 23.4 Sets - Dictionary Example

Program to check for misspelled words. A dictionary is read into a set, then checks input words against the set.

>     void spellCheck(istream& dictionary, istream& text)
>     {
>        set<string> words;
>        string word;

>        // First put all words from dictionary into set.
>        while (dictionary >> word)
>           words.insert(word);

>        // Then read words from text
>        while (text >> word)
>           if (words.count(word) == 0)
>              cout << "Misspelled word " << word << "\n";
>     }

## 23.5 Maps

- Indexed data structure, similar to a vector or deque
- 2 important differences:
  1. The indices (keys) can be any ordered type
  2. Ordered data structure (like the set), based on the keys
- Keys could be floats, strings, or even employees
- Keys may be looked up quickly
- `map` demands unique keys
- `multimap` permits multiple entries indexed by the same key
- Found in `<map>`

## 23.5 Maps (cont.)

- Takes three template arguments:

  >     template <typename K, typename V, typename CMP = less<K> >
  >     class map
  >     {
  >        . . .
  >     };

  - `K` - key type
  - `V` - value type
  - `CMP` - comparison for keys, less than by default
- `operator<` must be defined on the key type, or provide a function object

## 23.5 Maps (cont.)

- Set that maintains a collection of `pair`s (chptr. 22)
- Insert key/value pairs
- Iterators return `pair`s:

  >     map<string, int> database;
  >     . . .
  >     map<string, int>::iterator current = database.begin();
  >     while (current != database.end())
  >     {
  >        pair<string, int> element = *current;
  >        cout << "key is " << element.first << " value is " <<
  >           element.second << "\n";
  >        ++current;
  >     }

## 23.5 Maps - Operations

Operation | Description
--- | ---
`map()` | Construct an empty map
`map(iter, iter)` | Initialize a new map from the given range of values
`begin()` | Return iterator
`count(key)` | Return number of entries with key (0 or 1)
`empty()` | Return `true` if collection is empty
`end()` | Return ending iterator
`erase(iter)` | Erase value at indicated location
`erase(iter, iter)` | Erase range of values

## 23.5 Maps - Operations (cont.)

Operation | Description
--- | ---
`find(key)` | Return iterator to value with key
`insert(elem)` | Insert elem, which must be a key/value `pair`
`lower_bound(key)` | Return iterator for first entry with key (`multimap` only)
`rbegin()` | Return iterator in reverse order
`rend()` | Return ending iterator in reverse order
`size()` | Number of elements in container
`upper_bound(key)` | Return iterator for past-the-end entry with key (`multimap` only)
`operator[key]` | Return value associated with key

## 23.5 Maps - Example

Consider a directory listing of telephone numbers.

- Use unique names as keys
- Numbers as elements
- `print_all` produces a (naturally) ordered listing
- `print_by_number` produces a reverse white pages. A multimap provides an ordering on the numbers (not unique)

## 23.5 Maps - Example (cont.)

## 23.5.1 Priority Queue

- Non-linear container
- Optimized to quickly locate the highest priority element
- Does not imply a sorting
- Elements must be comparable
- Note: queue is a misnomer; FIFO is not enforced
- Basic operations:
  - `push` - Insert a new element
  - `top` - Return element w/highest priority
  - `pop` - Remove element w/highest priority
  - `empty`, `size` - as usual
- Comparison operator can be specified (less than, by default)

## 23.5.1 Priority Queue (cont.)

- `priority_queue` is defined in `<queue>`
- An adapter, wrapping an indexed structure (usually `vector`)
- Implemented using a `heap` (`priority_queue` wraps `heap`, which wraps an indexed container)

## 23.5.1 Priority Queue - Example

- Discrete event-driven simulation - classic application
- Structured around events (actions) that occur at some fixed time
- Often an action will spawn new events
- The following 2 files are the basis for an event-driven simulation
- Each event will be represented by an instance of `Event`
- The `Event` records the time, the key for comparison
- The lower time has higher priority
- A pure virtual method represents the action of an event

## 23.5.1 Priority Queue (`event.h`)

## 23.5.1 Priority Queue - Example

- Event loop - the heart of the simulation
- It pulls the next event (smallest time) from the PQ
- Events are removed in sequence, regardless of insertion
- As each event is removed it is executed, and the memory recovered
- The loop runs until the the queue is exhausted

## 23.5.1 Priority Queue (`event.cpp`)

## 23.5.1 Priority Queue - Example

- Subclass `Simulation` and `Event` to emulate traffic at a hot dog stand
- Vary the number of seats, see the outcome
- There are two types of events:
  1. Arrival event - signals the arrival of a customer. If seated, (s)he stays a random amount of time, the leaves
  2. Leave event - frees the seat the customer was occupying
- Random arrival events are generated over an hour to initialize the simulation

## 23.5.1 Priority Queue (`hotdog.cpp`)

## 23.6 Case Study: Dijkstra's Shortest Path Algorithm

- Find the shortest distance from a node on a directed graph to each other node
- A sample of routes to cities serviced by a bus company:

## 23.6 Case Study: Graph Representation

- Determine the minimum cost to travel from one city, e.g., Pierre, to each of the other cities
- Represent a destination, and the associated cost
- Could use a `pair`
- Need to override comparison operator
- Create a new class:

## 23.6 Case Study: Graph Representation

>     class DistanceToCity
>     {
>     public:
>        DistanceToCity(string n, int d);
>        string name;
>        int distance;
>        bool operator<(const DistanceToCity& right) const;
>     };

## 23.6 Case Study: Graph Representation (cont.)

>     DistanceToCity::DistanceToCity(string n, int d)
>     {
>        name = n;
>        distance = d;
>     }

>     bool DistanceToCity::operator<(const DistanceToCity& right) const
>     {
>        return right.distance < distance;
>     }

## 23.6 Case Study: Graph Representation (cont.)

- Represent graph using type of map
- City name is the key, a `DistanceToCity` is the element
- `cities` is a multimap; more than one edge may leave a city

  > `multimap<string, DistanceToCity> CityMap;`

  (Adjacency list)
- `DistanceFinder` wraps the multimap, provides 2 member functions:
  - `set_distance` adds an edge to the graph
  - `find_distance` fills in a map of destinations and their costs, given a source node

## 23.6 Case Study: Dijkstra's Algorithm

- A (min) PQ is used to represent the list of possible destinations with the relative cost of traveling to them
- Build a resultant map `shortest` of names and distances
- Place the source on the queue, w/distance 0
- Loop while the PQ is not empty:
  1. Pop element
  2. If city already visited (in `shortest`), goto 1
  3. Place city and cost in `shortest`
  4. For each adjacent node in `cities` (loop from `lower_bound` to `upper_bound`:
     - Add current distance to relative distance, add new entry to PQ

## 23.6 Case Study: Dijkstra's Shortest Path Algorithm (`dijkstra.cpp`)

## Chapter Summary

1. STL - a library of classes that represent containers that occur frequently in computer programs in all application areas.
2. Each class in the STL supports a relatively small set of operations. Basic functionality is extended through the use of generic algorithms.
3. The 3 fundamental data structures are the vector, list, and deque.
4. Vector and deque are indexed data structures; they support efficient access to each element based on an integer key.
5. A list supports efficient insertion into or removal from the middle of a collection. Lists can also be merged with other lists.

## Chapter Summary (cont.)

6. Stacks, queue, and priority queues are adapters built on top of the fundamental collections. A stack enforces the LIFO protocol, while the queue uses FIFO.
7. A set maintains elements in order. Permits very efficient insertion, removal, and testing of elements.
8. A map is a keyed container. Entries in a map are accessed through a key, which can be any ordered data type. Associated with each key is a value. A multimap allows more than one value to be associated with a key.
9. A priority queue is a collection organised so as to permit fast access to and removal of the largest element.