Chapter 26 - An Introduction to Design Patterns

Chapter Goals

To review the advantages of iterators
To learn about the pattern concept
To study several common design patterns: ITERATOR, ADAPTER, TEMPLATE METHOD, STRATEGY, COMPOSITE
To learn where patterns are used in the standard C++ library
To put patterns to work in a complex program

An Introduction to Design Patterns

A description of a problem and its solution
Can be applied to many situations
Useful patterns have been standardized
This chptr covers 5 common and easily understood patterns

26.1 Iterators

To traverse an STL linked-list:

list<string>::iterator pos;
for (pos = list.begin(); pos != list.end(); ++pos)
{
   string item = *pos;
   . . .
}

26.1 Iterators (cont.)

Compared to traditional traversal:

Node* current = list.head;
while (current != NULL)
{
   string item = current->data;
   current = current->next;
   . . .
}

26.1 Iterators (cont.)

Nodes are artifacts of a linked-lists
Consider circular lists, dummy head/tail nodes, etc.
Lists are easily corrupted
A list client should remain ignorant of nodes

26.1 Iterators (cont.)

Consider the interface:

A stack has:

push
pop
top

26.1 Iterators (cont.)

A array structure w/random access has:

operator[]
push_back
size

26.1 Iterators (cont.)

Interface for a linked list is more complicated

Adding/removing in the middle desired
Indices inefficient

Cursors (internal iterators) are one solution:

26.1 Iterators (cont.)

Interface for list w/cursor

T get() const // Get element at cursor
void set(const T& t) // Set element at cursor to t
T remove() // Remove element at cursor
void insert(const T& t) // Insert t before cursor
void reset() // Reset cursor to head
void next() // Advance cursor
bool is_done() // Check if cursor can be advanced

26.1 Iterators (cont.)

Cursors

Member of the list
Hides node details
reset moves cursor to beginning
next advances cursor
get, set, insert, and remove are relative to cursor

26.1 Iterators (cont.)

Cursors (cont.)

To traverse the list:

for (list.reset(); !list.is_done(); list.next())
{
   T item = list.get();
   . . .
}

26.1 Iterators (cont.)

Drawbacks of cursors

Only one
Can't implement algorithms to compare elements
Printing list moves cursor (is not const)

26.1 Iterators (cont.)

The iterator is a superior concept
Can have any number of iterators on a container
Consider uses outside of lists:
- istream - sequence of bytes
- Visit rows of a database
Examples of a common pattern

26.2 The Pattern Concept

Christopher Alexander formulated > 250 patterns for architectural design
Every pattern has:
- A short name
- A brief description of the context
- A lengthy description of the problem
- A prescription for a solution

26.2 The Pattern Concept

Patterns distill a design rule into a simple format
Provides cookbook for solutions
We apply the same principles to software design
We start with the ITERATOR pattern:

Pattern ITERATOR

Context

An object (aggregate) contains other objects (elements)
Clients need access
Aggregate should not expose its internals
Multiple clients may need simultaneous access

Pattern ITERATOR (cont.)

Solution

Define an iterator class
- External
- Fetches one element at a time
Each iterator object needs to keep track of the position of the next element to fetch

Pattern ITERATOR (cont.)

Solution

26.2 The Pattern Concept (cont.)

Names are simply examples

Consider the linked list iterators:

Name in Design Pattern	Actual Name (List Iterators)
`Aggregate`	`list<T>`
`Iterator`	`list<T>::iterator`
`create_iterator()`	`begin(), end()`
`next()`	`++` operator
`is_done`	Test against `end()`
`current_item()`	`*` operator

26.2 The Pattern Concept (cont.)

Input streams as example of iterator pattern:

Name in Design Pattern	Actual Name (Input Streams)
`Aggregate`	Source of Bytes
`Iterator`	`istream`
`create_iterator()`	`open()`
`next()`	`get()`
`is_done()`	`! fail()`
`current_item()`	Return value of `get()`

26.2 The Pattern Concept (cont.)

More abstract than an algorithm
Algorithm implements a computation
Pattern gives advice on solving a problem
See Design Patterns, Gamma, Helm, Johnson, & Vlissides

Advanced Topic 26.1

Generic Programming with Inheritance and Templates

Design Patterns further recommends using an abstract base class for the iterator and the aggregate

Generic code can then be written:

void print_all(AbstractAggregate* items)
{
   AbstractIterator* iter = items->create_iterator();
   while (!iter->is_done())
   {
      cout << iter->current_item() << "\n";
      iter->next();
   }
}

Advanced Topic 26.1 (cont.)

Very common in Java and Smalltalk, e.g.
C++ uses templates, not inheritance
Avoids cost of virtual functions

Similar functionality:

template<typename T>
void print_all(const T& items)
{
   T::iterator iter = items.begin();
   while (iter != items.end())
   {
      cout << *iter << "\n";
      iter++;
   }
}

26.3 The ADAPTER Pattern

When you want to use an existing class, but its i/f doesn't match the one you need
Consider converting a string containing numerics ("235") to an integer:
- string can't
- If digits were stored in a stream, great
- Hence, the istringstream class (chptr 12):
  string s = "235"; istringstream istr(s); int n; s >> n; // Now n is the integer 235

26.3 The ADAPTER Pattern (cont.)

The >> operator repeatedly calls get(), then assembles the integer
istringstream defines a get function to obtain the characters from a string, using string::operator[]
Example of the ADAPTER pattern

Pattern ADAPTER

Context

You want to use an existing class (adaptee) w/out modifying it
The context requires conformance to a target i/f, different from the adaptee's
Target i/f and adaptee i/f are conceptually related

Pattern ADAPTER (cont.)

Solution

Define an adapter class that implements the target i/f
Adapter class translates target functions to adaptee functions
The client wraps the adaptee into an adapter class object

Pattern ADAPTER (cont.)

Solution

26.3 The ADAPTER Pattern (cont.)

Name in Design Pattern	Actual Name (String Streams)
`Adaptee`	`string`
`Target`	`istream`
`Adapter`	`istringstream`
`Client`	Code that wants to use `operator>>` to read string
`target_function()`	`get()`
`adaptee_function`	`operator[]`

26.3 The ADAPTER Pattern (cont.)

Other ADAPTERS:

ostream_iterator wraps a stream with an iterator i/f:
copy( source.begin(), source.end(), ostream_iterator<string>( cout, "\n" ));
- Overload the * and = operators
- operator++ overloaded to do nothing

26.3 The ADAPTER Pattern (cont.)

Can be used to read from a stream:
copy( istream_iterator<string>(cin), istream_iterator<string>(), target.begin() );
- Default c'tor, istream_iterator<string>(), creates end-of-stream sentinel
- Overload the * and != operators

26.3 The ADAPTER Pattern (cont.)

Name in Design Pattern	Actual Name (String Streams)
`Adaptee`	`istream, ostream`
`Target`	`iterator`
`Adapter`	`istream_iterator, ostream_iterator`
`Client`	Code that wants to use a stream
`target_function()`	`<<, >>, fail()`
`adaptee_function`	The `*, =, +, !=` operators

26.4 The TEMPLATE METHOD Pattern

Pattern where an algorithm is mostly implemented in a base class, even when some details are unknown
Details supplied in virtual methods in derived classes
The base class template method tells how to fit in the details

26.4 The TEMPLATE METHOD Pattern (cont.)

Example - stream buffers

Each (buffered) stream has an associated stream
Characters sent to buffer
When buffer is full, contents are written to its target (file, screen, etc.)
More efficient
ofstream and ostringstream differ only by the attached buffers:
- ofstream has a filebuf object
- ostringstream has a stringbuf object

26.4 The TEMPLATE METHOD Pattern (cont.)

Example - stream buffers (cont.)

Consider an output operation:
cout << "Hello, World!\n";
The appropriate operator<< is invoked:

Converts each value into a sequence of characters
Inserts each character into a stream buffer

26.4 The TEMPLATE METHOD Pattern (cont.)

Example - stream buffers (cont.)

One possible implementation:

ostream& ostream::operator<<(const char s[])
{
   int i = 0;
   while (s[i] != '\0')
   {
      rdbuf()->sputc(s[i]); // returns a ptr to the buffer
      i++;
   }
   return *this;
}

26.4 The TEMPLATE METHOD Pattern (cont.)

Example - stream buffers (cont.)

Insert a character into the buffer:

int streambuf::sputc(char c)
{
   if (buffer full )
      return overflow(c);
   else
   {
      add c to the buffer
      return c;
   }
}

26.4 The TEMPLATE METHOD Pattern (cont.)

Example - stream buffers (cont.)

overflow writes the buffer content (and c) to its destination
overflow is a virtual method
Has a dummy implementation in streambuf, returns EOF
Derived classes redefine overflow
streambuf::sputc is not redefined

26.4 The TEMPLATE METHOD Pattern (cont.)

sputc is an example of the TEMPLATE METHOD Pattern

(Nothing to do w/C++ templates)

Base class defines an algorithm that calls primitive operations
Algorithm depends on derived class defining an appropriate operation
The template method combines primitive operations into a larger algorithm

Pattern TEMPLATE METHOD

Context

An algorithm is applicable for multiple types
Algorithm can be broken into primitive operations
The order of execution of the primitives doesn't depend on the type

Pattern TEMPLATE METHOD

Solution

Define the algorithm in the base class
The algorithm calls the primitive operations in order
Define the primitive operations as virtual functions in base class, with appropriate default behavior, or leave undefined
Each derived class defines the primitives, but not the algorithm

26.4 The TEMPLATE METHOD Pattern (cont.)

Name in Design Pattern	Actual Name (Stream Buffers)
`AbstractClass`	`streambuf`
`ConcreteClass`	`filebuf, stringbuf`
`template_method()`	`sputc`
`primitive_op1`	`overflow`

26.5 Function Objects and the STRATEGY Pattern

26.5.1 Function Objects

STRATEGY pattern shows how to supply a variety of algorithms to a computation

Motivation: the STL sort

E.g., sorting a vector of strings:
vector<string> names; . . . sort(names.begin(), names.end());

26.5.1 Function Objects (cont.)

sort works on any type that has operator<
Defined on strings, uses dictionary order
Consider sorting Employees:
vector<Employee> staff; sort(staff.begin(), staff.end());

To sort by name, supply:

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

26.5.1 Function Objects (cont.)

Sort by salary?
Redefine operator< for each sort order?
Sol'n: don't use the default operator<
SalaryComparator comp; sort(staff.begin(), staff.end(), comp);
(more concisely):
sort(staff.begin(), staff.end(), SalaryComparator());
Template function ptrs are messy, so we use a function object

26.5.1 Function Objects (cont.)

To sort by ascending salary:

class SalaryComparator
{
public:
   bool operator()(const Employee& a, const Employee& b)
   {
      return a.get_salary() < b.get_salary();
   }
};

No state
Its sole purpose is to execute a function

26.5.1 Function Objects (cont.)

Client is ignorant of sort implementation
Sort compares using:
```
if (!comp(x, y))
	 rearrange x and y;
```
comp is the object we passed in
comp(x, y) invokes SalaryComparator::operator()
Any sense of comparison is now possible

26.5.1 Function Objects (cont.)

Add attributes to extend functionality:

class SalaryComparator
{
public:
   SalaryComparator(bool a) : ascending(a) {}

   bool operator()(const Employee& a, const Employee& b)
   {
      if (ascending)
         return a.get_salary() < b.get_salary();
      else
         return a.get_salary() > b.get_salary();
   }

private:
   bool ascending;
}

26.5.1 Function Objects (cont.)

Use
SalaryComparator reverse_comp(false);
to sort by decreasing salary
When creating an unnamed object:
sort(staff.begin(), staff.end(), SalaryComparator() ):
Note the parenthesis after SalaryComparator
Creates an object using default c'tor
Must pass in an object, not a type

26.5.2 The STRATEGY Pattern

Comparator object provides a great deal of flexibility
This is an example of the STRATEGY pattern
Applies whenever you want to allow a client to supply an algorithm
Pattern places the essential steps in a strategy i/f
Vary algorithm by supplying different classes

Pattern STRATEGY

Context

A class (the context class) can benefit from variants on an algorithm
Clients of the context class can supply custom versions of the algorithm

Pattern STRATEGY

Solution

Define the strategy i/f, an abstraction for the algorithm
Concrete strategy classes implement the strategy i/f; each class defines a version of the algorithm
Client supplies a concrete strategy object to the context class
The context class calls the appropriate functions of the strategy object

26.5.2 The STRATEGY Pattern

Name in Design Pattern	Actual Name (String Streams)
`Context`	`sort` function
`Strategy`	The i/f that `sort` expects `comparator` to have, i.e., `operator()`
`ConcreteStrategy`	The `comparator` class
`do_work()`	The `operator()`

26.6 The COMPOSITE Pattern

Consider the invoice program (chptr 13)
Lists an item, quantity, and unit price
We'd like to add bundles of items

Sol'n: inherit Bundle from Item

class Bundle : public Item
{
   . . .
private:
   vector<Item*> items;
};

26.6 The COMPOSITE Pattern (cont.)

Example of the COMPOSITE pattern
Pimitive objects can be grouped into composite objects
Composites are primitives
E.g., in an HTML editor, elements can be grouped in a table, and the table is an element

26.6 The COMPOSITE Pattern (cont.)

Functions of the composite class must be applied to all primitives, then combine the results

E.g., compute the price of a bundle:

double Bundle::get_unit_price() const
{
   double price = 0;
   for (int i = 0; i < items.size(); i++)
   {
      price = price +
         ( items[i]->get_unit_price()
            * items[i]->get_quantity() );
   }
   return price;
}

Pattern COMPOSITE

Context

Primitive objects can be combined into composite objects
Clients treat a composite as a primitive

Pattern COMPOSITE

Solution

Define a class that is an abstraction for the primitive objects
Both primitive and composite classes inherit from that class
A composite object contains a collection of primitives
An operation on a composite class is applied to its primitives, results are combined

Pattern COMPOSITE

Solution (cont.)

26.6 The COMPOSITE Pattern (cont.)

Name in Design Pattern	Actual Name (String Streams)
`Primitive`	`Item`
`Composite`	`Bundle`
`op()`	`get_unit_price`

26.7 Case Study: Putting Patterns to Work

Refine the invoice printing program of Chptr 13
Include Bundle, from above
Make changes to employ several other patterns

26.7 Case Study: Putting Patterns to Work (cont.)

General Item abstract base class:

class Item
{
public:
   virtual double get_unit_price() const = 0;
   virtual int get_quantity() const = 0;
   virtual string get_description() const = 0;
   double get_total_price() const;
   . . .
};

26.7 Case Study: Putting Patterns to Work (cont.)

Derived classes implement the virtual functions

get_total_price is defined in the Item class:

double Item::get_total_price() const
{
   return get_quantity() * get_unit_price();
}

A generic item can't compute quantity or unit price, but it knows that the total price is their product - TEMPLATE METHOD pattern

26.7 Case Study: Putting Patterns to Work (cont.)

We want to add simple products to an invoice
Invoice stores Items, not Products
Use ADAPTER pattern, define ProductItem that wraps a Product in an Item i/f:

26.7 Case Study: Putting Patterns to Work (cont.)

class ProductItem : public Item
{
public:
   ProductItem(Product p);
   virtual double get_unit_price() const;
   virtual string get_description() const;
private:
   Product prod;
};

26.7 Case Study: Putting Patterns to Work (cont.)

Adapter methods call appropriate Product methods:

double ProductItem::get_unit_price() const
{
   return prod.get_price();
}

26.7 Case Study: Putting Patterns to Work (cont.)

Invoice holds a collection of items:

class Invoice
{
public:
   void add(Item* item)
   {
      items.push_back(item);
   }
   . . .
private:
   vector<Item*> items;
};

26.7 Case Study: Putting Patterns to Work (cont.)

Invoice clients my want to inspect the items
Invoice doesn't want to reveal its details - they may change
Sol'n - follow the ITERATOR pattern
Design an iterator class:

26.7 Case Study: Putting Patterns to Work (cont.)

class ItemIterator
{
public:
   . . .
   bool is_done() const;
   void next();
   Item* get() const;
private:
   vector<Item*>& items;
   int pos;
};

26.7 Case Study: Putting Patterns to Work (cont.)

These functions access a reference to the original vector:

Item* ItemIterator::get() const
{
   if (pos < items.size())
      return items[pos];
   else
      return NULL;
}

26.7 Case Study: Putting Patterns to Work (cont.)

inline void ItemIterator::next()
{
   pos++;
}

bool ItemIterator::is_done() const
{
   return pos >= items.size();
}

26.7 Case Study: Putting Patterns to Work (cont.)

Consider the current format of the invoice:

26.7 Case Study: Putting Patterns to Work (cont.)

Sufficient for all applications?
Printing a Web page? Need HTML tags
Need multiple algorithms for formatting
Use STRATEGY pattern
Design i/f to abstract out essential steps of the algorithm:
- Print header
- Print footer
- Print column entry (string or number)

26.7 Case Study: Putting Patterns to Work (cont.)

The i/f:

class InvoicePrinter
{
public:
   virtual void print_header(string s) = 0;
   virtual void print_string(string value, bool pad_right) = 0;
   virtual void print_number(double value, int precision) = 0;
   virtual void print_footer(string s, double total) = 0;
};

26.7 Case Study: Putting Patterns to Work (cont.)

Make the strategy object available to Invoice::print:

void Invoice::print(InvoiceFormatter& formatter)
{
   print_header("I N V O I C E");
   print_string("Description", true);
   print_string("Unit Price", false);
   print_string("Qty", false);
   print_string("Total Price", false);

   double amount_due = 0;
   for (ItemIterator iter = inv.create_iterator();
      !iter.is_done(); iter.next())
   {
      Item* it = iter.get();
      print_string(it->get_description(), true);
      print_number(it->get_unit_price(), 2);
      print_number(it->get_quantity(), 0);
      print_number(it->get_total_price(), 2);
      amount_due = amount_due + it->get_total_price();
   }

   print_footer("AMOUNT DUE:", amount_due);
}

26.7 Case Study: Putting Patterns to Work (cont.)

Relationships between classes for formatting:

26.7 Case Study: (`product.h`)

26.7 Case Study: (`item.h`)

26.7 Case Study: (`productitem.h`)

26.7 Case Study: (`bundle.h`)

26.7 Case Study: (`itemiterator.h`)

26.7 Case Study: (`invoiceprinter.h`)

26.7 Case Study: (`simpleinvoiceprinter.h`)

26.7 Case Study: (`invoice.h`)

26.7 Case Study: (`product.cpp`)

26.7 Case Study: (`item.cpp`)

26.7 Case Study: (`productitem.cpp`)

26.7 Case Study: (`bundle.cpp`)

26.7 Case Study: (`itemiterator.cpp`)

26.7 Case Study: (`simpleinvoiceprinter.cpp`)

26.7 Case Study: (`invoice.cpp`)

26.7 Case Study: (`invoicetest.cpp`)

More Patterns

Quick table of patterns from Design Patterns:

Pattern Name	Description	Example
Abstract Factory	An abstract class defines methods that construct related products. Concrete factories create these product sets	An abstract class specifies methods for constructing buttons, methods, and so on. Each user interface look and feel supplies a concrete subclass
Bridge	An abstraction and its implementation have separate inheritance hierarchies	A hierarchy of window types has separate implementations in various operating systems
Builder	A builder class has methods to build parts of a complex product, and to retrieve the completed product	A document builder has methods to build paragraphs, tables, and so on

More Patterns (cont.)

Pattern Name	Description	Example
Chain of Responsibility	A request is passed to the first handler in a chain. Each handler acts on the request (or chooses not to act), and passes the request on to the next handler	An event-handling mechanism passes a mouse or key event to a component, which then passes it to the parent component
Command	Commands are implemented as objects	A word processor stores recently issued commands so that they can be undone
Decorator	The behavior of a class is enhanced, keeping its interface	A user interface component is decorated with scroll bars or borders
Facade	A complex subsystem is accessed through a single class	A driver class provides access to the functionality of a database system

More Patterns (cont.)

Pattern Name	Description	Example
Factory Method	A virtual constructor can be redefined by derived classes	Collection classes that derive from a common base class redefine the create_iterator function
Flyweight	Uses shared objects instead of large numbers of separate objects with identical state	A word processor uses shared objects for styled characters rather than a separate object for each character
Interpreter	A class hierarchy represents grammar rules. The interpreter recursively evaluates a parse tree of rule objects	A program interactively evaluates mathematical expressions by building and evaluating a parse tree

More Patterns (cont.)

Pattern Name	Description	Example
Mediator	An object encapsulates the interaction of other objects	All components in a dialog box notify a mediator of state changes. The mediator updates affected components
Memento	An object yields an opaque snapshot of a part of its state, and can later return its state from that snapshot	An undo mechanism requests a memento from an object before mutating it. If the operation is undone, the memento is used to roll the object back to its old state
Observer	An object wants to be notified when another object generates an event	User interface components generate events, such as button clicks and text changes. A dialog box observes the events and repaints its contents

More Patterns (cont.)

Pattern Name	Description	Example
Proxy	A service needs to be made more versatile without affecting the service provider or client	A proxy class sends client requests to a server object on a different computer
Singleton	All clients need access to a single shared object of a class	A random number singleton gives all clients access to the same generator
State	A separate object is used for each state. State-dependent code is distributed over the various state classes	An image editor has different drawing states. Each state is handled by a separate tool object
Visitor	A structure with a fixed set of element classes needs an extensible set of operations	An XML visitor visits a tree of XML elements, applying arbitrary operations to each node

Chapter Summary

Iterators are preferred to cursors
A design pattern uses a standard format to give proven advice about a problem in software design
The ITERATOR pattern teaches how to access the elements of an aggregate object
The ADAPTER pattern teaches how to use a class in a context that requires a different interface
The STRATEGY pattern teaches how to supply variants of an algorithm to a client
The TEMPLATE METHOD pattern teaches how to supply varying behavior patterns to an algorithm
The COMPOSITE pattern teaches how to combine several objects into an object that has the same behavior as its parts
Design patterns apply in specific situations that are described by the context and solution parts of the pattern