c++.tex

c++的一些简单但是特别精炼的例子 关于栈和链表

\begin{verbatim}
    fprintf(stdout, "Hello world!  This is section %d!\n", 3);
\end{verbatim}

except that the C++ version is type-safe; with {\tt printf}, the
compiler won't complain if you try to print a floating point number
as an integer. In fact, you can use traditional {\tt printf} in a C++
program, but you will get bizarre behavior if you try to use both
{\tt printf} and {\tt <<} on the same stream.  Reading from {\tt stdin}
works the same way as writing to {\tt stdout}, except using the shift 
right operator instead of shift left.  
In order to read two integers from {\tt stdin}:

\begin{verbatim}
    int field1, field2;
    cin >> field1 >> field2;
        // equivalent to fscanf(stdin, "%d %d", &field1, &field2);
        // note that field1 and field2 are implicitly modified
\end{verbatim}

In fact, {\tt cin} and {\tt cout} are implemented as normal C++
objects, using operator overloading and reference parameters, but
(fortunately!) you don't need to understand either of those to be able
to do I/O in C++.
\end{enumerate}

\section{Advanced Concepts in C++: Dangerous but Occasionally Useful}

There are a few C++ features, namely (single) inheritance and templates,
which are easily abused, but can dramatically simplify an
implementation if used properly.  I describe the basic idea
behind these ``dangerous but useful'' features here, in case you 
run across them.  Feel free to skip this section -- it's long,
complex, and you can understand 99\% of the code in Nachos without
reading this section.

Up to this point, there really hasn't been any fundamental difference
between programming in C and in C++.  In fact, most experienced 
C programmers organize their functions into modules that relate
to a single data structure (a "class"), and often even use a naming 
convention which mimics C++, for example, naming routines 
{\tt StackFull()} and {\tt StackPush()}.  However, the features 
I'm about to describe {\em do} require a paradigm shift -- there
is no simple translation from them into a normal C program.
The benefit will be that, in some circumstances, you will be able to 
write generic code that works with multiple kinds of objects.

Nevertheless, I would advise a beginning C++ programmer against trying
to use these features, because you will almost
certainly misuse them.  It's possible (even easy!) to write completely 
inscrutable code using inheritance and/or templates.  Although
you might find it amusing to write code that is impossible for your 
graders to understand, I assure you they won't find it amusing at all,
and will return the favor when they assign grades.  In industry,
a high premium is placed on keeping code simple and readable. 
It's easy to write new code, but the real cost comes when
you try to keep it working, even as you add new features to it.

Nachos contains a few examples of the correct use of inheritance 
and templates, but realize that Nachos does {\em not} use them
everywhere.  In fact, if you get confused by this section, don't worry,
you don't need to use any of these features in order to do the Nachos
assignments.  I omit a whole bunch of details; if you find yourself
making widespread use of inheritance or templates, you should consult a C++
reference manual for the real scoop.  This is meant to
be just enough to get you started, and to help you identify when it would
be appropriate to use these features and thus learn more
about them!

\subsection{Inheritance}
Inheritance captures the idea that certain classes of objects are
related to each other in useful ways.  For example, lists
and sorted lists have quite similar behavior -- they both 
allow the user to insert, delete, and find elements that are
on the list.  There are two benefits to using inheritance:

\begin{enumerate}

\item You can write generic code that doesn't
care exactly which kind of object it is manipulating.  For
example, inheritance is widely used in windowing systems.
Everything on the screen (windows, scroll bars, titles, icons)
is its own object, but they all share a set of member functions
in common, such as a routine {\tt Repaint} to redraw the object
onto the screen.  This way, the code to repaint the entire screen 
can simply call the {\tt Repaint} function on every object on the screen.
The code that calls {\tt Repaint} doesn't need to know which
kinds of objects are on the screen, as long as each implements
{\tt Repaint}.

\item You can share pieces of an implementation between two
objects.  For example, if you were to implement both lists and 
sorted lists in C, you'd probably find yourself repeating code
in both places -- in fact, you might be really tempted to
only implement sorted lists, so that you only had to debug
one version.  Inheritance provides a way to re-use code
between nearly similar classes.  For example, given an implementation
of a list class, in C++ you can implement sorted lists by replacing
the insert member function -- the other functions, delete, isFull,
print, all remain the same.

\end{enumerate}

\subsubsection{Shared Behavior}

Let me use our Stack example to illustrate the first of these.
Our Stack implementation 
above could have been implemented with linked lists, instead of an array.
Any code using a Stack shouldn't
care which implementation is being used, except that the linked list
implementation can't overflow. (In fact, we could also change the
array implementation to handle overflow by automatically resizing
the array as items are pushed on the stack.)

To allow the two implementations to coexist, we first define an
{\em abstract} Stack, containing just the public member functions, 
but no data.

\begin{verbatim}
class Stack {
  public:
    Stack();
    virtual ~Stack();          // deallocate the stack
    virtual void Push(int value) = 0; 
                               // Push an integer, checking for overflow.
    virtual bool Full() = 0;   // Is the stack is full?
};

// For g++, need these even though no data to initialize.
Stack::Stack {}             
Stack::~Stack() {}
\end{verbatim}

The {\tt Stack} definition is called a {\em base class} or sometimes a {\em
superclass}.  We can then define two different {\em derived classes}, 
sometimes called {\em subclasses} which inherit behavior from the base
class.  (Of course, inheritance is recursive -- a derived class can in 
turn be a base class for yet another derived class, and so on.)
Note that I have prepended the functions in the base class is prepended 
with the keyword {\tt virtual}, to signify that they can be redefined by 
each of the two derived classes.  The virtual functions are
initialized to zero, to tell the compiler that those functions
must be defined by the derived classes.

Here's how we could declare the array-based and list-based
implementations of {\tt Stack}. The syntax {\tt : public Stack} signifies 
that both {\tt ArrayStack} and {\tt ListStack} are kinds 
of {\tt Stacks}, and share the same behavior as the base class.

\begin{verbatim}
class ArrayStack : public Stack {  // the same as in Section 2
  public:
    ArrayStack(int sz);   // Constructor:  initialize variables, allocate space.
    ~ArrayStack();        // Destructor:   deallocate space allocated above.
    void Push(int value); // Push an integer, checking for overflow.
    bool Full();     // Returns TRUE if the stack is full, FALSE otherwise.
  private:
    int size;        // The maximum capacity of the stack.
    int top;         // Index of the lowest unused position.
    int *stack;      // A pointer to an array that holds the contents.
};

class ListStack : public Stack {
  public:
    ListStack(); 
    ~ListStack();
    void Push(int value);
    bool Full();
  private:
    List *list;		// list of items pushed on the stack
};

ListStack::ListStack() { 
    list = new List;
}

ListStack::~ListStack() { 
    delete list; 
}
\end{verbatim}
\newpage
\begin{verbatim}
void ListStack::Push(int value) {
    list->Prepend(value); 
}

bool ListStack::Full() {
    return FALSE; 	// this stack never overflows!
}  
\end{verbatim}

The neat concept here is that I can assign pointers to instances of
{\tt ListStack} or {\tt ArrayStack} to a variable of type {\tt Stack}, and
then use them as if they were of the base type.

\begin{verbatim}
    Stack *s1 = new ListStack;
    Stack *s2 = new ArrayStack(17);

    if (!stack->Full())
        s1->Push(5);
    if (!s2->Full())
        s2->Push(6);

    delete s1;
    delete s2;
\end{verbatim}

The compiler automatically invokes {\tt ListStack} operations
for {\tt s1}, and {\tt ArrayStack} operations for {\tt s2};
this is done by creating a procedure table for each object,
where derived objects override the default entries in the table
defined by the base class.  To the code above, it invokes the
operations {\tt Full}, {\tt Push}, and {\tt delete} by indirection
through the procedure table, so that the code doesn't need to know
which kind of object it is.

In this example, since I never create an instance of the
abstract class {\tt Stack}, I do not need to {\em implement} its
functions.  This might seem a bit strange, but remember that
the derived classes are the various implementations of Stack,
and Stack serves only to reflect the shared behavior between
the different implementations.  

Also note that the destructor for {\tt Stack} is a virtual 
function but the constructor is not.  Clearly, when I create an
object, I have to know which kind of object it is, whether 
{\tt ArrayStack} or {\tt ListStack}.  The compiler 
makes sure that no one creates an instance of the abstract {\tt Stack} 
by mistake -- you cannot instantiate any class whose virtual 
functions are not completely defined (in other words, if any of 
its functions are set to zero in the class definition).

But when I deallocate an object, I may no longer know its exact
type.  In the above code, I want to call the destructor for the
derived object, even though the code only knows that I am deleting
an object of class {\tt Stack}.  If the destructor were not virtual,
then the compiler would invoke {\tt Stack}'s destructor, which is 
not at all what I want.  This is an easy mistake to make (I made
it in the first draft of this article!) -- if you don't define
a destructor for the abstract class, the compiler will define one 
for you implicitly (and by the way, it won't be virtual, since you
have a {\em really} unhelpful compiler).  The result for the
above code would be a memory leak, and who knows how you would 
figure that out!

\subsubsection{Shared Implementation}

What about sharing code, the other reason for inheritance? 
In C++, it is possible to use member functions
of a base class in its derived class.  (You can also share
data between a base class and derived classes, but this
is a bad idea for reasons I'll discuss later.)

Suppose that I wanted to add a new member function,
{\tt NumberPushed()}, to both implementations of {\tt Stack}.
The {\tt ArrayStack} class already keeps count of the number of
items on the stack, so I could duplicate that code in {\tt ListStack}.
Ideally, I'd like to be able to use the same code in both places.
With inheritance, we can move the counter into the 
{\tt Stack} class, and then invoke the base class operations
from the derived class to update the counter.

\begin{verbatim}
class Stack {
  public:
    virtual ~Stack();		// deallocate data
    virtual void Push(int value); // Push an integer, checking for overflow.
    virtual bool Full() = 0;	// return TRUE if full
    int NumPushed();	        // how many are currently on the stack?
  protected:
    Stack();			// initialize data
  private:
    int numPushed;
};

Stack::Stack() { 
    numPushed = 0; 
}

void Stack::Push(int value) { 
    numPushed++; 
}

int Stack::NumPushed() { 
    return numPushed; 
}
\end{verbatim}

We can then modify both {\tt ArrayStack} and {\tt ListStack}
to make use the new behavior of {\tt Stack}.  I'll only list
one of them here:

\begin{verbatim}
class ArrayStack : public Stack {
  public:
    ArrayStack(int sz);   
    ~ArrayStack();        
    void Push(int value); 
    bool Full();     
  private:
    int size;        // The maximum capacity of the stack.
    int *stack;      // A pointer to an array that holds the contents.
};

ArrayStack::ArrayStack(int sz) : Stack() { 
    size = sz;
    stack = new int[size];   // Let's get an array of integers.
}