Abstract Data Types

Abstract data types, include files, non-inline member functions, assertions.

It is now time to design some serious classes that actually do something useful. Let's start with something simple and easy to understand--an abstract data type--stack of integers. A stack is defined by its interface. Major things that you can do to a stack is to push a number into it and pop a number from it. What makes a stack a stack, is its LIFO (Last In-First Out) behavior. You can push values into it and, when you pop them, they come up in reverse order.

Our implementation choice is to use an array of integers. It would be nice to be able to separate the interface from the implementation. In some languages it is actually possible. Not so in C++ (or, at least, not without some gymnastics). The reasons are mostly technological. The compiler would have to have knowledge about all the files involved in the project in order to allow for such separation.

In C++, the best we can do is to separate the details of the implementation of some member functions into the implementation file. The interface file, however, must contain the definition of the class, and that involves specifying all the data members. Traditionally, interfaces are defined in header files with the .h extension. Here is the stack.h interface file.

const int maxStack = 16;

class IStack
{
public:
    IStack () :_top (0) {}
    void Push (int i);
    int  Pop ();
private:
    int _arr [maxStack];
    int _top;
};

The constructor of IStack initializes the top-of-the-stack index to zero--the start of the array. Yes, in C++ array elements are numbered from zero to n-1, where n is the size of the array. In our case the size is 16. It is defined to be so in the statement

const int maxStack = 16;

The modifier const tells the compiler that the value of maxStack will never change. The compiler is therefore free to substitute every use of the symbol maxStack with the actual value of 16. And that's exactly what it does.

The line

int _arr [maxStack];

declares _arr to be an array of maxStack integers. The size of an array has to be a constant. You don't have to specify the size when the array is explicitly initialized; as we have seen in the case of strings of characters.

Notice that member functions Push and Pop are declared but not defined within the definition of the class IStack. The difference between function declaration and function definition is that the latter includes the code--the implementation--(and is not followed by a semicolon). The former does not: It only specifies the types of parameters and the type of the return value. So where is the implementation of Push and Pop? In the separate implementation file stack.cpp.

First thing in that file is the inclusion of the header stack.h, which we have just seen. Next we include the new header file cassert. This file contains the definition of the very important function assert. I will not go into the details of its implementation, suffice it to say that this magical function can be turned off completely by defining the symbol NDEBUG. However, as long as we don't define NDEBUG, the assertion checks its argument for logical truth, that is, for a non-zero value. In other words, it asserts the truth of its argument. We define NDEBUG only after the final program is thoroughly tested, and in one big swoop we get rid of all the assertions, thus improving the program's speed². What happens when the argument of the assertion is not true (or is equal to zero)? In that unfortunate case the assertion will print a message specifying the name of the source file, the line number and the condition that failed. Assertions are a debugging tool. When an assertion fails it signifies a programmer's error--a bug in the program.

We usually don't anticipate bugs, they appear in unexpected places all by themselves. However there are some focal points in our code where they can be caught. These are the places where we make assumptions. It is okay to make certain assumptions, they lead to simpler and faster code. We should however make sure, at least during development and testing, that nobody violates these assumptions. Let's have a look at the implementations of Push and Pop:

#include "stack.h" #include <cassert> #include <iostream> using std::cout; using std::endl; //compile with NDEBUG=1 to get rid of assertions void IStack::Push (int i) { assert (_top < maxStack); _arr [_top] = i; ++_top; } int IStack::Pop () { assert (_top > 0); --_top; return _arr [_top]; }

The first thing worth noticing is that, when the definition of a member function is taken out of the context of the class definition, its name has to be qualified with the class name. There's more to it than meets the eye, though. The methods we've been defining so far were all inline. Member functions whose definition is embedded inside the definition of the class are automatically made inline by the compiler. What does it mean? It means that the compiler, instead of generating a function call, will try to generate the actual code of the function right on the spot where it was invoked. For instance, since the method GetValue of the object Input was inline, it's invocation in

cout << input.GetValue ();

is, from the point of view of generated code, completely equivalent to

cout << input._num;

On the other hand, if the definition of the member function is taken out of the class definition, like in the case of Pop, it automatically becomes non-inline.

Should one use inline or non-inline methods? It depends on the complexity of the method. If it contains a single statement, it is usually cheaper execution-wise and code-size-wise to make it inline. If it's more complex, and is invoked from many different places, it makes more sense to make it non-inline.

In any case, inline functions are absolutely vital to programming in C++. Without inlining, it would be virtually impossible to convince anybody to use such methods as GetValue or SetValue instead of simply making _num public (even with inlining it is still difficult to convince some programmers). Imposing no penalty for data hiding is a tremendous strength of C++. Typing a few additional lines of code here and there, without even having to think much about it, is a price every experienced programmer is happy to pay for the convenience and power of data hiding.

The main function does a few pushes and pops to demonstrate the workings of the stack.

void main () { IStack stack; stack.Push (1); stack.Push (2); cout << "Popped " << stack.Pop() << endl; cout << "Popped " << stack.Pop() << endl; }

² Believe it or not: Failure to turn off assertions and to turn on optimizations is often the reason for false claims of C++ slowness. (Others usually involve misuse of language features.)