Study your flashcards anywhere!

Download the official Cram app for free >

  • Shuffle
    Toggle On
    Toggle Off
  • Alphabetize
    Toggle On
    Toggle Off
  • Front First
    Toggle On
    Toggle Off
  • Both Sides
    Toggle On
    Toggle Off
  • Read
    Toggle On
    Toggle Off
Reading...
Front

How to study your flashcards.

Right/Left arrow keys: Navigate between flashcards.right arrow keyleft arrow key

Up/Down arrow keys: Flip the card between the front and back.down keyup key

H key: Show hint (3rd side).h key

A key: Read text to speech.a key

image

Play button

image

Play button

image

Progress

1/19

Click to flip

19 Cards in this Set

  • Front
  • Back
design principles that apply across a variety of software applications.
patterns
transforms one class into a different class without changing the
underlying class, merely by adding a new interface. (The new interface replaces the old
interface of the underlying class.) For example, in Chapter 19 we mentioned that the
stack
and
queue
template classes of the STL were adapter classes. We described both
the
stack
and
queue
interfaces and said you could choose the underlying class that
would actually store the data. For example, you can have a stack of
int
s with an
underlying vector,
stack<
vector<int>
>
, or a stack of
int
s with an underlying list,
stack<
list<int>
>
(or a stack with some other underlying container class, but two is
enough for our point). In either case, list or vector, the underlying class is not changed.
Only an interface is added.
How might the interface be added? That is an implementation detail that need not
be part of the Adapter pattern. There are, however, at least two obvious ways to do it.
For example, for a stack adapter the underlying container class could be a member
variable of the
stack
class, or the
stack
class could be a derived class of the underlying
container class.
The Adapter
pattern
a way of dividing the I/O task of an application
from the rest of the application. The Model part of the pattern performs the heart of
the application. The View part is the output part; it displays a picture of the Model’s
state. The Controller is the input part; it relays commands from the user to the Model.
Model-View-Controller
pattern
One big task is divided into three smaller tasks with well-defined
responsibilities.
The Model-View-Controller pattern is an example of a divide-andconquer
strategy:
is particularly
well suited to GUI (graphical user interface) design projects, where the View
can indeed be a visualization of the state of the Model.
Model-View-Controller pattern
the Model might be an object
to represent your list of computer desktop object names. The View could then be a
GUI object that produces a screen display of your desktop icons. The Controller relays
commands to the Model (which is a desktop object) to add or delete names. The
Model object notifies the View object when the screen needs to be updated.
Model-View-Controller pattern
an example in which the definition of split is very simple. It divides
the array into two intervals with no rearranging of elements. The join function is more complicated. After the
two subintervals are sorted, it merges the two sorted subintervals, copying elements from the array to a temporary
array. The merging starts by comparing the smallest elements in each smaller sorted interval. The smaller of
these two elements is the smallest of all the elements in either subinterval, and so it is moved to the first position
in the temporary array. The process is then repeated with the remaining elements in the two smaller sorted intervals
to find the next smallest element, and so forth.
merge sort
the definition of split is quite sophisticated. An arbitrary value in the array is
chosen; this value is called the splitting value. In our realization we chose a[begin], as the splitting value, but
any value will do equally well. The elements in the array are rearranged so that all those elements that are less
than or equal to the splitting value are at the front of the array and all the values that are greater than the splitting
value are at the other end of the array; the splitting value is placed so that it divides the entire array into
these smaller and larger elements. Note that the smaller elements are not sorted and the larger elements are not
sorted, but all the elements before the splitting value are smaller than any of the elements after the splitting
value. The smaller elements are sorted by a recursive call, the larger elements are sorted by another recursive
call, and then these two sorted segments are combined with the join function. In this case the join function is
as simple as it possibly could be: It does nothing. Since the sorted smaller elements all preceed the sorted larger
elements, the entire array is sorted.
quick-sort
divides the array
into two pieces, one with a single element and one with the rest of the array interval
(see Self-Test Exercise 2). Because of this uneven division, the ___ ___ has a worstcase,
and even average-case, running time that is O(N2). In practice, the ___ ___
is not a very fast sorting algorithm, although it does have the virtue of simplicity.
selection sort
Today’s candidate for a graphical representation formalism
Unified Modeling Language (UML)
The patterns discussed in this chapter are
Container-Iterator, Adapter, Model-
View-Controller, and Divide-and-Conquer Sorting patterns.
can give you a framework for comparing related algorithms for efficiency.
pattern
a graphical representation language for
object-oriented software design.
The Unified Modeling Language (UML)
is one formalism that can and is used to express patterns.
UML
1. Is a template function definition a pattern?
1. Yes, a template function definition is a pattern, but the term pattern is much more general
and encompasses more. Moreover, a useful pattern expressed as a template function
would leave some details unimplemented. If the only variation possible is a type parameter,
it is still a pattern but not likely to be usefully viewed as a pattern. (It can still be
useful as a template function, but it might not be useful to view it as a pattern in the
sense discussed in this chapter.)
2. Give the contents of a file named selectionsort.cpp that will realize the selection
sort algorithm (see Display 5.8) for the Divide-and-Conquer Sorting pattern given in
Display 20.2. (This is the selection sort analog of what was done for the quick sort in
Display 20.5.)
2. //File selectionsort.cpp: the selection sort realization
//of the Sorting pattern.
#include <algorithm>
using std::swap;
template <class T>
int indexOfSmallest(const T a[], int startIndex,
int sentinelIndex)
{
int min = a[startIndex],
indexOfMin = startIndex;
for (int index = startIndex + 1;
index < sentinelIndex; index++)
if (a[index] < min)
{
min = a[index];
indexOfMin = index;
//min is the smallest of a[startIndex]
//through a[index]
}
return indexOfMin;
}
template <class T>
int split(T a[], int begin, int end)
{
int index = indexOfSmallest(a, begin, end);
swap(a[begin], a[index]);
return (begin + 1);
}
template <class T>
void join(T a[], int begin, int splitPt, int end)
{
//Nothing to do.
}
3. Which of the following would give the fastest running time when an array is sorted
using the quick-sort algorithm: a fully sorted array, an array of random values, or an
array sorted from largest to smallest (that is, sorted backwards)? Assume that all arrays
are of the same size and have the same base type.
3. An array of random values would have the fastest running time, since it would divide the
array segments into approximately equal subarrays most of the time. The other two cases
would give approximately the same running time, which would be the worst-case O(N2)
running time because the algorithm would always divide an array segment into very
unequal pieces, one piece with only one element and one piece with the rest of the elements.
It is ironic but true that our version of the quick-sort algorithm has its worst
behavior on an already sorted array. There are variations on the quick-sort algorithm
that perform well on a sorted array. For example, choosing the middle element as the
splitting value will give good performance on an already sorted array. But whatever splitting
value you choose, there will always be a few cases with this worst-case running time.
4. Draw a class diagram for a class whose objects represent circles. Use Display 20.6
as a model.
pg. 891
5. Draw a class diagram for the IntNode class presented in Display 17.4.
pg. 891