• 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

• 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

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

• 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;
  }

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

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_iterators

• 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)?

• 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 bools, initialized to true
  • Increasing from 2, for each that is still true, strike out all multiples of that number

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

• 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

Operations unique to list:

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

• 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

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

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

• 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)

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;
};

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);
}

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();
}

• 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

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

• 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

• 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<)

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

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

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";
}

• 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>

• 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

• Set that maintains a collection of pairs (chptr. 22)
• Insert key/value pairs
• Iterators return pairs:

  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;
  }

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)

• 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)

• 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)

• 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

• 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

• 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

• 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:

• 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:

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

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

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

• 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

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

Chapter Summary

Chapter Summary (cont.)