Here we will describe some basic features of C++ that are useful for implementing abstract data types. Like all programming languages, C++ comes with an ideology, which in this case emphasizes object-oriented features like inheritance. We will be ignoring this ideology and treating C++ as an improved version of C.

The goal here is not to teach you all of C++, which would take a while, but instead to give you some hints for why you might want to learn C++ on your own. If you decide to learn C++ for real, Bjarne Stroustrup's The C++ Programming Language is the definitive source. A classic tutorial here aimed at C programmers introduces C++ features one at a time (some of these features have since migrated into C). The web site http://www.cplusplus.com has extensive tutorials and documentation.

1. Hello world

The C++ version of "hello world" looks like this:

   1 #include <iostream>
   2 
   3 int
   4 main(int argc, const char **argv)
   5 {
   6     std::cout << "hi\n";
   7 
   8     return 0;
   9 }

Compile this using g++ instead of gcc. Make shows how it is done:

$ make helloworld
g++     helloworld.cpp   -o helloworld

Or we could use an explicit Makefile:

CPP=g++
CPPFLAGS=-g3 -Wall

helloworld: helloworld.o
        $(CPP) $(CPPFLAGS) -o $@ $^

Now the compilation looks like this:

$ make helloworld
g++  -g3 -Wall  -c -o helloworld.o helloworld.cpp
g++ -g3 -Wall -o helloworld helloworld.o

The main difference from the C version:

1. #include <stdio.h> is replaced by #include <iostream>, which gets the C++ version of the stdio library.

2. printf("hi\n") is replaced by std::cout << "hi\n". The stream std::cout is the C++ wrapper for stdout; you should read this variable name as cout in the std namespace. The << operator is overloaded for streams so that it sends its right argument out on its left argument (see the discussion of operator overloading below). You can also do things like std::cout << 37, std::cout << 'q', std::cout << 4.7, etc. These all do pretty much what you expect.

If you don't like typing std:: before all the built-in functions and variables, you can put using namespace std somewhere early in your program, like this:

   1 #include <iostream>
   2 
   3 using namespace std;
   4 
   5 int
   6 main(int argc, const char **argv)
   7 {
   8     cout << "hi\n";
   9 
  10     return 0;
  11 }

2. References

Recall that in C we sometime pass objects into function by reference instead of by value, by using a pointer:

   1 void increment(int *x)
   2 {
   3     (*x)++;
   4 }

This becomes even more useful in C++, since many of the objects we are dealing with are quite large, and can defend themselves against dangerous modifications by restricting access to their components. So C++ provides a special syntax allowing function parameters to be declared as call-by-reference rather than call-by-value. The function above could be rewritten in C++ as

   1 void increment(int &x)
   2 {
   3     x++;
   4 }

The int &x declaration says that x is a reference to whatever variable is passed as the argument to increment. A reference acts exactly like a pointer that has already had * applied to it. You can even write &x to get a pointer to the original variable if you want to for some reason.

As with pointers, it's polite to mark a reference with const if you don't intend to modify the original object:

   1 void reportWeight(const SumoWrestler &huge)
   2 {
   3     cout << huge.getWeight();
   4 }

References are also used as a return type to chain operators together; in the expression

   1     cout << "hi" << '\n';

the return type of the first << operator is an ostream & reference (as is cout); this means that the '\n' gets sent to the same object. We could make the return value be just an ostream, but then cout would be copied, which could be expensive and would mean that the copy was no longer working on the same internal state as the original. This same trick is used when overloading the assignment operator.

3. Function overloading

C++ lets you define multiple functions with the same name, where the choice of which function to call depends on the type of its arguments. Here is a program that demonstrates this feature:

   1 #include <iostream>
   2 
   3 using namespace std;
   4 
   5 const char *
   6 typeName(int x)
   7 {
   8     return "int";
   9 }
  10 
  11 const char *
  12 typeName(double x)
  13 {
  14     return "double";
  15 }
  16 
  17 const char *
  18 typeName(char x)
  19 {
  20     return "char";
  21 }
  22 
  23 int
  24 main(int argc, const char **argv)
  25 {
  26     cout << "The type of " << 3 << " is " << typeName(3) << ".\n";
  27     cout << "The type of " << 3.1 << " is " << typeName(3.1) << ".\n";
  28     cout << "The type of " << 'c' << " is " << typeName('c') << ".\n";
  29 
  30     return 0;
  31 }

And here is what it looks like when we compile and run it:

$ make functionOverloading
g++     functionOverloading.cpp   -o functionOverloading
$ ./functionOverloading 
The type of 3 is int.
The type of 3.1 is double.
The type of c is char.

Internally, g++ compiles three separate functions with different (and ugly) names, and when you use typeName on an object of a particular type, g++ picks the one whose type matches. This is similar to what happens with built-in operators in straight C, where + means different things depending on whether you apply it to a pair of ints, a pair of doubles, or a pointer and an int, but C++ lets you do it with your own functions.

4. Classes

C++ allows you to declare classes that look suspiciously like structs. The main differences between a class and a C-style struct are that (a) classes provide member functions or methods that operate on instances of the class and that are called using a struct-like syntax; and (b) classes can distinguish between private members (only accessible to methods of the class) and public members (accessible to everybody).

In C, we organize abstract data types by putting the representation in a struct and putting the operations on the data type in functions that work on this struct, often giving the functions a prefix that hints at the type of its target (mostly to avoid namespace collisions). Classes in C++ make this connection between a data structure and the operations on it much more explicit.

Here is a simple example of a C++ class in action:

   1 #include <iostream>
   2 
   3 using namespace std;
   4 
   5 /* counters can be incremented or read */
   6 class Counter {
   7     int value;            /* private value */
   8 public:
   9     Counter();            /* constructor with default value */
  10     Counter(int);         /* constructor with specified value */
  11     int read();           /* get the value of the counter */
  12     void increment();     /* add one to the counter */
  13 };
  14 
  15 Counter::Counter() { value = 0; }
  16 Counter::Counter(int initialValue) { value = initialValue; }
  17 int Counter::read() { return value; }
  18 void Counter::increment() { value++; }
  19 
  20 int
  21 main(int argc, const char **argv)
  22 {
  23     Counter c;
  24     Counter c10(10);
  25 
  26     cout << "c starts at " << c.read() << '\n';
  27     c.increment();
  28     cout << "c after one increment is " << c.read() << '\n';
  29 
  30     cout << "c10 starts at " << c10.read() << '\n';
  31     c.increment();
  32     c.increment();
  33     cout <<"c10 after two increments is " << c10.read() << '\n';
  34 
  35     return 0;
  36 }

Things to notice:

1. In the class Counter declaration, the public: label introduces the public members of the class. The member value is only accessible to member functions of Counter. This enforces much stronger information hiding than the default in C, although one can still use void * trickery to hunt down and extract supposedly private data in C++ objects.

2. In addition to the member function declarations in the class declaration, we also need to provide definitions. These look like ordinary function definitions, except that the class name is prepended using :: as in Counter::read.

3. Member functions are called using struct access syntax, as in c.read(). Conceptually, each instance of a class has its own member functions, so that c.read is the function for reading c while c10.read is the function for reading c10. Inside a member function, names of class members refer to members of the current instance; value inside c.read is c.value (which otherwise is not accessible, since c.value is not public).

4. Two special member functions are Counter::Counter() and Counter::Counter(int). These are constructors, and are identifiable as such because they are named after the class. A constructor is called whenever a new instance of the class is created. If you create an instance with no arguments (as in the declaration Counter c;), you get the constructor with no arguments. If you create an instance with arguments (as in the declaration Counter c10(10);), you get the version with the appropriate arguments. This is just another example of function overloading. If you don't define any constructors, C++ supplies a default constructor that takes no arguments and does nothing. Note that constructors don't have a return type (you don't need to preface them with void).

5. The special member function Counter::~Counter() is a destructor; it is called when an object of type Counter is de-allocated (say, when returning from a function with a local variable of this type). This particular destructor is not very useful. Destructors are mostly important for objects that allocate their own storage that needs to be de-allocated when the object is; see the section on storage allocation below.

Compiling and running this program gives the following output. Note that the last two lines are produced by the destructor.

c starts at 0
c after one increment is 1
c10 starts at 10
c10 after two increments is 10
counter de-allocated with value 10
counter de-allocated with value 3

One subtle difference between C and C++ is that C++ uses empty parentheses () for functions with no arguments, where C would use (void). This is a bit of a historical artifact, having to do with C allowing () for functions whose arguments are not specified in the declaration (which was standard practice before ANSI C).

Curiously, C++ also allows you to declare structs, with the interpretation that a struct is exactly like a class except that all members are public by default. So if you change class to struct in the program above, it will do exactly the same thing. In practice, nobody who codes in C++ does this; the feature is mostly useful to allow C code with structs to mix with C++ code.

5. Operator overloading

Sometimes when you define a new class, you also want to define new interpretations of operators on that class. Here is an example of a class that defines elements of the max-plus algebra over ints. This gives us objects that act like ints, except that the + operator now returns the larger of its arguments and the * operator now returns the sum.¹

The mechanism in C++ for doing this is to define member functions with names operatorsomething where something is the name of the operator we want to define. These member functions take one less argument that the operator they define; in effect, x + y becomes syntactic sugar for x.operator+(y) (which, amazingly, is actually legal C++). Because these are member functions, they are allowed to access members of other instances of the same class that would normally be hidden.

This same mechanism is also used to define automatic type conversions out of a type: the MaxPlus::operator int() function allows C++ to convert a MaxPlus object to an int whenever it needs to (for example, to feed it to cout). (Automatic type conversions into a type happen if you provide an appropriate constructor.)

   1 #include <iostream>
   2 #include <algorithm> // for max
   3 
   4 using namespace std;
   5 
   6 /* act like ints, except + does max and * does addition */
   7 class MaxPlus {
   8     int value;
   9 public:
  10     MaxPlus(int);
  11     MaxPlus operator+(const MaxPlus &);
  12     MaxPlus operator*(const MaxPlus &);
  13     operator int();
  14 };
  15 
  16 MaxPlus::MaxPlus(int x) { value = x; }
  17 
  18 MaxPlus 
  19 MaxPlus::operator*(const MaxPlus &other)
  20 {
  21     return MaxPlus(value + other.value);
  22 }
  23 
  24 MaxPlus 
  25 MaxPlus::operator+(const MaxPlus &other)
  26 {
  27     /* std::max does what you expect */
  28     return MaxPlus(max(value, other.value));
  29 }
  30 
  31 MaxPlus::operator int() { return value; }
  32 
  33 int
  34 main(int argc, const char **argv)
  35 {
  36     cout << "2+3 == " << (MaxPlus(2) + MaxPlus(3)) << '\n';
  37     cout << "2*3 == " << (MaxPlus(2) * MaxPlus(3)) << '\n';
  38 
  39     return 0;
  40 }

Avoid the temptation to overuse operator overloading, as it can be dangerous if used to obfuscate what an operator normally does:

   1 MaxPlus::operator--() { godzilla.eat(tokyo); }

The general rule of thumb is that you should probably only do operator overloading if you really are making things that act like numbers (yes, cout << violates this).

Automatic type conversions can be particularly dangerous. The line

   1     cout << (MaxPlus(2) + 3) << '\n';

is ambiguous: should the compiler convert MaxPlus(2) to an int using the MaxPlus(int) constructor and use ordinary integer addition or convert 3 to a MaxPlus using MaxPlus::operator int() and use funky MaxPlus addition? Fortunately most C++ compilers will complain about the ambiguity and fail rather than guessing wrong.

6. Templates

One of the things we kept running into in CS223 was that if we defined a container type like a hash table, binary search tree, or priority queue, we had to either bake in the type of the data it held or do horrible tricks with void * pointers to work around the C type system. C++ includes a semi-principled work-around for this problem known as templates. These are essentially macros that take a type name as an argument, that are expanded as needed to produce functions or classes with specific types (see C/Macros for an example of how to do this if you only have C).

Typical use is to prefix a definition with template <class T> and then use T as a type name throughout:

   1 template <class T>
   2 T add1(T x)
   3 {
   4     return x + ((T) 1);
   5 }

Note the explicit cast to T of 1; this avoids ambiguities that might arise with automatic type conversions.

If you put this definition in a program, you can then apply add1 to any type that has a + operator and that you can convert 1 to. For example, the output of this code fragment:

   1     cout << "add1(3) == " << add1(3) << '\n';
   2     cout << "add1(3.1) == " << add1(3.1) << '\n';
   3     cout << "add1('c') == " << add1('c') << '\n';
   4     cout << "add1(MaxPlus(0)) == " << add1(MaxPlus(0)) << '\n';
   5     cout << "add1(MaxPlus(2)) == " << add1(MaxPlus(2)) << '\n';

is

add1(3) == 4
add1(3.1) == 4.1
add1('c') == d
add1(MaxPlus(0)) == 1
add1(MaxPlus(2)) == 2

By default, C++ will instantiate a template to whatever type fits in its argument. If you want to force a particular version, you can put the type in angle brackets after the name of whatever you defined. For example,

   1     cout << "add1<int>(3.1) == " << add1<int>(3.1) << '\n';

produces

add1<int>(3.1) == 4

because add1<int> forces its argument to be converted to an int (truncating to 3) before adding one to it.

Because templates are really macros that get expanded as needed, it is common to put templates in header (.h) files rather than in .cpp files. See the stack implementation below for an example of this.

7. Exceptions

C provides no built-in mechanism for signaling that something bad happened. So C programmers are left to come up with ad-hoc mechanisms like:

1. Calling abort to kill the program, either directly or via assert.

2. Calling exit with a nonzero exit code.

3. Returning a special error value from a function. This is often done in library routines, because it's rude for a library routine not to give the caller a chance to figure out how to deal with the error. But it means coming up with some special error value that won't be returned normally, and these can vary widely from one routine to another (null pointers, -1, etc.)

C++ provides a standard mechanism for signaling unusual events known as exceptions. The actual mechanism is similar to return: the throw statement throws an exception that may be caught by a try..catch statement anywhere above it on the execution stack (not necessarily in the same function). Example:

   1 #include <iostream>
   2 
   3 using namespace std;
   4 
   5 int fail()
   6 { 
   7     throw "you lose";
   8 
   9     return 5;
  10 }
  11 
  12 int
  13 main(int argc, const char **argv)
  14 {
  15     try {
  16         cout << fail() << '\n';
  17     } 
  18     catch(const char *s) {
  19         cerr << "Caught error: " << s << '\n';
  20     }
  21 
  22     return 0;
  23 }

In action:

$ make exception
g++  -g3 -Wall   exception.cpp   -o exception
$ ./exception
Caught error: you lose

Note the use of cerr instead of cout. This sends the error message to stderr.

A try..catch statement will catch an exception only if the type matches the type of the argument to the catch part of the statement. This can be used to pick and choose which exceptions you want to catch. See http://www.cplusplus.com/doc/tutorial/exceptions/ for some examples and descriptions of some C++ standard library exceptions.

8. Storage allocation

C++ programs generally don't use malloc and free, but instead use the built-in C++ operators new and delete. The advantage of new and delete is that they know about types: not only does this mean that you don't have to play games with sizeof to figure out how much space to allocate, but if you allocate a new object from a class with a constructor, the constructor gets called to initialize the object, and if you delete an object, its destructor (if it has one) is called.

There are two versions of new and delete, depending on whether you want to allocate just one object or an array of objects, plus some special syntax for passing constructor arguments:

• To allocate a single object, use new type.

• To allocate an array of objects, use new type[size]. As with malloc, both operations return a pointer to type.

• If you want to pass arguments to a constructor for type, use new type(args). This only works with the single-object version, so you can't do new SomeClass[12] unless SomeClass has a constructor that takes no arguments.

• To de-allocate a single object, use delete pointer-to-object.

• To de-allocate an array, use delete [] pointer-to-base-of-array. Mixing new with delete [] or vice versa is an error that may or may not be detected by the compiler. Mixing either with malloc or free is a very bad idea.

The program below gives examples of new and delete in action:

   1 #include <iostream>
   2 #include <cassert>
   3 
   4 using namespace std;
   5 
   6 int
   7 main(int argc, const char **argv)
   8 {
   9     int *p;
  10     int *a;
  11     const int n = 100;
  12 
  13     p = new int;
  14     a = new int[n];
  15 
  16     *p = 5;
  17     assert(*p == 5);
  18 
  19     for(int i = 0; i < n; i++) {
  20         a[i] = i;
  21     }
  22 
  23     for(int i = 0; i < n; i++) {
  24         assert(a[i] == i);
  25     }
  26 
  27     delete [] a;
  28     delete p;
  29 
  30     return 0;
  31 }

8.1. Storage allocation inside objects

Inside objects, storage allocation gets complicated. The reason is that if the object is copied, either by an assignment or by being passed as a call-by-value parameter, the storage pointed to by the object will not be copied. This can lead to two different objects that share the same internal data structures, which is usually not something you want. Furthermore, when the object is deallocated, it's necessary to also deallocate any space it allocated, which can be done inside the object's destructor.

To avoid all these problems, any object of type T that uses new needs to have all of:

1. A destructor T::~T().

2. A copy constructor T::T(const T &), which is a constructor that takes a reference to another object of the same type as an argument and copies its contents.

3. An overloaded assignment operator T::operator=(const T &) that does the same thing, but also deallocates any internal storage of the current object before copying new data in place of it (or possibly just copies the contents of internal storage without doing any allocation and deallocation). The overloaded assignment operator is particularly tricky, because you have to make sure it doesn't destroy the contents of the object if somebody writes the useless self-assignment a = a, and you also need to return a reference to *this so that you can chain assignments together as in a = b = c.

Here is an example of a Stack class that includes all of these members. Note that it is defined using templates so we can make a stack of any type we like.

   1 template <class T>
   2 class Stack {
   3     static const int initialSize = 32;   /* static means this is shared across entire class */
   4     int top;
   5     int size;
   6     T* contents;
   7 public:
   8     Stack();          /* create a new empty stack */
   9 
  10     /* the unholy trinity of complex C++ objects */
  11     ~Stack();         /* destructor */
  12     Stack(const Stack &);     /* copy constructor */
  13     Stack& operator=(const Stack &); /* overloaded assignment */
  14 
  15     void push(T);     /* push an element onto the stack */
  16     int isEmpty();    /* return 1 if empty */
  17     T pop();          /* pop top element from stack */
  18 };
  19 
  20 template <class T>
  21 Stack<T>::Stack() 
  22 { 
  23     size = initialSize;
  24     top = 0;
  25     contents = new T[size];
  26 }
  27 
  28 template <class T> 
  29 Stack<T>::~Stack()
  30 { 
  31     delete [] contents;
  32 }
  33 
  34 template <class T>
  35 Stack<T>::Stack(const Stack<T> &other)
  36 {
  37     size = other.size;
  38     top = other.top;
  39     contents = new T[size];
  40 
  41     for(int i = 0; i < top; i++) {
  42         contents[i] = other.contents[i];
  43     }
  44 }
  45 
  46 template <class T>
  47 Stack<T> &
  48 Stack<T>::operator=(const Stack<T> &other)
  49 {
  50     if(&other != this) {
  51         /* this is a real assignment */
  52 
  53         delete [] contents;
  54 
  55         size = other.size;
  56         top = other.top;
  57         contents = new T[size];
  58 
  59         for(int i = 0; i < top; i++) {
  60             contents[i] = other.contents[i];
  61         }
  62     }
  63     
  64     return *this;
  65 }
  66 
  67 template <class T>
  68 void 
  69 Stack<T>::push(T elt)
  70 {
  71     if(top >= size) {
  72         int newSize = 2*size;
  73         T *newContents = new T[newSize];
  74 
  75         for(int i = 0; i < top; i++) {
  76             newContents[i] = contents[i];
  77         }
  78 
  79         delete [] contents;
  80 
  81         contents = newContents;
  82         size = newSize;
  83     }
  84         
  85     contents[top++] = elt;
  86 }
  87 
  88 template <class T>
  89 T
  90 Stack<T>::pop()
  91 {
  92     if(top > 0) {
  93         return contents[--top];
  94     } else {
  95         throw "stack empty";
  96     }
  97 }

   1 #include <iostream>
   2 
   3 #include "stack.h"
   4 
   5 using namespace std;
   6 
   7 int
   8 main(int argc, const char **argv)
   9 {
  10     Stack<int> s;
  11     Stack<int> s2;
  12 
  13     try {
  14         s.push(1);
  15         s.push(2);
  16         s.push(3);
  17 
  18         s2 = s;
  19 
  20         cout << s.pop() << '\n';
  21         cout << s.pop() << '\n';
  22         cout << s.pop() << '\n';
  23 
  24         cout << s2.pop() << '\n';
  25         cout << s2.pop() << '\n';
  26         cout << s2.pop() << '\n';
  27 
  28         try {
  29             s2.pop();
  30         } catch(const char *err) {
  31             cout << "Caught expected exception " << err << '\n';
  32         }
  33 
  34         for(int i = 0; i < 1000; i++) {
  35             s.push(i);
  36         }
  37 
  38         cout << s.pop() << '\n';
  39     } catch(const char *err) {
  40         cerr << "Caught error " << err << '\n';
  41     }
  42 
  43     return 0;
  44 }

9. Standard library

C++ has a large standard library that includes implementations of many of the data structures we've seen in CS223. In most situations, it is easier to use the standard library implementations than roll your own, although you have to be careful to make sure you understand just what the standard library implementations do. For example, here is a reimplementation of the main routine from stack.cpp using the stack template from #include <stack>.

   1 #include <iostream>
   2 #include <stack>
   3 
   4 using namespace std;
   5 
   6 int
   7 main(int argc, const char **argv)
   8 {
   9     stack<int> s;
  10     stack<int> s2;
  11 
  12     s.push(1);
  13     s.push(2);
  14     s.push(3);
  15 
  16     s2 = s;
  17 
  18     cout << s.top() << '\n'; s.pop();
  19     cout << s.top() << '\n'; s.pop();
  20     cout << s.top() << '\n'; s.pop();
  21 
  22     cout << s2.top() << '\n'; s2.pop();
  23     cout << s2.top() << '\n'; s2.pop();
  24     cout << s2.top() << '\n'; s2.pop();
  25 
  26     for(int i = 0; i < 1000; i++) {
  27         s.push(i);
  28     }
  29 
  30     cout << s.top() << '\n';
  31 
  32     return 0;
  33 }

One difference between the standard stack and our stack is that std::stack's pop member function doesn't return anything. So we have to use top to get the top element before popping it.

There is a chart of all the standard library data structures at http://www.cplusplus.com/reference/stl/.

10. Things we haven't talked about

The main thing we've omitted here is any discussion of object-oriented features of C++, particularly inheritance. These are not immediately useful for the abstract-data-type style of programming we've used in CS223, but can be helpful for building more complicated systems, where we might want to have various specialized classes of objects that can all be approached using a common interface represented by a class that they inherit from. If you are interested in exploring these tools further, the CS department occasionally offers a class on object-oriented programming; Mike fischer's lecture notes from the last time this course was offered can be found at http://zoo.cs.yale.edu/classes/cs427/2011a/lectures.html.

CategoryProgrammingNotes