In this chapter we will learn about programming with arrays and pointers. In the Standard Template Library, arrays and pointers are one fundamental component, though they are unchanged from standard C++. Most of the major features of the STL are generalizations and abstractions based on features of arrays and pointers.

An *array* is a block of memory consisting of several items of the same
kind. These items are called components of the array. The components are
arranged sequentially, one after the other, in computer memory. The computer
will store the array with no wasted space in a single block of data. This
storage method is sometimes called *dense* or *contiguous* storage.
An array has a fixed number of components, defined at the time the array is
created.

Figure 2.1, an Array

There are two ways to define an array in C++. We are required to give the type of components of the array as well as its length in the definition. The easiest is to use a definition like the following, which defines an array of 12 doubles.

```
double monthlySalary[12];
```

`This definition actually defines two things, which are most often treated
as if there were only one. The first thing created is the array itself. If
doubles require 4 bytes of storage, then this array will require a single block
of 48 bytes. The second thing created is the address of this block. The
address of the block is also the address of the first component of the block.
The name monthlySalary actually has a value equal to this address. The
location of a component of an array is called a cell. The individual
cells of the array are named monthlySalary[0] through monthlySalary[11]. These
cells are variables like any other and can hold a value that can be changed.
monthlySalary itself is a constant, meaning that it will always refer to this
same block of data. Notice that the length of the array is 12, and, since we
start with a cell numbered 0, there is no cell numbered 12. `

`
`

`Figure 2.1, an Array with markings indicating cell numbers. `

`When used as a cell number, an integer is called a subscript. This
comes from mathematical usage that would probably write Ai, for the computer
scientist's A[i]. A subscript is also called an index. `

`A very common pattern of use of arrays is the following for loop, which
reads 12 doubles from the standard input and assigns them to the 12 components
of the array. `

`
`

```
for (int i = 0; i < 12; ++i)
cin << monthlySalary[i];
```

`Notice from the above, that subscript expressions may, in fact, be
variables. They may also be arbitrarily complex integer valued expressions.
C++ has no restrictions here. `

`The location of the block of data defined by the array definition is up to
the compiler to arrange. If an array definition appears at the global level or
is marked static, then the block will continue to exist as long as your program
continues to run. If the definition is local to a function or to an object,
then the array only exists while the function is running or the object exists.
Because the lifetime of the array is managed by the system, such data are often
called automatic. This applies to all data, not just to arrays.
`

`Be careful with array definitions. The following defines a single double
(called a scalar to distinguish it from an array) and an array.`

`
`

```
double thisMonth, monthlySalary[12];
```

`
`

`Suppose we are building a game program in which the player guesses integer
numbers. Suppose that the game needs to remember the guesses made by the
player in the order that they are made. One way to do this is to create an
array whose length is the maximum number of guesses allowed, together with an
auxiliary variable called an index. `

`
`

```
long guess[ 10 ];
int nextGuess = 0;
```

`Then, when a guess is made by the player we execute`

`
`

```
guess[ nextGuess ] = playerGuess;
nextGuess++;
```

`which first increments the index and then uses that value as a subscript
into the array to determine the component into which we save the player's
guess. We can, of course, combine these two statements into the single
one:`

`
`

```
guess[ nextGuess++ ] = playerGuess;
```

`Finally, we can process all of the guesses actually made with`

`
`

```
for(int i = 0; i < nextGuess; i++)
... guess[ i ] ...
```

`For automatic arrays the built in function sizeof will tell us the number
of bytes required by the array. We can apply sizeof to either a value, such as
a variable, or to a type. If we want the number of components, we can divide
the size of the array by the size of the component. `

`
`

`Often we want to create arrays in which the components are to be a user
defined type, especially a type defined by a class. There are special
requirements that enable this to be done. C++ requires a class used in this
way have a default constructor: a constructor with no parameters. Since all
classes should have such a constructor anyway, and since C++ will provide one
if you don't provide any constructors at all, this is a light requirement.
`

`Recall the CountedInt class from Chapter 1. This class has a default
constructor since we may call one of the constructors with no arguments. Now
we can fill an array with CountedInt values and look at what we have. `

```
void main()
{ CountedInt All [10];
// The default constructor is called for each cell.
for(int i = 0; i < 10; i++)
cout << All[i].getOrder() << endl;
}
```

**Exercise**. Test the above code. First anticipate what it will
produce. Are you correct?

`
`

`The second way to define an array actually splits the definitions of the
two parts (name and block) into two definitions. We may define a variable that
will be used to refer to an array of doubles with`

`
`

```
double* dailyCosts;
```

`Here, the variable dailyCosts is defined to be a pointer variable.
While pointers can be used in many ways in C++, one of the most important is to
make them "point to" arrays. Note that dailyCosts is a variable, not a
constant, and so it could hold different values at different times. The above
declaration does not give it any value however. It is useful to give every
variable some value and C++ provides a value named NULL for use in initializing
pointer variables. This is normally just the constant 0, but it guarantees the
pointer has a specific value that can be tested. A better definition of
dailyCosts would be`

`
`

```
double* dailyCosts = NULL;
```

`This both defines the variable, and initializes its value. This looks like
an assignment, but it is technically not. It is an initialization. `

`None of the above defines an array, just a variable that could be used to
refer to an array. We could actually define such a variable and make it point
to our monthlySalary array with:`

`
`

```
double* someSalary = monthlySalary;
```

`This assumes that monthlySalary was previously defined. This defines
someSalary as an alias of monthlySalary, and someSalary could be used just as
monthlySalary is used. An alias is a name that refers to the same thing,
usually a variable, as another name. Note that someSalary is a variable while
monthlySalary (as a name) is a constant. We could set the sixth monthly salary
using an assignment such as`

`
`

```
someSalary[5] = 1200.0; // Set the sixth monthly salary.
```

`However, since someSalary is a variable, it can be used to refer to any
array of doubles (or to any single double, for that matter). One way to make
someSalary refer to an array is to create the array at run time. The computer
reserves a large amount of storage in a structure called the free store
or heap which can be used to create things as the program runs. We
always refer to things in the free store with pointers, though pointers may
refer to locations elsewhere as well. We create things in the free store by
using the C++ operator new. Operator new creates variables that are called
dynamic. The lifetimes of dynamic values are determined by the
programmer, they are not automatic. `

` someSalary = new double[6];`

`creates a new array of 6 doubles on the free store and assigns a value to
someSalary which is the address of, or a pointer to, this block of data.
Having done this, someSalary[0] through someSalary[5] are defined and legal,
though the computing system will not be able to detect an expression like
someSalary[8] as an error. An important lesson to learn about arrays is that
the legality of subscript expressions is up to the programmer to guarantee.
The system provides little help here. `

`
`

`Figure 2.3. A pointer variable and the value it points to. `

`The C++ system does not guarantee a particular layout of memory, so the
following may not work exactly as shown, but some variant will. Suppose we
define two automatic arrays with`

`
`

```
long array1[5], array2[5];
```

`Then array1[9] might well refer to the same component as array2[4]. This
would be the case if array2 were laid out exactly after array1 in the memory.
`

**Exercise**. Try the above on your computer and report on what you
learn.

`We need to distinguish between the pointer variable that refers to an array
and the array itself. Given the above, someSalary is an automatic variable
that refers to a dynamic value. If someSalary were local to a function, then
its lifetime would end when the function returns. The array itself, however
continues to exist until the programmer deletes it using something like`

`
`

```
delete [] someSalary; // Delete an array.
```

`The delete operator is the inverse of new. It returns previously defined
free store values to the heap. Note that delete is used for other values
besides arrays. To use the above, however, we would need to write it in a
place where the name someSalary is defined. It is possible for a dynamic value
to outlive the variable used to create it. Consider the following`

`
`

```
double* getNewSalaries()
{ double* result = new double[12];
for(int i = 0; i < 12; ++i)
cin >> result[i];
return result;
}
```

`This function creates and returns an array. Notice that the variable
result is automatic and ceases to be at the end of this function. The array
itself, however is returned to the caller. Actually, the array itself isn't
returned. A pointer to it is returned. The array itself just continues to
exist in the free store. It is then the responsibility of the caller to see to
its eventual deletion. A function that returns a new dynamic value should
clearly say so in its documentation, since deletion of the value becomes a user
responsibility. `

`Automatic arrays in C++ may be initialized with constant values. Suppose,
for example that we need an array of strings, and we know the values of these
strings in advance. Then we may define and initialize the array at once with
something like:`

`
`

```
char* days[7] =
{"Sun", "Mon", "Tues" ,"Wed", "Thur", "Fri", "Sat"};
```

`Here days is an array of seven strings (char *). The system will create
the array defined by the initializer and make days a constant pointer to it.
We could write out the contents of this array with `

`
`

```
for(int i = 0; i< 7; ++i)
cout << days[i]<<endl;
```

`We cannot initialize dynamic arrays in the same way. The problem is that a
dynamic array must exist before we can give its components values, while an
initialization such as the above must exist before the pointer that is to refer
to it. In particular, the following will not work. `

`
`

```
long* values[5] = new double[5]; // Create a new dynamic array.
values = { 2, 3, 5, 7, 11 };
```

`At the end of this sequence, values will be pointing to a static array and
the dynamic array on the free store has no pointer pointing to it. It is a
lost block in the heap that cannot be recovered while the program runs. In
general, you should never follow a free store allocation by an assignment to
the same variable. Between such statements you should either delete the item
or create an alias, so that you always have at least one pointer to each free
store item. This is true of arrays as well as other things in the free store.
`

`If you define an array dynamically, the sizeof function won't tell you the
size of the array if you apply it to a pointer to the array. This is because
you are asking for the size of a pointer (often 4 bytes), not the sizeof the
array. Therefore, the sizeof(days) will probably be 4. If you ask for
sizeof(*days) you will likely get 1, the sizeof a char. The best way to know
the size of a dynamic block is to remember it when you allocate it. Save the
length you use in a variable. `

`
`

`If we have a pointer variable, we often need the thing that it points to.
The prefix operator * is called the dereferencing operator and it will give us
the value to which a pointer points. For example, in the above string example,
the array variable days is a pointer that points to the beginning of the array.
In other words it points to its first component (days[0]). Therefore *days and
days[0] may be used interchangeably. `

`One can also always create a pointer value. Suppose that we have a double
value salary. We can create a pointer to it with &salary. `

`
`

```
double salary = 4500.00;
double* aliasOfSalary = &salary;
```

`Now salary and *aliasOfSalary are variables that refer to the same entity,
namely the 4500.00. Thus the following will increase the salary by
2000.`

`
`

```
salary += 1000.00;
*aliasOfSalary += 1000.00;
```

`Thus & and * are inverse operators. One gives us an address from a
value and the other a value from an address. `

`We can apply the above to arrays and array components as well. `

`
`

```
double* sal = &monthlySalary[4];
```

`gives us in sal, the address of monthlySalary[4]. Notice that we are using
two operators in this expression, operator& and operator[]. The latter has
the highest precedence so this is the address of monthlySalary[4] not the fifth
component of &monthlySalary (which doesn't really exist since
&monthlySalary isn't an array). `

`Some arithmetic operators can be applied to pointers. In particular an
integer may be added to or subtracted from any pointer, and the difference
between two pointers (to the same type of thing) may be computed. The meaning
is illustrated in the following examples.`

`
`

```
long values [10] = { 10, 20, 30, 40, 50, 60, 70, 80, 90, 100 };
long* somewhere = values; // Points to the 10.
somewhere++; // Points to the 20.
cout << (*somewhere) + 2; // Prints 22.
cout << *(somewhere + 2); // Prints 40.
cout << *somewhere + 2; // Prints 22.
cout << *(somewhere + 22); // Prints garbage outside array.
cout << somewhere - values; // Prints 1; the number of
// componenents betweent the two values.
cout << *somewhere - *values; // Prints 10.
```

`Note that the addition operator has lower precedence than the dereferencing
operator. `

`We can generate a pointer to the cell immediately following our array
values with`

`
`

```
long * afterEnd = &values[10];
```

`It would not be safe to dereference this pointer, but we shall see that we
will eventually need this value in the STL. `

`If we have an array A, then A is a pointer and the expression & A[i] is
exactly the same as the expression A+i. In fact the pointer duality law
specifies the equivalence of these two expressions. Note that A+i does not
refer to a location i bytes past the beginning of A, but the location i
components after A. This will be true independent of the component type
of the array. `

`Using the pointer duality law implies that the following for loop will
process all of the elements of our array, values. `

`
`

```
for(long* p = values; p < afterEnd; ++p)
cout << *p;
```

`What can happen if you are not careful about your array subscripts and
equivalent pointer expressions? That depends on whether you are reading values
or writing them. If you are reading values from the "array" and your subscript
does not fall in legal bounds, then you will get a value, but the value will be
meaningless. The computer will interpret the values retrieved as if they had
the component type, but, of course, they may not. It is for this reason that
(a) you get garbage, and (b) it is hard to recognize as such, since it has the
correct form. `

`If you are attempting to place data into the array (write the array), then
the situation is much worse. If you write into a valid cell then you change
it, of course. If you write into an illegal cell, one outside the legal
bounds, then you change something. That location in the computer memory is
very probably being used for something else, and when the value of that item is
later retrieved, it will not have the last value that was correctly placed into
it, but some value placed by our incorrect reference. There is no guarantee
that the value written has the same type as the value read, but any sequence of
bits can be interpreted according to (nearly) any type, so the user of that
other data item will find a legal value, but the wrong value. `

`In the worst case, on some computers, you can do serious damage by making
illegal array references. For example, on many small computers, a technique
called memory-mapped I/O is used in which physical devices such as disks and
printers are installed in such a way that they look just like memory. They are
controlled by "writing" into their device control registers, which are just
memory locations. If an out-of-bounds array reference were to accidentally
write to a device register, that device would do something. Perhaps, if it
were a disk drive, it would erase that disk. This would be a very unhappy
event. `

`A few final words on pointer arithmetic. Notice that it is
bi-directional. You can subtract from a pointer just as you can add.
Therefore, continuing the above examples, afterEnd - 1 is a pointer to the last
cell of our array. `

`Actually, pointers are more than just bi-directional. They are actually
random access. This means that from a pointer to any cell in the array,
we can move immediately, in one step to any other cell. For example, suppose
that third is a pointer to the third cell of some array. Then third + 5 is
automatically a pointer to the eighth cell, if such exists. Using the pointer
duality law, if A[i] represents the third cell, then A[i+5] represents the
eighth. In either case we can move from any cell to any other, without
visiting the intervening, or any other, cells. `

`Finally, we may subtract two pointers into the same array. Thus, again
referring to the array values from above, afterEnd - values is the number of
components of the array; 10. Note again that it is not the number of bytes of
storage occupied by the array, indeed some computers are not even byte
oriented. Rather it is the number of cells between the two pointers. `

`
`

`In C++ multiple dimension arrays are not technically possible. It is,
however, possible to define arrays whose components are arrays, and this has
much the same effect. We can give an alternate definition of our days array
with:`

`
`

```
char days[7][5] =
{"Sun", "Mon", "Tues", "Wed", "Thur", "Fri", "Sat"};
```

`Here we have an array of 7 arrays, each of 5 characters. We describe the
array as "7 by 5" or as having 7 rows and 5 columns. We need the "inner"
arrays to hold 5 characters, since Thur has four letters plus the terminating
null character. The extra character is wasted in the other names, except Tues,
of course. In C++ we may have an arbitrary number of dimensions in this way,
but be careful since the size of the resulting structure is the product of the
sizes in the individual dimensions and the size of the ultimate component type,
here char. A large number of dimensions could result in a very large
structure, even if the length in each dimension is small. Sometimes an array
with two dimensions is called a matrix. `

`
`

`Figure 2.4, a Matrix with 7 rows and 5 columns`

`This new declaration of days defines a slightly different structure than
the original however. In this new definition it is clear that there are a few
wasted bytes, since each interior array is required to have five, though most
of the values stored require only four. In the original, this wasted space
will not be present. The former method of definition is somewhat more flexible
because it admits components of differing sizes. The first definition of days
defines an array whose components are pointers to characters. The second
defines one whose components are arrays of characters. Similar, but not quite
the same. Use sizeof to discover the difference. `

`Just as we can get access to the individual strings by indexing, we can
also get access to the individual characters, though we need to use double
indexing. `

`
`

```
days[ 2 ] [ 0 ]; // Refers to the T of Tues.
days[ 5 ] [ 2 ]; // Refers to the i of Fri.
days[ 4 ]; // Refers to the array containing Thur.
```

`One of the topics in artificial intelligence is machine learning. In this
section we present a simple game that learns from its mistakes. It is almost
too simple to be called artificial intelligence, but it is only intended to
introduce you to the concept and to show programming with arrays. `

`The French Military Game is played on a graph with 11 nodes, numbered 0 to
10. The game has two sides: the Police and the Fox. The Fox has only one
piece, that begins the game at cell 5. The police have 3 pieces, originally at
0, 1, and 3. The police move first and the players alternate. On a turn each
side may move one piece along one of the arcs. The object of the fox is to
reach cell 0. The police, who may only move vertically and to the right, has
the objective of trapping the fox against a sidewall, For example, if the fox
is at 6 and the police at 3, 5, and 9, then the police win. If the fox reaches
cell 0 then it wins. A game with over 20 moves is forfeited to the fox. (The
fox is a spy, trying to elude the police and reach its base.) Play the game a
few times with two human players to get a feel for it. Note that there is only
one side for the police, not three separate players. When "The Police" moves,
it may move only one piece. `

`
`

```
1--4--7
/|\ | /|\
/ | \|/ | \
0--2--5--8--10
\ | /|\ | /
\|/ | \|/
3--6--9
```

`In this computer simulation, the computer plays the fox. Initially the
computer plays randomly, with a bias toward moving left. However, the fox
learns from its mistakes and after only a few games it becomes nearly
impossible for the human player to win. `

`To represent this game board, we use a two dimensional array of integers.
`

`
`

```
0 2 2 2 0 0 0 0 0 0 0
1 0 2 0 2 2 0 0 0 0 0
1 2 0 2 0 2 0 0 0 0 0
1 0 2 0 0 2 2 0 0 0 0
0 1 0 0 0 2 0 2 0 0 0
0 1 1 1 2 0 2 2 2 2 0
0 0 0 1 0 2 0 0 0 2 0
0 0 0 0 1 1 0 0 2 0 2
0 0 0 0 0 1 0 2 0 2 2
0 0 0 0 0 1 1 0 2 0 2
0 0 0 0 0 0 0 1 1 1 0
```

`This is a definition of the board. It has 11 rows and 11 columns, one for
each cell in the graph. A zero at a row, column entry indicates there is no
arc from the row entry to the column entry. A non-zero entry indicates an arc,
hence a possible path for the fox. The police can't travel all arcs in all
directions, so a 2 is used to show a legal police move. The 2 on row 1 (the
second row, since they are numbered from 0) and column 2, indicates it is legal
for the police to move from cell 1 to cell 2. Such an array is called an
adjacency matrix, since it defines which cells in a graph are adjacent (have
arcs between them). `

`One can store this game board definition in a file of 121 integers. This
file is read in at the beginning of play and stored in a two dimensional array.
`

`The key to the learning aspect of this game is that there are only 165
legal positions for white. and 11 positions for black. During one play of the
game, the computer keeps a record (in an array) of all of the positions that
occur. `

`A single game is stored in a two dimensional array with 20 rows and 2
columns. Column 0 is used for a police position (a number from 0 to 164), and
the second column is used to store the fox position (a number from 0 to 10).
`

`At the end of the game it updates a 165 x 11 matrix of weights, increasing
all the weights of positions occupied if the computer won, and decreasing them
if it lost. When the computer tries to choose a move, it consults this table
and chooses one with the highest weight value. This means that the complete
results of all positions of all games played can be summarized in a rectangular
array of 165 by 11 integer entries. Finding a best move is just searching for
the maximum value in a portion of an array. Very simple.`

`The police position is translated into a number by computing 2 ^{a}
+ 2^{b} + 2^{c}, where a, b, and c are the cell numbers
occupied by the police. Since no two police pieces can occupy the same cell,
and since they are all less than 11, the maximum value of this is 2^{9}
+ 2^{8} + 2^{10} and no two positions result in the same value.
Only 165 different values actually occur (The number of ways to choose 3 items
from a set of 11 without replacement, in the language of combinatorics. 165 =
(11!) / (3!)(8!)) The 165 different values of this sum are all between 7 and
1792. These are stored in another array. We search this latter array for a
police position value and the cell number in which we find the result is used
as a row index into the memory array. `

`From this description you can try to build the game. `

`
`

`In the Standard Template Library there are several other data structures
that have components. These data structures are called, collectively,
containers. Each of them has some feature different from arrays. Vectors are
like arrays except that their length may be changed. Deques can grow also, but
at either end. Lists do not use dense, contiguous, storage. Sets don't have a
linear or sequential structure. There are several other container classes as
well. `

`Pointers are generalized in the STL to objects called iterators. An
iterator has the property that it refers to a specific location in a container,
and that this location may be moved by doing simple arithmetic operations. One
of the features of iterators in the STL is that they may be used with for loops
in a way completely analogous to the way we use pointers and for loops with
arrays. Some iterators, like pointers, are bi-directional. Some iterators,
like pointers are random access. Other iterators are more restricted, such as
forward iterators that can only move in one direction through their container.
Different kinds of containers support different kinds of iterators. `

`The algorithms provided by the Standard Template Library for the
manipulation of containers are all defined in terms of iterators. In other
words, to manipulate a container using one of these algorithms, we pass the
algorithm one or more iterators over that container. This philosophy that the
algorithms are defined in terms of the iterators, rather than the containers
themselves, makes it possible to write the algorithms in a very general way.
In particular, an algorithm that works for lists may well also work for sets or
for vectors. Finally, this philosophy makes it possible for these same
algorithms to work with the built in arrays of C++ as well as the components of
the STL proper. `

`
`

`When we save data in some container, we often want to retrieve the values
we have stored. The efficiency with which we can do this is greatly determined
by the ordering of the data within the container. Sorting is the problem of
putting a collection of data into some particular ordering or relationship.
Searching is the retrieval process itself. `

`
`

`One common problem that occurs in dealing with arrays is that of searching
for an element that may or may not be in the array. While loops are especially
helpful in this. Suppose we have an array A in which we are certain that a
value x occurs and we would like to know the cell number that it occurs in.
The following loop will tell us.`

`
`

```
int i = 0;
while(A[i] != x) i++;
```

`This loop exits as soon as A[i] == x and so we have the desired index. If
we are not certain whether x is in the array or not, however, we need to be a
bit more careful to avoid searching past the end of the array. The following
will serve, where we replace lengthOfA with the actual length of the array A.
`

`
`

```
int i = 0;
while (i < lengthOfA && A[i] != x) i++;
```

`The test for the length must be made first, so that we can guarantee that
an index used to retrieve a value (A[i]) represents a legal subscript. C++
will guarantee that if i >= lengthOfA the second test will not be evaluated
and the loop will exit. This is the advantage of short circuiting the
evaluation of Boolean expressions. The value is returned as soon as enough of
the expression is evaluated to make the answer clear. The same is true of the
OR operator; ||. Note that in this search, if the item is not present, the
value of i will be left at lengthOfA. This can be tested for. Remember that
when you write a loop with a compound exit condition such as here, that when it
exits, you don't know which condition caused the exit. Therefore an additional
test after the loop is often required. `

`A for loop can also be used in conjunction with the break statement.`

`
`

```
for (int i = 0; i < lengthOfA; ++i)
if ( A[ i ] == x ) break;
```

`this loop will also exit with either A[ i ] containing the desired value or
the index equal to lengthOfA. `

**Exercise**: Use the pointer duality law to change the above for loop
into an equivalent one that uses pointers instead of subscripts.

`The above process is called sequential search, since we look for the item
of interest sequentially, starting at the first component. If the array is
long, then this can take quite a while. It is possible to search faster if the
array is sorted as we shall see. `

`
`

`Next we attack the problem of putting an array in order, assuming that the
elements in the array are "sortable." To be sortable, means that the elements
of the component type must support operator<. This is certainly the case
for the built-in types of C++ and it may be true for user defined types since
it is possible for the programmer to give alternate definitions of operator<
for user defined data. `

`One of the simplest algorithms for sorting is called selection sort. The
idea behind selection sort is to remove the smallest element from the array,
then sort the remainder with the same process, and then to attach that
smallest element back to the beginning. The picture in Figure 2.1 should help.
`

`
`

`Figure 2.5, Selection Sort Outer Loop`

`This is intended to be a picture of the sort function in the middle of its
operation. The implication is that there is an index i, somewhere between 0
and length-1, and all cells strictly to the left of cell i have been sorted and
also contain the smallest values in the entire array. `

`Each array picture that we draw, called an array section, is
intended to represent the state of some array part way through an algorithm.
Usually they represent the state of some loop or recursion partly completed.
The above picture actually represents a for loop with control variable i in the
middle of its execution, as we shall see. When we put a value below the
rectangle representing the array we intend it to represent a subscript. When
it is inside the rectangle it represents a value. A vertical bar in the
rectangle separates the array into two parts that may have different
characteristics. If something is known about the elements in some section then
we write a description within the rectangle. The positioning of subscripts and
vertal lines is significant and in the above case the fact that the subscript i
is to the right of the vertical line indicates that the description "Sorted and
Smallest" applies only to subscripts 0 through i - 1. `

`Our job is to complete the process by getting i up to value length-1 so
that the part to the left will be the entire array except for one cell. Since
that part is sorted and since its values are no greater than the value in cell
i = length-1, then the entire array is sorted, which is our aim. The problem
then is how to get this figure true, keep it true, and get i up to
length-1.`

`First, it is easy to make this picture true. All we need to do is to set i
to be 0. Since there are no cells to the left of i = 0, it is certainly true
that it is sorted. Likewise nothing there is any larger than any thing in the
part from i through length-1, since there are no cells at all in that left
part. `

`The goal of getting i up to length - 1 can be achieved if we keep
increasing i as we progress. We will use a for loop to do this for us. The
part about keeping the picture in Figure 2.1 true is the challenging part, and
this is where the original idea comes in. `

`What we want to do is to find the smallest value in the part i...length-1
and move it to cell i. Then, when we increase i, the picture is still true.
Make sure that you understand why. `

`To handle this last part of the task it will be helpful to consider the
picture in Figure 2.2.`

`
`

`Figure 2.6. Selection Sort, Inner Loop.`

`The implication here is that we have a picture of the portion between i and
length-1. In this section we have an index j and an index s, and cell s
contains the smallest element in the section between i and j. If we can get
this true, keep this true, and get j up to length-1 we will have found the
smallest value in i...length-1. We can then swap cells i and s to achieve our
goal of getting the smallest value to cell i. We can make this true initially
just by setting s and j to be i and keeping an auxiliary value named small to
hold the smallest value discovered so far, the one in cell s. We can get j
increased with a for loop. We can keep the picture true just by setting s to
value j whenever we discover a smaller value at j as we move j along. This
leaves us with the following code for the selection sort. Note that the only
requirement we make on the type to be sorted is that it support operator<.
`

`
`

```
const int length = ...;
float elements[length];
...
void selectionSort()
{ for(int i = 0; i < length - 1; ++i)
{ int s = i;
float small = elements[s];
for(unsigned j = i + 1; j < length; ++j)
if(elements[j] < small) // operator< used.
{ s = j;
small = elements[s];
}
elements[s] = elements[i];
elements[i] = small;
}
}
```

`This is not a very good function, since it will only sort an array named
elements, and only if its length is named length and only if it contains
floats. We can do better. One way is to pass in the array to be sorted along
with the length, so the function sorts its parameter instead of a global value.
That would certainly be an improvement. In C++ this would look like the
following. `

`
`

```
void selectionSort(float elements[], int length)
{ for(int i = 0; i < length - 1; ++i)
{ int s = i;
float small = elements[s];
for(unsigned j = i + 1; j < length; ++j)
if(elements[j] < elements[s])
{ s = j;
small = elements[s];
}
elements[s] = elements[i];
elements[i] = small;
}
}
```

`This is much better, but we still can sort only floats. One way to improve
this further is to turn it into a function template . The result won't be a
function, but a means of creating functions as needed. `

`
`

```
template < class T >
void selectionSort(T elements[], int length)
{ for(int i = 0; i < length - 1; ++i)
{ int s = i;
T small = elements[s];
for(unsigned j = i + 1; j < length; ++j)
if(elements[j] < small)
{ s = j;
small = elements[s];
}
elements[s] = elements[i];
elements[i] = small;
}
}
```

`Note that here, both occurrences of the type float have been replaced by a
reference to the template parameter T. This parameter is a type. Later if we
need to sort an array of ints, then the system will use this function template,
with T equal to int, to create a sorting function for us. It will also be used
to create a different function that will sort floats if we need it. The
compiler sees to this creation (instantiation) of functions from the template
by examining which functions we make use of in our code. This instantiation of
template functions from function templates is automatic, but note that it
requires the system create different functions for different values of the
template parameter. `

`
`

```
int intArray[6] = {5, 4, 3, 6, 2, 1};
float floatArray[5] = {1.2, 3.4, 2.5, 0.4, 1.1};
selectionSort(intArray, 6);
selectionSort(floatArray, 5);
```

`One requirement that the writer of a function template must remember, is
that the template parameter must appear int the parameter list of the function
itself. This is the means that the compiler uses to determine which template
function to create. It is not enough to specialize the return type or the body
of the function. The template parameter must appear in the function parameter
list. `

`Another means of improving on our selection sort algorithm is to include it
as a member function in a class. Suppose we build a class Array to provide
additional support that C++ arrays do not have. For example our Array class
could provide bounds checking which C++ does not do for built-in arrays. This
class would actually be a class template rather than a class, with the element
type (component type) as the template parameter. If this were the case, and it
is attractive to do, then we might consider making selection sort one of the
member functions of this class. In this case, the array elements would be one
of the member variables of this class, implementing the class with a built-in
array. `

`These last two solutions, a function template or a member function, are
both great improvements over our original version, but note that they still
have a restriction. They can only sort arrays. In the function template case
we have used an array declaration as the type of one of the parameters. If we
have a member function of class Array we are obviously restricted to sorting
objects of that type. `

`However, if we apply the pointer duality rule uniformly we can remove even
this requirement. We are going to change selectionSort again. Suppose we pass
in two pointers, one that points to the first component of the array and one
that points just after the array. A typical call might look something like the
following.`

`
`

```
int elements[20];
int * start = elements;
int * after = &elements[20];
...
selectionSort(start, after);
```

`To make this work we change the prototype of the function template
to`

`
`

```
template < class T >
void selectionSort(T* start, T* end)
```

`Now, selectionSort can sort elements without referring to an array directly
in any way. The important thing to recognize is the pointer duality law, which
states that if A is any pointer to the start of an array, then A[i] is
equivalent to A + i. The replacements we shall make are defined as
follows:`

`replace elements[s] by *loc or equivalently &elements[s] by
loc`

`replace elements[i] by *where`

`replace elements[j] by *inner`

`See Figure 2.7 and compare it to Figure 2.6. `

`This gives us the following version, which no longer makes reference to any
array, only to pointers that point in to the array. `

`
`

```
template < class T >
void selectionSort(T* start, T* end)
{ for(T* where = start ; where < end ; where++)
{ T* loc = where;
T small = *loc;
for(T* inner = where + 1; inner < end; inner++)
if(*inner < *loc)
{ loc = inner;
small = *loc;
}
*loc = *where;
*where = small;
}
}
```

`
`

`Figure 2.7. Selection Sort, Inner Loop with Pointers`

`The algorithms of the Standard Template Library are all defined using this
last idea. While it is entirely equivalent to the above when we are sorting
arrays, the fact that the algorithm doesn't refer directly to arrays but only
to pointers means that the same algorithm can be used for other structures that
have the property that they can be referred to by pointers. Do note however,
that this last version is not nearly as easy to read. Especially for novices.
Being less easy to read and understand, it is more likely to have an error.
`

`What essential features of pointers have we used in the above? All we need
to do is examine the uses. We have applied operator++ to the pointer variables
in several places. We have used operator* to dereference the pointers in
several places. We have used operator< for pointers (as well as their
dereferenced values). We have assigned one pointer value to another with
operator=. We have done pointer arithmetic (e.g. where + 1). Finally, we have
implicitly assumed that if we execute start++ sufficiently often then
eventually start < end will be false. The implication of all this is that
we don't even need pointers. Any datatype that has these essential features
could be used in place of pointers here. The iterators of the STL have all of
these properties. `

`It is important to note that we refer to the contents of a container in the
STL using two iterators. The first of these refers to some element in the
container: its "first" element. The other, however does not refer to any
element. It refers to a location "past the end" of the container. In
mathematics a range of real numbers is called an interval. There are several
kind of intervals depending on whether they include or exclude their endpoints.
The interval [a, b], for exammple, includes all of the numbers between a and b,
including both of these values, as well. This is called a "closed" interval.
The open interval (a,b) excludes both endpoints, but contains the values
strictly between a and b. The half open interval [a,b), includes a, but
excludes b. In the STL we uniformly use something like this half open interval
to refer to our containers, except that the "end points" are iterators, rather
than numbers. `

`It is also possible to sort an array into decreasing order, in which the
largest value is first, rather than last. To do so we replace operator<
with operator> of course. `

`
`

`Once an array is sorted, it is possible to search in much more efficiently
than if it is not. One commonly used mechanism is called binary search which
is similar to a guessing game that you may have played. One player announces
that she has thought of a number, say between 1 and 100. The other players
guess what the number is, and for each guess the original player informs the
guesser whether the guess is correct, too high, or too low. A correct sequence
of guesses can arrive at the remembered number quite quickly. In fact, if the
number remembered is between 1 and one million, it only requires about 20
guesses to arrive at the answer. `

`The correct next guess, of course, is half way between the largest previous
guess that was too low, and the smallest previous guess that was too high. So
your first guess in the 1...100 version is 50 and if that is too high you next
try 25, which if too low, you next guess either 37 or 38, etc. `

`In binary search over a sorted array, we first look in the cell in the
middle of the array. If that is the desired value we are done, but if that
value is larger than the one we seek, then, since the array is sorted, the
desired value must be to the left (assuming the sort was increasing). Binary
search is called "binary" by the way, since it splits the portion of the array
yet to be searched into two equal parts at each step. In other words, each
failure reduces the remaining work by a factor of 2. `

`Here is a recursive version of binary search over an array. It returns the
cell number in which it finds the item, or an arbitrary cell number if the
target is not present. Because the process is recursive over a portion of the
array, we must pass parameters to indicate the subscript bounds of the search.
`

`
`

```
template<class T>
unsigned int binarySearch
( T* elements, // Array of Ts.
const T& t, // Searching for t in elements.
unsigned int first, // Starting here.
unsigned int last // Ending here.
)
{ if(first >= last) return first;
unsigned int mid = (first + last)/2; // Middle.
if(t == elements[mid]) return mid;
if(elements[mid] < t )
return binarySearch(t, mid + 1, last);
else
return binarySearch(t, first, mid - 1);
}
```

**Exercise**. Modify Binary Search by applying the pointer duality law
throughout. The parameters of your modified version should be the target plus
two pointers, one to the first cell of interest, and the other to the location
just after the last. It should return a pointer to the cell that contains the
value if found, and an arbitrary pointer into the array otherwise. Be careful
about the translation of mid. Test both the original version and your new
version.

`
`

`Quicksort is called quick because it sorts faster than sorts like selection
sort. This is because it does more work each time they scan the array. In
particular, what we will attempt to do is to establish the truth of the logical
statement embodied in Figure 2.8.`

`
`

`Figure 2.8`

`The idea here is to split the array approximately in the middle around a
value t with the property that all values to the left of t are less than or
equal to it, and all values to the right are strictly larger. Once we establish
this "partition step" we will then recursively sort the two side pieces: the
piece from 0 to m-1 and the piece from m + 1 to length - 1. Since this is to
be done recursively, and since we need to say in the recursion step what the
limits of the sorting are to be, quickSort will need to have two parameters so
that we may pass in these bounds. We can establish our plan in an outline as
follows`

`quicksort(first, last) is`

` if (first < last)`

` partition, finding m`

` quicksort(first, m-1)`

` quicksort(m+1 last)`

`There are a variety of ways to carry out the partition step. One of the
clearest and easiest follows. What we will do first is establish the truth of
Figure 2.9.`

`
`

`Figure 2.9`

`This will be a bit easier to do, since we know where the special "pivot"
value will be -- always in cell first. Instead of m, we now use an index
named lastLow, that marks the cell in which we find the last "small" value.
Note that if we can establish 2.9 then a swap of cells first and lastLow will
establish Figure 2.8. `

`To establish Figure 7.4 we will carry out a process described in Figure
2.10.`

`
`

`Figure 2.10`

`What we do here is to use an index i, which we move along so that it is
eventually equal to last. Cells between first+1 and lastLow are <= t, those
between lastLow+1 and i are > t, and we don't know about those beyond i,
since we haven't examined them yet. We make this picture true initially by
setting i and lastLow to be first. Then all parts are empty except the first
cell and the ?? part. We get i to be last eventually, by increasing it in a
for loop. We keep Figure 2.10 to be true in the following way. Each time we
increase i we examine the new cell i. If its value is > t then nothing
needs to be done. On the other hand, if it is <= t, we can increase lastLow
and then swap cells i and lastLow. This will reestablish the truth of 2.10 for
the new i. Putting all of this together we arrive at the following code for
quickSort. We employ an auxiliary function swap, that exchanges the values of
two cells. `

`
`

```
template<class T>
void swap(T* elements, int i, int j)
{ T temp = elements[i];
elements[i] = elements[j];
elements[j] = temp;
}
template<class T>
void quickSort
( T * elements,
unsigned int first,
unsigned int last
)
{ if(first < last)
{ T t = elements[first]; // t is the pivot.
unsigned lastLow = first;
for (unsigned i = first + 1; i <= last; i++)
if(elements[i] < t)
{ ++lastLow;
swap(elements, lastLow, i);
}
swap(first, lastLow);
if(lastLow != first)
quickSort(elements, first, lastLow - 1);
if(lastLow != last)
quickSort(elements, lastLow + 1,last);
}
}
```

`Note that the portion of this algorithm up to the recursive calls is called
the partition step and its result (Figure 2.8) is called a partition of the
array. `

**Exercise**. Modify QuickSort by applying the pointer duality law
throughout. Your function should have two parameters. They are pointers to
the beginning and the "after" position as usual. Test both the original
version and your new version.

`
`

`After correctness, the most important aspect of any algorithm is its
efficiency. There are two aspects to efficiency, namely the efficiency of the
algorithm itself and the efficiency of its implementation. It turns out that
the latter measure is not nearly so important as the former and merely requires
that the programmer take care not to execute unneeded instructions. The
essential efficiency of the algorithm itself is much more important as it sets
limits that no details of implementation can overcome. `

`Efficiency can be measured various ways. One measure is the space
required. If an algorithm is written to run on a multi-processor system then
the number of processors required may be an important measure. Usually,
however, efficiency means time efficiency. How much time can we expect an
algorithm to take to complete? `

`It must first be recognized that this question cannot be answered in
specific, concrete, exact terms. Computers differ in their speeds. Disk
drives have differing transfer rates. Multi-user computers have different
loads that affect the speed of programs running on them. Most importantly,
each time we run a program we likely do so with a different set of input data.
This can have a large effect, and we expect that a run with a small amount of
data will be faster than one with a large amount of data. `

`Therefore efficiency is always expressed in terms of some measure of the
input requirements (size of the data) or the resources required (memory,
processors, ...). Here we will consider only the time efficiency of our
algorithms as a function of the size of the input data. We also adopt a
measure that will be independent of the speed of a particular computing system
on which a program implementing the algorithm might be run. `

`Some algorithms always take the same amount of time when run on a given
system in a given start state (system load, available memory...). For example,
an algorithm that returns the first element of an array can be expected to run
in constant time independent of the size of the array. However, an algorithm
that uses a simple for loop to sum the elements of an integer array must visit
each cell of the array, so we expect that its running time will be proportional
to the size of the array, approximately doubling if we double the size of the
array. But this doubling isn't a precise measure either, since any such
algorithm will have a certain amount of overhead (initializing the sum...) that
must be done no matter what the number of data items that it processes.
Therefore, for example, summing an array of two items using our for loop
algorithm will not run exactly twice as long as when applied to one element.
However, between 1000 and 10,000 elements the time will be very nearly related
in a 1 to 10 ratio, since this fixed overhead will be "amortized" or spread out
over a large number of repetitions. `

`In order to be as precise as possible when presenting the run-time
characteristics of an algorithm, we resort to a mathematical means of
expressing the upper and lower bounds of functions, here the running time, as a
function of the amount of the data processed. What we do, essentially, is to
compare the running time function to functions of well known behavior, such as
polynomials, logarithms, and exponential functions. These functions have been
extensively studied and characterized using Calculus. When the value of
function g is always less than the value of function f for a given input x, we
say that f dominates g, or gives an upper bound for g. If, on the other hand,
function g is always greater than function h at each point of the domain, we
say that h forms a lower bound of g. If functions f and h are also quite close
together at all input values then we have pinned down the behavior of function
g quite well. `

`Computers run relatively fast today, so the behavior of an algorithm on a
small amount of data is only seldom of interest. For most algorithms the time
is "nearly instantaneous." The problem gets interesting only when the data set
gets large, the time gets long, and we reach the limit of how long we are
willing to wait for an answer. So, we are usually willing to ignore the bounds
problem for small inputs. With all of this in mind we can give a definition of
a precise measure of the upper bound of a function, in terms of another
function. `

`Let f and g both be functions of an integer variable. We say that function
g is O(f), read "big oh of f, provided that there is an integer M and a
constant C, such that for all x>M it is true that g(x) <= C
``.`` f(x). The purpose of M is to ignore small values of x
(the size of the input in our application). In effect, this lets us ignore the
fixed overhead of the algorithm. The purpose of C is to provide a constant of
proportionality that lets us ignore the specific speed of processors.
Different systems will just have different values of C. `

`Note that if our running time is O(f) for some function f, this just means
that the running time for input size n is less than some multiple of f(n) for
all n that are relatively large. It might be nearly C ^{.}f(n) or
considerably less. To get a "sharp" estimate of the running time we also need
a lower bound. `

`Lower bounds are expressed quite differently, though it sounds similar. We
say that a function g is `[[Omega]]` (f), read "big omega of f", if
there is a constant C such that for any integer N there is an n > N such
that g(n) >= C``.``f(n). Said another way, g is bigger than a
fixed multiple of f for infinitely many values. All this means is that it is
sometimes "large", not that it is necessarily always large. In terms of
running time this means that for some sets of inputs, the program will run for
a long time and that this behavior will be observed for more than just a finite
number of values. `

`Normally however, when we give a "big oh" bound for a function, we mean
that the running time is indeed close to that bound. So, while it is
technically true to describe a function as O(x ^{2}), when it is also
O(x), that won't normally be done. Note that if a function is big O of some
polynomial function then it is also big O of x^{n}, where n is the
degree of that polynomial, since any given polynomial of degree n, is
O(x^{n}). `

`We call an algorithm linear if it is O(x), since f(x) = x is a linear
function. An algorithm that is O(x ^{2}) is called quadratic. One that
is O(x^{3}) is cubic. As one extreme, an algorithm with constant
running time is O(1), and at the other extreme an algorithm is called
exponential if it is O(2^{n}). Exponential running time algorithms
take extremely long to execute on large sets of data as illustrated by the
following exercise. Another commonly used bound function is the logarithmic
function log2(n). An algorithm with such a bound is described as logarithmic.
`

**Exercise**. Suppose that you have an exponential algorithm that takes
1 second to complete if the size of the input is 16 items. For each additional
item the time doubles. How much time does it take on a set of 64 items?
Suppose your computing cost (cost of time and depreciation on the machine +
electricity consumed) is one penny for 16 items. What does it cost for 64
items using the same formula?

`The sequential search algorithm presented above is linear, of course. The
number of steps it executes is directly proportional to the length of the array
as can be inferred from the use of the for loop. Likewise the selection sort
algorithm is quadratic, since it contains two nested loops, each of which is
linear. In general, algorithms built out of loops are relatively easy to
analyze for their run time bounds. Recursive algorithms and some others are a
bit more challenging. `

`One means of analyzing the running time of an algorithm is to write down an
equation that describes the running time and then to solve it. Even though we
know that sequential search has linear running time, let us use this technique
to analyze the efficiency as an illustration of how to go about it. `

`In sequential search we look at one item in a set of n and if that is not
the target of the search we still need to examine n-1 others. Therefore if
there is a single item in our container we take one unit of work to verify
whether or not that item is the target. If there is more than one item, say n,
then the work required is one unit to check the first item plus the work
required for the other n-1 items. If we write down this work equation, where
Wn represents the work done for n items and Wn-1 the work for n-1 items, we get
the following. `

`Wn = 1 + Wn-1, if N > 1 and W1 = 1. `

`We can solve this by repeated substitution, replacing a work term on the
right hand side by its definition using this formula itself. Notice that we
start with n-1 on the right and a single 1. If we substitute the meaning of
Wn-1 = 1 + Wn-2 into the above formula we get:`

`Wn = 1 + ( 1 + Wn-2 ) = 2 + Wn-2 `

`If we repeat this we get `

`Wn = 2 + Wn-2 = 3 + Wn-3 . . . = n`

`That is to say, the work to process n items is n times the work to process
one item. This again justifies the statement that the work of sequential
search is proprotional to the length of the array. `

`Suppose that we try to analyze the running time of binary search in this
same way. `

`The binary search proceeds by doing one unit of work to look in the center
location in the array. If that is not a hit, then the recursion says that the
binary search must do the same process over a data set half as large. Of
course, if the array only has one item it only takes one unit of work. We just
verify that that item is, or is not, the target of the search. Suppose that we
again let Wn represent the work done (time expended) for exactly n items. Then
an equation defining this work that corresponds to the first two sentences of
this paragraph is`

`Wn = 1 + Wn/2, if n > 1, and W1 = 1. `

`This can be solved if we substitute n = 2 ^{k} into the equation and
then do repeated substitutions on the right hand side using this definition
itself. `

`W2k = 1 + W2k-1, if n > 1, and W1 = 1. `

` = 1 + 1 + W2k-2`

` = 1 + 1 + 1 + W2k-3`

` . . .`

` = k`

`Therefore Wn = k = log2(n), and we have a logarithmic algorithm. This is
very good, since the log of a number is small in comparison to the number.
This justifies our earlier claim that we can binary search an array with a
million items with only about 20 repetitions. `

**Exercise** Normally the quick sort exhibits the following behavior.
The partition step splits the array into two parts of about equal size.
Therefore the work done is the work done to do the partition, which is linear,
plus the work done to quick sort the two halves. But this is just twice the
work required to sort an array half as big. Of course, an array with only one
element takes no work at all to sort, since it already is sorted. Use this
idea to verify the claim that quick sort is O(n log2(n)).

`Some algorithms work well on most data sets but perform badly on a few.
Quick sort as presented here is such an algorithm. In an average case the
quick sort is O(n log2(n)). However, the algorithm as presented has a very
strange behavior if we give it a sorted array to start with. In this case, the
partition doesn't divide the array into two parts of equal size, but into one
part that is empty and the other which has just one less element. So, in this
case, the running time is the time required to do the partition (linear) plus
the time required to sort an array with one less item. Now the recurrence is
`

`Wn = n + Wn-1, if n > 1, and W1 = 0. `

`It is easy to show that the solution of this "recurrence relation" is a
quadratic function of n. Therefore, quick sort is no better than insertion
sort on a few cases. For quick sort we say that the average running time is
O(n log2(n)), but the worst case running time is O(n ^{2}). As a
shorthand we will use lg(n) in place of log2(n) as the log base 2 commonly
occurs when measuring efficiency. `

`There is another measure of running time that is occasionally useful,
though not for these algorithms. Suppose we want to build a class to implement
arrays that can be expanded. A nice technique is to do the following. The
class has a member variable that is a dynamic array of some convenient size at
creation. If we later learn that the array was too small we "expand" the array
as follows. Allocate a new array, twice as long as the original, copy the
elements from the old array into the new one, and then delete the old array,
assigning the new one to the member variable. If we ask how much time it takes
to insert an element into this "array class", the answer is that it depends.
If it is not time to expand, the time is constant, If an expansion is required
the time is linear in the number of items currently stored, to account for the
copying time. But if we average this out over all insertions, we find that the
(average) time is still constant, actually about twice the time of one of the
atomic instructions. Note that to make this work you must double the size when
you expand, not just increase it by a fixed amount. Such an algorithm is
called "amortized constant," since we amortize the cost of an expensive
operation out over several cheap operations, with the average being constant.
`

`
`

`Most of the algorithms provided with the Standard Template Library work for
arrays as well as those additional containers provided by the STL itself. This
was one of the primary design decisions of the STL. They work because pointers
into arrays satisfy the requirements of random access iterators. Since most of
the algorithms work with such iterators, they work with arrays. `

`To use the algorithms you must include the header <algo.h> provided
with the STL and probably provided with your C++ compiler. To sort an array,
we need a pointer to the beginning of it and a pointer to the cell that would
immediately follow the array (not a pointer to the last cell, a pointer to the
following cell). Consider the following test example`

`
`

```
int testArray[5] = { 3, 1, 4, 2, 5 };
int * first = testArray;
int * last = &testArray[5];
sort(first, last);
for (int i =0; i< 5; ++i)
cout << testArray[i]<<endl;
```

`This produces `

`
`

```
1
2
3
4
5
```

`Notice that the sort function doesn't mention the array that it is sorting.
It only needs pointers to the first cell and the "last" position. Technically,
in the language of the STL, sort takes two iterators as arguments and sorts the
section of the container between the two iterators, including the item at the
location of the first iterator and not including the position of the second.
Sort works for many (but not all) of the container classes, and most algorithms
take one or more iterators as arguments. `

`There are two requirements for using the sort routine of the STL. The
first is that the pointer must dereference to a type that supports
operator<. In other words, the component type must support this operator.
The second is that the operator< of that type must have the property that if
a < b then it is not true also that a == b. If your type doesn't meet this
specification then you might get a compiler error that operator< is not
defined, or if it is but the operator fails to satisfy its condition, then
using sort may result in an infinite computation. `

`A somewhat less obvious requirement of the STL sort is automatically
fulfilled by arrays and array pointers. Sort requires that the iterators (here
pointers) passed in satisfy the requirements of random access iterators. Since
array pointers have this property this is not a problem, but applying sort to
some other data structures (e.g. linked lists) might not be possible. `

`The STL sort algorithm is a variation of quicksort. It is a bit more
sophisticated than the one shown above, as it works efficiently for already
sorted arrays, though it will be inefficient for some collections of data. The
STL has other sort routines that are slower on average than sort, though they
can be guaranteed to always be faster than quadratic algorithms like selection
sort. See heap sort in the index, for example. `

`Another STL algorithm that can be used in exactly the same way as sort is
reverse, which reverses the elements of an array (or other container). `

`Note that when you apply one of the STL algorithms using an iterator, the
value of that iterator may change. It may no longer point to the location to
which it originally pointed. We say that an iteration "consumes its iterator."
`

`
`

`One of the important problems in computer processing is how to efficiently
and effectively store large amounts of information. The solution is called a
database. We shall present an extremely simple solution here, that is not
really adequate for large amounts of data, but it introduces a few key
concepts. `

`Data is stored so that it may later be retrieved. Usually the data is
stored once, updated infrequently, but accessed frequently. Eventually the
data will likely be removed. For example, when a new employee is hired a new
record is placed into the employee database, describing the relevant
information about that person. The data is modified or updated only when some
piece of information changes, such as name or address. The data is retrieved
at least as frequently as the pay cycle, since it is needed to write a
paycheck. Finally, when the person leaves employment the data is removed from
the active part of the database, though the information may simply be moved to
an archival region. `

`Since retrieval is done more frequently than creation/modification/removal,
it is important to organize the database so that lookups are fast, even if this
somewhat slows the speed of insertions. One of the chief ways that this is
achieved is to choose from among all of the data to be stored, some portion
that can be guaranteed to be uniquely associated with the data entity (here
person) and that will not be the same for any other entity. This portion of
the record is called the key, and the remainder of the data for that
entity is called the information. Therefore, data is a collection of
key-information pairs. Social Security Numbers are often used in the United
States as a key for employee records, since they are required to be maintained
by employers (for taxing purposes) and they are also (supposed to be) unique.
In general, however, the type of the key and the type of the information differ
from one database to another, and even from one portion of the same database to
another, so it is useful to abstract these types. We can do this with a class
template.`

`
`

```
template <class Key, class Information>
class DataRecord
{ public:
DataRecord(Key k, Information v):key(k), information(v){}
Information getInformation() const
{ return information;
}
bool match(const Key k) const
{ return k == key;
}
private:
Key key;
Information information;
DataRecord(){} // Needed to create arrays of DataRecords.
friend class Database<Key, Information>;
};
```

`We can now build a database using an array to hold DataRecords. This
solution, as mentioned before, is overly simplified as it requires that we know
the maximum size of the database in advance, which is seldom the case. `

`
`

```
template <class Key, class Information>
class Database
{ public:
Database(int size)
: currentSize(0),
storage(new DataRecord<Key, Information> [size] )
{
}
void store (const Key k, const Information v)
{ storage[currentSize++] =
DataRecord<Key, Information> (k, v);
}
Information retrieve(const Key k) const
{ for(int i = 0; i < currentSize; i++)
if(storage[i].key == k) return storage[i].information;
return Information();
// The default value of type Information;
}
private:
DataRecord<Key, Information> * storage;
// Save the data in an array.
int currentSize;
};
```

`We can now store information into our database, where it is saved in the
next available slot in the array. We can also retrieve the information
associated with any key, though it takes a sequential search of the database to
achieve it. Thus, though it works, it does not satisfy the efficiency
requirements that specify that lookups should be fast. Here insertions are
fast but retrievals are very slow. `

`To create a database you need to specify the key and information types as
well as the maximum size. `

`
`

```
Database< int, char*> BonMot(100);
BonMot.store(22, "Have a nice day.");
BonMot.store(11, "Have an OK day.");
BonMot.store(33, "Have a wonderful day.");
BonMot.store( 5, "Have a day.");
cout << BonMot.retrieve(11) << endl;
cout << BonMot.retrieve(99) << endl; // Prints garbage.
```

**Exercise**. Speed up retrievals, even at the expense of insertions.
One way to do this is to sort the database after each insertion. This requires
that DataRecords have an operator<, which you will need to write. This
operator should consider only the keys and ignore the information values.

**Exercise.** Devise a better mechanism for signaling that the data
sought is not to be found. You can turn retrieve into a bool function that
returns its information value in a reference parameter, for example. Throwing
an exception is another possibility.

`
`

`If we assign a value to some component of an array, then a copy of the
value is made and stored at that component. Sometimes we want to avoid this
copying because of its cost, or because the logic of the problem dictates that
we not make copies of things. In this case we may store pointers to values
rather than values themselves as the components of the arrays. This same
technique may be applied to other containers as well, of course. `

`For example, in a database, it might be desirable to store the same objects
in several places without copying. We try to keep only a single copy of data
in a database to simplify the problem of updating values. If several copies of
a piece of data are stored, then all must be updated at the same time. One way
to achieve this is to avoid copies altogether, keep one copy of each piece of
data and use pointers as needed to simulate replication. `

`To do this our database will store pointers to data records rather than
data records. Each cell of the array will contain just a pointer to some
actual data record, or possibly be NULL. `

`Aside from the avoidance of copying, there is another major advantage of
using pointers as the contents of our containers. This is the possibility of
making the containers heterogeneous: of storing different types of things in
the same container. This can't be done with complete freedom in C++, however,
since pointers have a type that includes the type of the thing that they point
to. However, we may use the object oriented features of C++ to achieve
heterogeniety. We return again to derived classes. `

`Since we define a new class when we derive one class from another, we have
different types. However these types are partly compatible with each other.
In particular, a pointer to a base type may hold a value that is a pointer to a
derived class. This means that if we have a container, such as an array,
defined to hold pointers to some class, then it may in fact hold pointers to
any class derived from that class. For example, we may create an array of
pointers to SpreadSheetCells and store pointers to NumericCells and
FormulaCells as well. `

`
`

```
SpreadsheetCell* lotsOfCells [100]; // Array of cell pointers
lotsOfCells[0] = new FormulaCell(...);
lotsOfCells[1] = new NumericCell(...);
```

`As a final brief note, we mention that pointers may be used to refer to
other things than arrays. One of the most fruitful uses is to use pointers as
links to chain data cells together. Each cell will now contain not only a
value, such as an array cell does, but also the address of another cell. In
this way the cells do not need to be stored contiguously, but can be anywhere
in the free store. The advantage of this is that it is quite easy to insert a
cell "between" two other cells and nothing needs to be moved. All that is
required is that the addresses that impose the physical ordering on the cells
be updated. In this way we can build sequential structures called linked
lists. More generally, we can use more than one such address in a cell and
build non-sequential structures such as trees and graphs. Lists will be taken
up in detail in Chapter 8. `

`
`

`Make certain that you understand each of the following terms`

`Array`

`Array Section`

`Alias`

`Big O`

`Binary Search`

`Cell`

`Component`

`Half Open Interval [a, b)`

`Index`

`Iterator`

`Pointer`

`Pointer Duality Law`

`Quicksort`

`Searching`

`Selection Sort`

`Sequential Search`

`Sorting`

`Subscript`

`
`

`1. Build a calendar generation program. Fill in a 6 by 7 array with
numbers representing the days of a month. Consider columns to represent the
days Sunday, Monday, ..., Saturday. Input a date a build a calandar for the
month containing that date. If a cell does not correspond to a day in that
month, give it a zero or negative value. Provide a print routine to print
nicely formated monthly calendars. `

`More sorts`

`More use of stl`

`apps`

`
`