c++.tex

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

void
ArrayStack::Push(int value) {
    ASSERT(!Full());
    stack[NumPushed()] = value;
    Stack::Push();	     // invoke base class to increment numPushed
}
\end{verbatim}

There are a few things to note:

\begin{enumerate}

\item The constructor for {\tt ArrayStack} needs to invoke the
constructor for {\tt Stack}, in order to initialize {\tt numPushed}.
It does that by adding {\tt : Stack()} to the first line in the constructor:

\begin{verbatim}
ArrayStack::ArrayStack(int sz) : Stack()
\end{verbatim}

The same thing applies to destructors.  There are special rules for which 
get called first -- the constructor/destructor for the base class or 
the constructor/destructor for the derived class.  All I should say is,
it's a bad idea to rely on whatever the rule is -- more generally, it is a 
bad idea to write code which requires the reader to consult a manual 
to tell whether or not the code works!

\item I introduced a new keyword, {\tt protected}, in the new definition
of {\tt Stack}.  For a base class, {\tt protected} signifies that those
member data and functions are accessible to classes derived (recursively)
from this class, but inaccessible to other classes.  In other words, protected
data is {\tt public} to derived classes, and {\tt private} to everyone else.
For example, we need {\tt Stack}'s constructor to be callable by 
{\tt ArrayStack} and {\tt ListStack}, but we don't want anyone
else to create instances of {\tt Stack}.  Hence, we make {\tt Stack}'s 
constructor a protected function.  In this case, this is not strictly
necessary since the compiler will complain if anyone tries to create an
instance of {\tt Stack} because {\tt Stack} still has an undefined virtual 
functions, {\tt Push}.  By defining {\tt Stack::Stack} as {\tt protected}, 
you are safe even if someone comes along later and defines {\tt Stack::Push}.

Note however that I made {\tt Stack}'s data member {\tt private}, not
{\tt protected}.  Although there is some debate on this point,
as a rule of thumb you should never allow one class to see directly
access the data in another, even among classes related
by inheritance.  Otherwise, if you ever change the implementation
of the base class, you will have to examine and change all the 
implementations of the derived classes, violating modularity.

\item The interface for a derived class automatically includes all
functions defined for its base class, without having to explicitly 
list them in the derived class.  Although we didn't define 
{\tt NumPushed()} in {\tt ArrayStack}, we can still call it for 
those objects:

\begin{verbatim}
    ArrayStack *s = new ArrayStack(17);

    ASSERT(s->NumPushed() == 0);	// should be initialized to 0
\end{verbatim}

\item Conversely, even though we have defined a routine {\tt Stack::Push()},
because it is declared as {\tt virtual}, if we invoke {\tt Push()} 
on an {\tt ArrayStack} object, we will get {\tt ArrayStack}'s version 
of {\tt Push}:

\begin{verbatim}
    Stack *s = new ArrayStack(17);

    if (!s->Full())		// ArrayStack::Full
        s->Push(5);		// ArrayStack::Push
\end{verbatim}

\item {\tt Stack::NumPushed()} is not {\tt virtual}.  That means 
that it cannot be re-defined by {\tt Stack}'s derived classes.
Some people believe that you should mark {\em all} functions
in a base class as {\tt virtual}; that way, if you later want to
implement a derived class that redefines a function, you don't have
to modify the base class to do so.

\item Member functions in a derived class can explicitly invoke 
public or protected functions in the base class, by the full
name of the function, {\tt Base::Function()}, as in:

\begin{verbatim}
void ArrayStack::Push(int value)
{
    ...
    Stack::Push();	     // invoke base class to increment numPushed
}
\end{verbatim}

Of course, if we just called {\tt Push()} here (without prepending 
{\tt Stack::}, the compiler would think we were referring 
to {\tt ArrayStack}'s {\tt Push()}, and so that would recurse,
which is not exactly what we had in mind here.

\end{enumerate}

Whew!  Inheritance in C++ involves lots and lots of details.
But it's real downside is that it tends to spread implementation 
details across multiple files -- if you have a deep inheritance 
tree, it can take some serious digging to figure out what code 
actually executes when a member function is invoked.

So the question to ask yourself before using inheritance is:
what's your goal?  Is it to write your programs with the
fewest number of characters possible?  If so, inheritance is
really useful, but so is changing all of your function and variable 
names to be one letter long -- "a", "b", "c" -- and once you
run out of lower case ones, start using upper case, then two character 
variable names: "XX XY XZ Ya ..." (I'm joking here.)
Needless to say, it is really easy to write unreadable code
using inheritance.  

So when is it a good idea to use inheritance and when should it be
avoided?  My rule of thumb is to only use it for representing 
{\em shared behavior} between objects, and to never use it for
representing {\em shared implementation}.  With C++, you can use 
inheritance for both concepts, but only the first will lead to
truly simpler implementations.

To illustrate the difference between shared behavior and shared
implementation, suppose you had a whole bunch of different kinds
of objects that you needed to put on lists.  For example, almost everything
in an operating system goes on a list of some sort: buffers, threads,
users, terminals, etc.

A very common approach to this problem (particularly among people new
to object-oriented programming) is to make every object inherit from
a single base class {\em Object}, which contains the forward and backward
pointers for the list.  But what if some object needs to go on multiple
lists?  The whole scheme breaks down, and it's because we tried to use
inheritance to share implementation (the code for the forward and backward
pointers) instead of to share behavior.  A much cleaner (although slightly
slower) approach would
be to define a list implementation that allocated forward/backward
pointers for each object that gets put on a list.

In sum, if two classes share at least some of the same member function
signatures -- that is, the same behavior, {\em and} if there's code that
only relies on the shared behavior, then there {\em may}
be a benefit to using inheritance.  In Nachos, locks don't inherit from
semaphores, even though locks are implemented using semaphores.  The
operations on semaphores and locks are different.  Instead, inheritance is
only used for various kinds of lists (sorted, keyed, etc.),
and for different implementations of the physical disk abstraction,
to reflect whether the disk has a track buffer, etc.  A disk is used
the same way whether or not it has a track buffer; the only difference is
in its performance characteristics.

\subsection{Templates}

Templates are another useful but dangerous concept in C++.
With templates, you can parameterize a class definition
with a {\em type}, to allow you to write generic type-independent
code.  For example, our {\tt Stack} implementation above only worked 
for pushing and popping {\em integers}; what if we wanted a stack 
of characters, or floats, or pointers, or some arbitrary data structure?

In C++, this is pretty easy to do using templates:

\begin{verbatim}
template <class T> 
class Stack {
  public:
    Stack(int sz);    // Constructor:  initialize variables, allocate space.
    ~Stack();         // Destructor:   deallocate space allocated above.
    void Push(T 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.
    T *stack;       // A pointer to an array that holds the contents.
};
\end{verbatim}

To define a template, we prepend the keyword {\tt template} to
the class definition, and we put the parameterized type for the
template in angle brackets.  If we need to parameterize the implementation
with two or more types, it works just like an argument list:
{\tt template <class T, class S>}.  We can use the type parameters
elsewhere in the definition, just like they were normal types.

When we provide the implementation for each of the member functions
in the class, we also have to declare them as templates, and again,
once we do that, we can use the type parameters just like normal types:

\begin{verbatim}
     // template version of Stack::Stack
template <class T> 
Stack<T>::Stack(int sz) {
    size = sz;
    top = 0;
    stack = new T[size];   // Let's get an array of type T
}

     // template version of Stack::Push
template <class T> 
void
Stack<T>::Push(T value) {
    ASSERT(!Full());
    stack[top++] = value;
}
\end{verbatim}

Creating an object of a template class is similar to creating
a normal object:

\begin{verbatim}
void
test() {
    Stack<int> s1(17);
    Stack<char> *s2 = new Stack<char>(23);

    s1.Push(5);
    s2->Push('z');
    delete s2;
}
\end{verbatim}

Everything operates as if we defined two classes, one
called {\tt Stack<int>} -- a stack of integers, and one
called {\tt Stack<char>} -- a stack of characters.
{\tt s1} behaves just like an instance of the first;
{\tt s2} behaves just like an instance of the second.
In fact, that is exactly how templates are typically implemented --
you get a complete {\em copy} of the code for the template
for each different instantiated type. In the above example,
we'd get one copy of the code for {\tt ints} and one copy for {\tt chars}.

So what's wrong with templates?  You've all been taught to make
your code modular so that it can be re-usable, so {\em everything}
should be a template, right?  Wrong.  

The principal problem with templates is that they can be {\em very} 
difficult to debug -- templates are easy to use if they work, but 
finding a bug in them can be difficult. In part this is because 
current generation C++ debuggers don't really understand templates 
very well.  Nevertheless, it is easier to debug a template than
two nearly identical implementations that differ only in their types.

So the best advice is -- don't make a class into a template
unless there really is a near term use for the template. And if you
do need to implement a template, implement and debug a non-template
version first.  Once that is working, it won't be hard to convert
it to a template.  Then all you have to worry about code
explosion -- e.g., your program's object code is now megabytes
because of the 15 copies of the hash table/list/... routines, one for 
each kind of thing you want to put in a hash table/list/...
(Remember, you have an unhelpful compiler!)

\section{Features To Avoid Like the Plague}

Despite the length of this note, there are numerous
features in C++ that I haven't explained.  I'm sure each feature
has its advocates, but despite programming in C and C++ for over 15 
years, I haven't found a compelling reason to use them in any code
that I've written (outside of a programming language class!) 

Indeed, there is a compelling reason to avoid using these features -- they are 
easy to misuse, resulting in programs that are harder to read and understand
instead of easier to understand.  In most cases, the features are also 
redundant -- there are other ways of accomplishing the same end.  Why have
two ways of doing the same thing?  Why not stick with the simpler one?

I do not use any of the following features in Nachos.  
If you use them, {\it caveat hacker}.

\begin{enumerate}

\item {\bf Multiple inheritance.}  It is possible in C++ to define
a class as inheriting behavior from multiple classes (for instance,
a dog is both an animal and a furry thing).  But if programs
using single inheritance can be difficult to untangle, programs
with multiple inheritance can get really confusing.

\item {\bf References.}  Reference variables are rather hard to
understand in general; they play the same role as pointers, with
slightly different syntax (unfortunately, I'm not joking!) 
Their most common use is to declare some parameters to a function 
as {\it reference parameters}, as in Pascal.  A call-by-reference 
parameter can be modified by the calling function, without the callee 
having to pass a pointer.  The effect is that parameters look 
(to the caller) like they are called by value (and therefore can't change), 
but in fact can be transparently modified by the called function.
Obviously, this can be a source of obscure bugs, not to mention
that the semantics of references in C++ are in general not obvious.

\item {\bf Operator overloading.}  C++ lets you redefine the meanings
of the operators (such as {\tt +} and \verb+>>+) for class objects.
This is dangerous at best ("exactly which implementation of '+' does
this refer to?"), and when used in non-intuitive ways, a
source of great confusion, made worse by the fact that C++ does 
implicit type conversion, which can affect which operator
is invoked.  Unfortunately, C++'s I/O facilities
make heavy use of operator overloading and references, so you
can't completely escape them, but think twice before you redefine
'+' to mean ``concatenate these two strings''.

\item {\bf Function overloading.}  You can also define different functions
in a class with the same name but different argument types.  This is also
dangerous (since it's easy to slip up and get the unintended version), 
and we never use it.  We will also avoid using default arguments (for the
same reason).  Note that it can be a good idea to use the same name for 
functions in different classes, provided they use the same
arguments and behave the same way -- a good example of this is that 
most Nachos objects have a {\tt Print()} method.