c++.tex

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

\item {\bf Standard template library.} An ANSI standard has emerged for a
library of routines implementing such things as lists, hash tables,
etc., called the standard template library.  Using such a library
should make programming much simpler if the data structure you need
is already provided in the library.  Alas, the standard template
library pushes the envelope of legal C++, and so virtually no
compilers (including g++) can support it today.  Not to mention that 
it uses (big surprise!) references, operator overloading, and 
function overloading.

\item {\bf Exceptions.} There are two ways to return an error from
a procedure.  One is simple -- just define the procedure to return
an error code if it isn't able to do it's job.  For example,
the standard library routine {\tt malloc} returns NULL if there
is no available memory.  However, lots of programmers are lazy and 
don't check error codes.  So what's the solution?  You might think 
it would be to get programmers who aren't lazy, but no, the C++ solution 
is to add a programming language construct!  A procedure can
return an error by ``raising an exception'' which effectively
causes a {\tt goto} back up the execution stack to the last
place the programmer put an exception handler.  You would think
this is too bizarre to be true, but unfortunately,
I'm not making this up.

\end{enumerate}

While I'm at it, there are a number of features of C that you also
should avoid, because they lead to bugs and make your code less easy
to understand.  See Maguire's "Writing Solid Code" for a more complete
discussion of this issue.  All of these features are legal C;
what's legal isn't necessarily good.

\begin{enumerate}
\item Pointer arithmetic.  Runaway pointers are a principal source 
of hard-to-find bugs in C programs, because the symptom of this happening
can be mangled data structures in a completely different part of the program.
Depending on exactly which objects are allocated on the heap in which 
order, pointer bugs can appear and disappear, seemingly at random.
For example, {\tt printf} sometimes allocates memory on the heap,
which can change the addresses returned by all future calls to {\tt new}.
Thus, adding a {\tt printf} can change things so that a pointer
which used to (by happenstance) mangle a critical data structure
(such as the middle of a thread's execution stack), now overwrites memory 
that may not even be used.

The best way to avoid runaway pointers is (no surprise) to be 
{\em very} careful when using pointers.  Instead of iterating
through an array with pointer arithmetic, use a separate index  
variable, and assert that the index is never larger than the size
of the array.  Optimizing compilers have gotten very good, so that the
generated machine code is likely to be the same in either case.

Even if you don't use pointer arithmetic, it's still easy
(easy is bad in this context!) to have an off-by-one errror 
that causes your program to step beyond the end of an array.
How do you fix this?  Define a class to contain the array
{\em and its length}; before allowing any access to the array,
you can then check whether the access is legal or in error.

\item Casts from integers to pointers and back.  Another source
of runaway pointers is that C and C++ allow you to convert
integers to pointers, and back again.  Needless to say, using a 
random integer value as a pointer is likely to result in unpredictable
symptoms that will be very hard to track down.

In addition, on some 64 bit machines, such as the Alpha, it is
no longer the case that the size of an integer is the same as the
the size of a pointer.  If you cast between pointers and integers,
you are also writing highly non-portable code.

\item Using bit shift in place of a multiply or divide.
This is a clarity issue.  If you are doing arithmetic, use
arithmetic operators; if you are doing bit manipulation,
use bitwise operators.  If I am trying to multiply by 8, which is 
easier to understand, {\tt x << 3} or {\tt x * 8}?  In the 70's, 
when C was being developed, the former would yield more efficient 
machine code, but today's compilers generate the same code in both
cases, so readability should be your primary concern.

\item Assignment inside conditional.  Many programmers have the attitude
that simplicity equals saving as many keystrokes as possible.
The result can be to hide bugs that would otherwise be obvious.
For example:

\begin{verbatim}
    if (x = y) {
      ...
\end{verbatim}

Was the intent really {\tt x == y}?  After all, it's pretty easy
to mistakenly leave off the extra equals sign.  By never using
assignment within a conditional, you can tell by code inspection
whether you've made a mistake.

\item Using {\tt \#define} when you could use {\tt enum}.
When a variable can hold one of a small number of values,
the original C practice was to use {\tt \#define} to set up 
symbolic names for each of the values.  {\tt enum} does this 
in a type-safe way -- it allows the compiler to verify
that the variable is only assigned one of the enumerated values,
and none other.  Again, the advantage is to eliminate a class of
errors from your program, making it quicker to debug.
\end{enumerate}
\newpage

\section{Style Guidelines}

Even if you follow the approach I've outlined above, it is still
as easy to write unreadable and undebuggable code in C++ as it
is in C, and perhaps easier, given the more powerful features the
language provides.  For the Nachos project, and in general, we suggest 
you adhere to the following guidelines (and tell us if you catch us 
breaking them):

\begin{enumerate}

\item Words in a name are separated SmallTalk-style (i.e., capital
letters at the start of each new word).  All class names and member
function names begin with a capital letter, except for member
functions of the form {\tt getSomething()} and {\tt setSomething()},
where {\tt Something} is a data element of the class (i.e., accessor
functions).  Note that you would want to provide such functions only
when the data should be visible to the outside world, but you want to
force all accesses to go through one function.  This is often a good
idea, since you might at some later time decide to compute the data
instead of storing it, for example.

\item All global functions should be capitalized,
except for {\tt main} and library
functions, which are kept lower-case for historical reasons.

\item Minimize the use of global variables.  If you find yourself
using a lot of them, try and group some together in a class in a
natural way or pass them as arguments to the functions that need them
if you can.

\item Minimize the use of global functions (as opposed to member
functions).  If you write a function that operates on some object,
consider making it a member function of that object.

\item For every class or set of related classes, create a separate
{\tt .h} file and {\tt .cc} file. The {\tt .h} file acts as the {\it
interface} to the class, and the {\tt .cc} file acts as the
{\it implementation} (a given {\tt .cc} file should {\tt include} it's
respective {\tt .h} file).  If using a particular {\tt .h} file requires
another {\tt .h} file to be included (e.g., {\tt synch.h} needs
class definitions from {\tt thread.h}) you should include the dependency
in the {\tt .h} file, so that the user of your class doesn't have to 
track down all the dependencies himself.  
To protect against multiple inclusion, bracket each {\tt .h}
file with something like:
\begin{verbatim}
#ifndef STACK_H
#define STACK_H

class Stack { ... };

#endif
\end{verbatim}
Sometimes this will not be enough, and you will have a circular
dependency.  For example, you might have a {\tt .h} file that
uses a definition from one {\tt .h} file, but also defines something
needed by that {\tt .h} file.  In this case, you will have to do 
something ad-hoc.  One thing to realize is that you don't always
have to completely define a class before it is used.  If you
only use a pointer to class {\tt Stack} and do not access any
member functions or data from the class, you can write, in lieu of 
including {\tt stack.h}:
\begin{verbatim}
class Stack;
\end{verbatim}
This will tell the compiler all it
needs to know to deal with the pointer.  In a few cases this won't work,
and you will have to move stuff around or alter your definitions.

\item Use {\tt ASSERT} statements liberally to check that your program
is behaving properly.  An assertion is a condition that if
FALSE signifies that there is a bug in the program;
{\tt ASSERT} tests an expression and aborts if the condition is
false.  We used {\tt ASSERT} above in {\tt Stack::Push()} to check 
that the stack wasn't full. The idea is to catch errors as early
as possible, when they are easier to locate, instead of waiting until 
there is a user-visible symptom of the error (such as a segmentation 
fault, after memory has been trashed by a rogue pointer).

Assertions are particularly useful at the beginnings and ends of 
procedures, to check that the procedure was called with the right 
arguments, and that the procedure did what it is supposed to.
For example, at the beginning of List::Insert, you could assert that 
the item being inserted isn't already on the list, and at the end of
the procedure, you could assert that the item is now on the list.

If speed is a concern, ASSERTs can be defined to make the check
in the debug version of your program, and to be a no-op in the production
version.  But many people run with ASSERTs enabled even in production.

\item Write a module test for every module in your program.
Many programmers have the notion that testing code means running
the entire program on some sample input; if it doesn't crash, that 
means it's working, right?  Wrong.  You have no way of knowing
how much code was exercised for the test.  Let me urge you to
be methodical about testing.  Before you put a new module
into a bigger system, make sure the module works as advertised 
by testing it standalone.  If you do this for every module, 
then when you put the modules together, instead of {\em hoping}
that everything will work, you will {\em know} it will work.

Perhaps more importantly, module tests provide an opportunity
to find as many bugs as possible in a localized context.  
Which is easier: finding a bug in a 100 line program, or in a 
10000 line program?

\end{enumerate}

\section{Compiling and Debugging}

The Makefiles we will give you works only with the GNU version of
make, called ``gmake''.  You may want
to put ``alias make gmake'' in your .cshrc file.

You should use {\bf gdb} to debug your program rather than {\bf dbx}.
Dbx doesn't know how to decipher C++ names, so you will see function
names like \verb+Run__9SchedulerP6Thread+.

On the other hand, in GDB (but not DBX) when you do a stack backtrace
when in a forked thread (in homework 1), after printing out the
correct frames at the top of the stack, the debugger will sometimes
go into a loop printing the lower-most frame ({\tt ThreadRoot}), and 
you have to type control-C when it says ``more?''.  If you understand
assembly language and can fix this, please let me know.

\section{Example: A Stack of Integers}

We've provided the complete, working code for the stack example.  You should
read through it and play around with it to make sure you understand
the features of C++ described in this paper.

To compile the simple stack test, type {\tt make all} --
this will compile the simple stack test ({\tt stack.cc}), 
the inherited stack test ({\tt inheritstack.cc}), and
the template version of stacks ({\tt templatestack.cc}).

\section{Epilogue}

I've argued in this note that you should avoid using certain C++ 
and C features.  But you're probably thinking I must be leaving 
something out -- if someone put the
feature in the language, there must be a good reason, right?  I believe that
every programmer should strive to write code whose behavior would be
immediately obvious to a reader;
if you find yourself writing code that would require someone reading the code
to thumb through a manual in order to understand it, you are almost certainly
being way too subtle.  There's probably a much simpler and more obvious
way to accomplish the same end.  Maybe the code will be a little longer
that way,
but in the real world, it's whether the code works and how simple it is for
someone else to modify, that matters a whole lot more than how many
characters you had to type.

A final thought to remember:

\begin{quote}
``There are two ways of constructing a software design: one way is to
make it so simple that there are {\em obviously} no deficiencies and
the other way is to make it so complicated that there are no {\em
obvious} deficiencies.'' \\ \hbox{} \hfill C. A. R. Hoare, ``The Emperor's
Old Clothes'', CACM Feb. 1981
\end{quote}

\section{Further Reading}

\begin{itemize}
\item[] James Coplien, ``Advanced C++'', Addison-Wesley.
This book is only for experts, but it has some good ideas in it,
so keep it in mind once you've been programming in C++ for a few years.

\item[] James Gosling.  ``The Java Language.''  Online at
``http://java.sun.com/''  Java is a safe subset of C++.  It's main 
application is the safe extension of Web browsers by allowing 
you to download Java code as part of clicking on a link to 
interpret and display the document.  Safety is key here, since 
after all, you don't want to click on a Web link and have 
it download code that will crash your browser.  Java was defined 
independently of this document, but interestingly, it enforces a 
very similar style (for example, no multiple inheritance and
no operator overloading).

\item[] C.A.R. Hoare, ``The Emperor's Old Clothes.''
{\em Communications of the ACM}, Vol. 24, No. 2, February 1981,
pp. 75-83.  Tony Hoare's Turing Award lecture.  How do you build 
software that really works?  Attitude is everything -- you need
a healthy respect for how hard it is to build working software. 
It might seem that addding this whiz-bang feature is only 
``a small matter of code'', but that's the path to late, buggy
products that don't work.

\item[] Brian Kernighan and Dennis Ritchie, ``The C Programming Language'',
Prentice-Hall.  The original C book -- a very easy read.  But the
language has evolved since it was first designed, and this book doesn't
describe all of C's newest features.  But still the best place for
a beginner to start, even when learning C++.

\item[] Steve Maguire, ``Writing Solid Code'', Microsoft Press.
How to write bug-free software; I think this should be required 
reading for all software engineers.  This really {\em will} change 
your life -- if you don't follow the recommendations in this book, 
you'll probably never write code that completely works, and you'll
spend your entire life struggling with hard to find bugs.  
There is a better way!  Contrary to the programming language types, 
this d