c++.tex

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

function, we really don't need to look at the {\tt top} or {\tt stack}
members outside of the class -- in fact, we'd rather that users of the Stack
abstraction {\em not} know about its internal implementation, in case
we change it.  Thus we can rewrite the class as follows:

\begin{verbatim}
class Stack {
  public:
    void Push(int value); // Push an integer, checking for overflow.
    bool Full();       // Returns TRUE if the stack is full, FALSE otherwise.
  private:
    int top;          // Index of the top of the stack.
    int stack[10];    // The elements of the stack.
};
\end{verbatim}

Before, given a pointer to a {\tt Stack} object, say {\tt s}, any part
of the program could access {\tt s->top}, in potentially bad ways.
Now, since the {\tt top} member is private, only a member function,
such as {\tt Full()}, can access it.  If any other part of the
program attempts to use {\tt s->top} the compiler will report an error.

You can have alternating {\tt public:} and {\tt private:} sections in
a class.  Before you specify either of these, class members are
private, thus the above example could have been written:

\begin{verbatim}
class Stack {
    int top;          // Index of the top of the stack.
    int stack[10];    // The elements of the stack.
  public:
    void Push(int value); // Push an integer, checking for overflow.
    bool Full();       // Returns TRUE if the stack is full, FALSE otherwise.
};
\end{verbatim}

Which form you prefer is a matter of style, but it's usually best
to be explicit, so that it is obvious what is intended.  In Nachos,
we make everything explicit.

What is not a matter of style: {\bf all data members of a class 
should be private.}  All operations on data should be via that
class' member functions.  Keeping data private adds to the modularity 
of the system, since you can redefine how the data members are stored 
without changing how you access them.

\item {\bf Constructors and the operator new.}  In C, in
order to create a new object of type {\tt Stack}, one might write:

\begin{verbatim}
    struct Stack *s = (struct Stack *) malloc(sizeof (struct Stack));
    InitStack(s, 17);
\end{verbatim}

The {\tt InitStack()} function might take the second argument as the
size of the stack to create, and use {\tt malloc()} again to get an
array of 17 integers.

The way this is done in C++ is as follows:

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

The {\tt new} function takes the place of {\tt malloc()}.  To
specify how the object should be initialized, one declares a {\it
constructor} function as a member of the class, with the name of the
function being the same as the class name:

\begin{verbatim}
class Stack {
  public:
    Stack(int sz);    // Constructor:  initialize variables, allocate space.
    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.
};

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

There are a few things going on here, so we will describe them one at
a time.

The {\tt new} operator automatically creates (i.e. allocates) the object
and then calls the constructor function for the new object.
This same sequence happens even if, for instance, you declare an object
as an automatic variable inside a function or block -- the compiler allocates
space for the object on the stack, and calls the constructor function on it.

In this example, we create two stacks of different sizes, one
by declaring it as an automatic variable, and one by using {\tt new}.

\begin{verbatim}
void
test() {
    Stack s1(17);
    Stack* s2 = new Stack(23);
}
\end{verbatim}

Note there are two ways of providing arguments to constructors: with
{\tt new}, you put the argument list after the class name, and with
automatic or global variables, you put them after the variable name.

It is crucial that you {\bf always} define a constructor
for every class you define, and that the constructor initialize
{\bf every} data member of the class.  If you don't define 
your own constructor, the compiler will automatically define
one for you, and believe me, it won't do what you want
(``the unhelpful compiler'').
The data members will be initialized to random, unrepeatable
values, and while your program may work anyway, it might not
the next time you recompile (or vice versa!).

As with normal C variables, variables declared inside a function
are deallocated automatically when the function returns; for  
example, the {\tt s1} object is deallocated when {\tt test}
returns.  Data allocated with {\tt new} (such as {\tt s2}) is 
stored on the heap, however, and remains after the function returns;
heap data must be explicitly disposed of using {\tt delete}, described below.  

The {\tt new} operator can also be used to allocate arrays, illustrated
above in allocating an array of {\tt ints}, of dimension {\tt size}:

\begin{verbatim}
    stack = new int[size];
\end{verbatim}

Note that you can use {\tt new} and {\tt delete} (described below)
with built-in types like {\tt int} and {\tt char} as well as with
class objects like {\tt Stack}.

\item {\bf Destructors and the operator delete.}  Just as {\tt new} is the
replacement for {\tt malloc()}, the replacement for {\tt free()} is
{\tt delete}.  To get rid of the {\tt Stack} object we allocated
above with {\tt new}, one can do:

\begin{verbatim}
    delete s2;
\end{verbatim}

This will deallocate the object, but first it will call the
{\it destructor} for the {\tt Stack} class, if there is one.  This
destructor is a member function of {\tt Stack} called {\tt {\verb^~^}Stack()}:

\begin{verbatim}
class Stack {
  public:
    Stack(int sz);    // Constructor:  initialize variables, allocate space.
    ~Stack();         // 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.
};

Stack::~Stack() {
    delete [] stack;  // delete an array of integers
}
\end{verbatim}

The destructor has the job of deallocating the data the constructor
allocated.  Many classes won't need destructors, and some will use
them to close files and otherwise clean up after themselves.

The destructor for an object is called when the object is deallocated.
If the object was created with {\tt new}, then you must call
{\tt delete} on the object, or else the object will continue
to occupy space until the program is over -- this is called
``a memory leak.''  Memory leaks are bad things -- although virtual
memory is supposed to be unlimited, you can in fact run out of it --
and so you should be careful to {\bf always} delete what you allocate.
Of course, it is even worse to call {\tt delete} too early --
{\tt delete} calls the destructor and puts the space back on the heap 
for later re-use.  If you are still using the object, you will
get random and non-repeatable results that will be very difficult
to debug.  In my experience, using data that has already been deleted 
is major source of hard-to-locate bugs in student (and professional)
programs, so hey, be careful out there!

If the object is an automatic, allocated on the execution stack
of a function, the destructor will be called and the space deallocated when
the function returns; in the {\tt test()} example above, {\tt s1}
will be deallocated when {\tt test()} returns, without you having to
do anything.

In Nachos, we always explicitly allocate and deallocate objects with 
{\tt new} and {\tt delete}, to make it clear when the constructor and
destructor is being called.  For example, if an object contains another 
object as a member variable, we use
{\tt new} to explicitly allocated and initialize the member variable,
instead of implicitly allocating it as part of the containing object.
C++ has strange, non-intuitive rules for the order in which the 
constructors and destructors are called when you implicitly allocate 
and deallocate objects.  In practice, although simpler, explicit allocation 
is slightly slower and it makes it more likely that you will forget 
to deallocate an object (a bad thing!), and so some would disagree with 
this approach.

When you deallocate an array, you have to tell the compiler that
you are deallocating an array, as opposed to a single element in the array.
Hence to delete the array of integers in {\tt Stack::{\verb^~^}Stack}:

\begin{verbatim}
    delete [] stack;
\end{verbatim}

\end{enumerate}

\subsection{Other Basic C++ Features}

Here are a few other C++ features that are useful to know.

\begin{enumerate}

\item When you define a {\tt class Stack}, the name {\tt Stack} becomes
usable as a type name as if created with {\tt typedef}.  The same is
true for {\tt enum}s.

\item You can define functions inside of a {\tt class} definition,
whereupon they become {\it inline functions}, which are expanded in
the body of the function where they are used.  The rule of thumb to
follow is to only consider inlining one-line functions, and even then 
do so rarely.  

As an example, we could make the {\tt Full} routine an inline.

\begin{verbatim}
class Stack {
   ...
   bool Full() { return (top == size); };
   ...
};
\end{verbatim}

There are two motivations for inlines: convenience
and performance.  If overused, inlines can make your code more confusing,
because the implementation for an object is no longer in one place, 
but spread between the {\tt .h} and {\tt .c} files.  Inlines can sometimes
speed up your code (by avoiding the overhead of a procedure call), but 
that shouldn't be your principal concern as a student (rather, at least to 
begin with, you should be most concerned with writing code that is simple 
and bug free).  Not to mention that inlining sometimes slows down a program,
since the object code for the function is duplicated wherever the function 
is called, potentially hurting cache performance.

\item Inside a function body, you can declare some variables, execute
some statements, and then declare more variables.  This can make code
a lot more readable.  In fact, you can even write things like:

\begin{verbatim}
for (int i = 0; i < 10; i++) ;
\end{verbatim}

Depending on your compiler, however, the variable {\tt i} may still visible
after the end of the {\tt for}
loop, however, which is not what one might expect or desire.

\item Comments can begin with the characters \verb+//+ and extend to
the end of the line.  These are usually more handy than the
\verb+/* */+ style of comments.

\item C++ provides some new opportunities to use the 
{\tt const} keyword from ANSI C.  The basic idea of {\tt const}
is to provide extra information to the compiler about how a variable
or function is used, to allow it to flag an error if it is being 
used improperly.  You should always look for ways to get the compiler 
to catch bugs for you.  After all, which takes less time?  Fixing
a compiler-flagged error, or chasing down the same bug using gdb?  

For example, you can declare that a member function only reads the 
member data, and never modifies the object:

\begin{verbatim}
class Stack {
   ...
   bool Full() const;  // Full() never modifies member data
   ...
};
\end{verbatim}

As in C, you can use {\tt const} to declare that a variable is never 
modified:

\begin{verbatim}
    const int InitialHashTableSize = 8;
\end{verbatim}

This is {\em much} better than using {\tt \#define} for constants,
since the above is type-checked.

\item Input/output in C++ can be done with the {\tt >>} and {\tt <<}
operators and the objects {\tt cin} and {\tt cout}.  For example,
to write to {\tt stdout}:

\begin{verbatim}
    cout << "Hello world!  This is section " << 3 << "!";
\end{verbatim}

This is equivalent to the normal C code