Introduction

This document explains what is expected of you on the projects. These guidelines are intended to help you produce a correct project submission as well as develop good coding habits.

Pay special attention to text that is boxed, as in the following guideline.

To see an example of a simple project that follows these guidelines, look at the files in here.

Requirements for container classes

• Default constructor
• Destructor
• Copy constructor
• Assignment operator (operator=)
• size (returns number of items in container)
• max_size (returns max. number of items container can hold)
• empty (returns true if container hold no items)
• swap (exchanges the values of two containers efficiently)
• Comparison (operator== and operator!=)
• Iterators (begin and end)
• Const iterators (begin and end again)
• erase (removes element pointed at by iterator)
• insert (adds element immed. before iterator)

In some cases one or more of these may not make sense for the class, or the default version may be acceptable. You must provide a comment to this effect when omitting any of the required member functions.

Requirements for iterator classes

• Default constructor
• Destructor
• Copy constructor
• Assignment operator
• Dereference (operator*)
• Comparison (operator== and operator!=)
• Pre- and post-increment (operator++)
• Pre- and post-decrement (operator--)
• Random access operations: operator+(int), operator-(int), operator-(iterator)
• Conversion from iterator (const_iterator only)

Some iterators may not support all of the above (for example, foward iterators would not support the decrement or random access operations).

Miscellaneous coding rules

Often it is useful to have constructors that take arguments; for example, to provide the size of a container:

template <class T>
class container {
 ...
  container(int sz) { ... }  
};

container c;
c = 1;       // Convert integer to a container?

Any function argument that is not meant to be modified should be declared const. Any member function that does not modify its object should be declared const. Any function that returns a temporary should return const.

The standard library (aka the STL) provides a large number of generic data structures and algorithms. Using them will make your coding easier, more readable, and more efficient.

A primary theme in the standard library (and in this course) is the concept of iterators, which work like plain old pointers. Iterators are the key to using the generic algorithms in the standard library effectively.

Note that if you have already implemented the member function operator==, then it is trivial to write:

template <class T>
class container {
 ...
  bool operator!=(const container & c) const { return !operator==(c); }
};

Likewise, if you already have implemented pre-increment, you can write:

const T operator++(int)()
{
  T old(*this);
  ++*this;
  return old;
}

The standard library is now contained in a namespace called std. To use the name of a standard component, for example cout, you must do either one or the other of the following:

• Qualify the name with the namespace: std::cout everywhere you use it.
• Provide the declaration: using std::cout and then you can just type cout everywhere.

If you only need to specify a component once or a few times, the first option is probably best. Use the second option for names that you use a lot, like cout, cin, and endl.

You may be tempted to put using namespace std; at the top of all your files. Do not do this!

The return type of the main function is always int (even though some compilers will allow other types). Main either takes no parameters, or the two parameters argc and argv following the C convention. You main function should always look like one or the other of the following:

int main() 
{ 
  ... 
}

int main(int argc, char * argv[])
{
  ...
}

Coding style and comments

Comments should help you to understand the code. They are especially useful when you return to code after a period of time and are no longer familiar with it, or when someone other than the original author is looking at the code.

When writing comments, write what you would say if you were explaining the code to someone else. Do not write obvious comments like the following:

// Increment the variable 'x'.
++x;

Instead, try to provide insight as to what the code is intended to do at a higher level:

// Find the in-order successor 's' of the node 'x'.
assert(x->right_child);
node * s = right_child;
while (s->left_child)
  s = s->left_child;

In certain situations comments are always required:

An exception to the last point above are constructors, destructors, copy constructors, assignment operators, and any other required functions such as size, empty, swap, etc.

It is recommended that you name your C++ source files using the extension ".cxx" and your include files using the extension ".h".

One piece of advice: although it is good practice to separate interface and implementation into .h and .cxx files, this can cause problems with some compilers. For this course, make put both into a single .h file.

Use of assert

Every data structure has an invariant, a collection of properties that are true about it. (For example, the invariant of a binary tree is that the key of each node is greater than the key of every node in its left subtree, and less than the key of every node in its right subtree.)

Properties that must be true should be specified using the assert macro. (To use this macro in your code you must include the header <cassert>). For example, to specify the property that a must be less than b we would write:

assert(a < b);

Such an assertion will produce a message at run time if the property does not hold. This almost certainly indicates a bug in your program.

Sometimes a property is so complicated that it would be difficult or impossible to write a formal assertion for it. We will still document such cases by writing an assertion that contains a short string literal describing the property. For example, below we could have saved the original size of the container in a local variable for later comparison, but this would be inefficient and confusing. Instead we write:

template <class T>
class container {
 ...

  void insert(T x) {
    ...
    assert("size of container increased by one");
  }

This trick works because the string literal has a non-zero (pointer) value, which is converted to true in C++.

For algorithms, it is often useful to talk about pre-conditions and post-conditions, properties that are true before and (respectively) after the algorithm is performed. As with the invariant, these can be documented and checked at run time by placing appropriate assertions at the begining and end of the function implementing the algorithm.

Often the algorithm we are interested in performs an operation on a data structure. In this case the invariant is part of both the pre- and post-condition. Since the invariant returns true or false, it can be checked using an assertion like any other property.

There are several exceptions to the above rule. For constructors, it only makes sense to provide a post-condition; likewise, destructors should only provide a pre-condition. The assignment operator and copy constructor (as well as any other public member function taking a member of the class as an argument) should check the invariant for the argument, too. Member functions that are declared const need not check the invariant in the post-condition, since the value of the object will not have changed since it was checked in the pre-condition.

You may find it useful (although it is not required) to add pre- and post-condition assertions to private member functions as well.

One note of caution: if you are not careful you can end up with infinite recursion. Consider the following example.

template <class T>
class container {
public:
  int size() const {
    assert(invariant());
    // Check other pre-conditions and compute and return size...
  }
private:
  bool invariant() const {
    assert(size() >= 0);  // Container cannot have negative size.
  }
};

Error checking

For example, before removing an item from a container, obviously it is a requirement that the container not be empty. This is an external requirement, so we would not write:

assert(!empty());   // Wrong!

Instead, we write:

if (!empty())
  throw container_empty();  // Correct!

The call following the throw statement invokes the constructor of an exception class that must be declared. Exception classes are simply empty classes with meaningful names.

class container_empty {};  // Empty class.

If the error occurs while your program is running, it will terminate cleanly. Exceptions can also be caught to allow the program to handle the error itself.

Test cases

A test case should execute within a try-block, and any exceptions that are thrown should be reported as a failure (except, of course, if the test is checking for a particular exception to be thrown).

In addition to printing an appropriate message indicating if the test case passed or failed (and if it failed, why), the main function of a test case should return zero if the test passed and one if it failed. This allows the makefile to automatically flag failed tests.

See the sample files for examples of test cases.

Certain numbers and types of test cases will be required for every project.

A good way to build up a collection of test cases is to write one whenever you encounter a bug. Write a test case that exposes the bug in your code, use the test case code to fix the bug, and then rely on the test case to check that the bug does not return.

Another way to generate useful test cases is to think about the "boundary conditions". For example, does a container work correctly when it is empty? When it is full? Does an iterator work correctly when it is at the begining and end of its container?

Makefile

Use the sample makefile as a guide, and learn how to construct your own.