C++ Programming
Part I: INFO1-CE9264 / Y12.1003
Part II: INFO1-CE9265 / Y12.1004
Part III: INFO1-CE9266
Syllabus

Introduction

This series of three courses is named “C++ Programming”, offered for both credit and no credit.
      Part I: INFO1-CE9264 / Y12.1003
      Part II: INFO1-CE9265 / Y12.1004
      Part III: INFO1-CE9266

The three courses share the same home page, which may be accessed as
http://i5.nyu.edu/~mm64/INFO1-CE9264/
http://i5.nyu.edu/~mm64/INFO1-CE9265/
http://i5.nyu.edu/~mm64/INFO1-CE9266/

These courses are offered by
New York University
School of Continuing and Professional Studies
Department of Information Technologies

Current semester dates, times, rooms: see Mark Meretzky.

This document

This document contains only an outline of the topics covered. The entire content of the course is free and online right now at
http://i5.nyu.edu/~mm64/book/
The current version of this document (September 16, 2013) is online in triplicate at
http://i5.nyu.edu/~mm64/INFO1-CE9264/syllabus.html
http://i5.nyu.edu/~mm64/INFO1-CE9265/syllabus.html
http://i5.nyu.edu/~mm64/INFO1-CE9266/syllabus.html
If you are reading a copy from any other source, it may already be out of date.

Instructor

Mark Meretzky has no office, and hence no office hours, but answers questions via email. He has taught C, C++, Java, Javascript, Ruby on Rails, iPhone programming in Objective-C, Android programming in Java, Unix, Networking, and Calculus at NYU.
mark.meretzky@nyu.edu
http://i5.nyu.edu/~mm64/

Catalog Descriptions

I wrote the following catalog descriptions for this three-semester course.

C++ Part I INFO1-CE9264 / Y12.1003

From online gaming services to global real-time trading systems, C++ is the language of choice for complex, large-scale applications that demand peak performance. This three-part course teaches you the techniques for creating bigger classes and objects out of smaller ones, in Part I with aggregation, in Part II with inheritance, and in Part III with templates. Part I covers the non-object topics of C++: standard i/o, expression evaluation, placement of declarations, type conversion, pointers and references, C functions called from a C++ program, function name overloading, default values for function arguments, and inline functions. You then build classes and objects without inheritance, using data members, member functions, constructors, destructors, friend functions, arrays of objects, constant and static members, pointers to members, aggregation, and operator overloading. Large-scale programming exercises. Prerequisite: knowledge of pointers and structures in the language C.

C++ Part II INFO1-CE9265 / Y12.1004

Make a long-term investment in your future as a developer with this three-semester course. Pick up from Part I with three applications of operator overloading: formatted and file i/o, dynamic memory allocation, and standard containers such as vector, list, and string. Then concentrate on building classes using the different varieties of inheritance: single and multiple, virtual and non-virtual, public and private, and inheritance from an abstract base class with pure virtual functions. See how object-oriented design results in maintainable, extensible architectures; also explore the implementations of, and alternatives to, inheritance. Report and recover from runtime errors by throwing and catching exceptions. Large-scale programming exercises. Prerequisite: C++ Part I INFO1-CE9264.

C++ Part III INFO1-CE9266

See how the problems plaguing inherently difficult programming projects are solved with the C++ Standard Template Library (STL) in Part III of this three-semester course. Deploy template functions and template classes, and explore their interaction with the inheritance in Part II. Master the design of the Standard Template Library: containers, iterators, and algorithms; iterator traits and iterator categories, predicates and other function objects, and adapters. Learn how the STL delivers performance competitive with hand-crafted assembly language; decipher the library error messages by tracing how the algorithms are dispatched. Exploit iterators and other design patterns to achieve a loosely coupled architecture for migrating software to new environments and international locales. Large-scale programming exercises. Prerequisite: C++ Part II INFO1-CE9265.

Prerequisites

This is a series of courses for people who already know C. The following is an exact definition of how much C you need to know before beginning Part I. You must know how to use a pointer, a structure, and a pointer to a structure; and you must be able to pass the latter as an argument to a function. You must also know the pairs of C functions fopen/fclose and malloc/free. All of this will be reviewed in C++ Part I using the examples at
http://i5.nyu.edu/~mm64/INFO1-CE9264/src/

The prerequisite for Part II is Part I. The prerequisite for Part III is Part II.

How these courses fit into the certificate

See the Certificate in C++ Programming.

What to purchase for this course

Nothing. The textbook for the course is free and online at
http://i5.nyu.edu/~mm64/INFO1-CE9236/src/
http://i5.nyu.edu/~mm64/book/
You don’t have to buy it, but you’ll have to print it out or bring it on a laptop as we cover it, chapter by chapter, in class.

You can use any C and C++ compiler, including Microsoft, Borland, Sun, or GNU, on any platform. Free GNU compilers are available online from Bloodshed. If you don’t already have a computer (or even if you do), you get free access to the GNU C and C++ compilers on the Sun Solaris Unix machine i5.nyu.edu, which can be used at any of the computer labs on campus, or at your home or work by logging into it from your PC or Mac. The necessary communications software (PuTTY or ssh respectively) is free.

Examinations and major assignments

There are no exams. I can serve you better by using all 35 hours of class time per part to tell you about C++ and to entertain questions.

There will be many individual homeworks, all of them C or C++ programs. For each program, hand in the program itself and the output thereof on paper, one week after it was assigned. (You can postal mail it to me at NYU if you’re going to be absent.) I will return each homework to you one week after you hand it in, with every error corrected. (Eager beavers can have their homework corrected and returned to them on the night they hand it in, during the intermission.) You get no credit for uploading a program after I have given out the answer; assignments handed in after I give out the answer are invariably copies of my answers.

I post each week’s homework on the course home page the morning after each lecture. Whether you are present or absent, you should check the home page each week to find out what the homework was, and to see if any errors were discovered in the course materials. To show you in advance how much work to expect, the previous semester’s assignments are kept online on the home page.

Grading

Your grade will be based on the homeworks you hand in on paper. If you do the homeworks correctly, you get a good grade. If you do the homeworks incorrectly, you get a bad grade. For example, if less than 50% of your homeworks produce the correct output, you will fail the course. (I mention this only for legal reasons. In real life, no one ever comes close to having only 50% of their homeworks produce the correct output. Everyone does almost all the coursework or almost none of the coursework.) To produce the correct output, or indeed any output at all, your programs must compile, link, and run.

To collaborate with one or two other people, you may collectively hand in one copy of every assignment with the names of the two or three authors. You must stay with the same partner(s) throughout the semester, and you will all receive the same grade. In the real world you will program with other people, so I encourage you to do so now. Two people usually do a better job than one; it’s also less work for me to read.

You must do all your own work with no help from anyone except your partner(s), if any. You will fail the course if I receive two copies of the same work from people who are not partners, or work on which you were helped by a person who is not your partner. After you’re caught, it is too late to make the other person your partner. You will also fail the course if you hand in copies of my answers, or anybody else’s answers. Plagiarists are subject to the ridicule of their peers.

I will not tell you your grade. I mail the grades to NYU immediately after the last lecture of the course, I don’t know how long it will take NYU to make your grade available to you. They will provide a printed transcript.

SCPS dean Carl F. Lebowitz says “Incomplete grades should be given only in rare circumstances where a student has been able to complete nearly all of the course assignments by the end of the semester and has submitted the Incomplete Contract in advance regarding the situation.” NYU also says that to receive a passing grade, students must attend 80% of the course.

You can request NE for non-evaluative, P/F for pass/fail, and I for incomplete. See policies and procedures.

Course Objectives

This is a series of courses in C++ programming. In addition to covering the language itself (“where to put the semicolons”) and its standard library, we use classes and objects to organize and package programs better than could be done in languages that lack these features. This is called object-based programming. For example, Part I often presents the same program first in C, without classes and objects, and then in C++, with classes and objects.

When augmented with inheritance and virtual functions in Part II, object-based programming becomes object-oriented programming. When augmented with templates and the C++ Standard Template Library in Part III, we have generic programming. We cover all three methodologies of programming; the series is offered under the name “Object-Oriented Programming” only for marketing reasons.

Part I also covers function name overloading, default values for function arguments, inline functions, and pointers to members. Part II also covers operator overloading, formatted input and output with i/o manipulators, file input and output (including random access), dynamic memory allocation with new and delete, the containers vector and list, and error detection and recovery with exceptions. namespaces, runtime type identification, and internationalization with locale’s.

Overview of Sessions

The chapter for each session is already online, containing every example we will work through and its references. The topics are spread out over three parts, of ten weekly lectures each, of three hours each.

C++ Part I: INFO1-CE9264

The C subset of C++

In theory, C++ is a superset of C. In practice, however, many features of C should not be used in C++: printf, scanf, #define, etc. We begin with their superior C++ equivalents: << and >> in place of printf and scanf, const and inline functions in place of #define, etc. << and >> require a brisk review of operator precedence, associativity, and side effects in C and C++.

We round up all the features of C++ that have nothing to do with classes and objects to avoid later digressions. These include the placement of declarations, inline functions, function name overloading, default values for function arguments (bound at compile time, evaluated at runtime), calling C functions from a C++ program, C NULL vs. C++ 0 for pointers, and the C++ syntax for casting with static_cast, reinterpret_cast, and const_cast,

References are accompanied by a review of function argument pass-by-value vs. pass-by-reference. We use the C++ const reference notation for speed, the C pointer notation to let a function change the value of its arguments.

Classes and objects

Simple classes (date, stack, and J. H. Conway’s “Game of Life”) show how to write the basic machinery: classes vs. objects, public vs. private members, data members vs. member functions, const and inline member functions, constructors vs. destructors, copy constructors and default constructors, the this pointer, the three groups of names in scope in a member function, and header files.

We switch from pass-by-value to pass-by-reference to avoid unnecessary construction and destruction of objects used as function arguments and return values.

Object-based programming

As the students see these examples of classes (and the same code written without classes), we talk philosophy. There are several ways to think about objects. An object is a C structure with tighter security, thanks to constructors and private data members. An object is something you might want to have more than one of simultaneously; our examples are stacks and random number generators. An object is something you might want to create and destroy as the program runs. An object is a body of data that outlives the successive function calls that manipulate it.

An object can also trigger a pair of events. We appeal to examples in C: the pairs of functions malloc/free and fopen/fclose. In every language, pairs of events are nested: a window appears and then fills up with icons; eventually the icons disappear and the window disappears too. Parentheses in an arithmetic expression and tags in an HTML document are examples of nesting in space and time.

We look for patterns in C code that can be packaged more cleanly as objects: C local and global static variables, pairs of function calls, etc.

A class point and a member function giving the distance to another point show how the member functions of one object can access the private members of another object of the same class. The same example shows how friend functions rather than member functions provide a more symmetrical notation for operations on a pair of objects. (A doubly-linked list of nodes is another example of this same pattern.)

An evolving example

Learning C++ is harder than learning C. Any feature of C can be demonstrated in a program of at most one page: an if statement, a loop, and array. That one page will suffice to show not only the syntax for a feature, but also why the feature makes the program simpler and more powerful.

But the heavy-duty machinery of C++ is worthwhile only for a long,complicated program; employing them in a shorter would be like using a sledgehammer to kill ants. Instead of presenting a large example for each feature and then throwing it away, we develop one evolving example throughout INFO1-CE9264 and INFO1-CE9265: a video game. As the objects appear on and disappear from the screen, you can see their constructors and destructors being called; as the objects move around, you can see the values of the data members (x, y) change.

The game is upgraded with a succession of new features: const data members, static data members and member functions, arrays of objects, vector’s and list’s of pointers to objects, and dynamic allocation of objects with new, and delete. We end up accessing most objects via pointers, which positions us for object-oriented programming in INFO1-CE9265.

The game runs on the three different platforms that most students use: Microsoft Visual C++, Unix (GNU) C++, and Borland Turbo C++. The need for portability leads us to introduce an interface class.

Pointers to members

First we show the different C and C++ syntax for pointers to functions. We motivate pointers to functions with a jump table implemented as an array of pointers to functions.

We then show the syntax for C++ pointers to data members and member functions using the binary operators .* and ->*. We motivate pointers to member functions with a pop-up menu of objects: shift-copy, unshifted-copy, etc.

Aggregation

More complicated classes can be built out of simpler ones in three ways: aggregation, inheritance, and templates. Part I covers aggregation; Part II covers inheritance; and Part II covers templates. These three styles of programming are called object-based, object-oriented, and generic.

Aggregation means using little objects as component parts (i.e., data members) of a bigger object. We create a class using aggregation, demonstrating how the functions that build the big object (i.e., the constructors) interact with the functions that build the little objects.

C++ Part II: INFO1-CE9265

Operator overloading

Operator overloading lets us manipulate our objects with the same notation that we use to manipulate variables of the built-in data types int, char, double, etc. When we acquire templates in Part III, we will see the real benefit of a uniform notation. For the time being, operator overloading is just syntactic sugar: a nicer notation for calling the public member functions of an object. But there are complications. Operators can be implemented as member functions, friends, or neither. And some operators merely change the value of an existing object (e.g., +=, prefix ++) while others create new objects (e.g., binary +, postfix ++). This brings us back to pass-by-value vs. pass-by-reference.

We build a class string to motivate references in C++ with an operator[], and to demonstrate the differences between a copy constructor and an operator=.

Input and Output

We endow class date with operators for conversion (operator int) and input and output (operator<<, operator>>). We can check if an i/o operation has succeeded or failed, and use this to control an input loop.

After applying out i/o operators to the standard input and output, we use them to perform file i/o with the C++ Standard Library classes ifstream, ofstream, and fstream. We also perform string i/o with the classes istringstream and ostringstream. Finally, we format our output with i/o manipulators: left and right justification, number of digits to the right of the decimal point, etc.

Dynamic memory allocation, vectors, and lists

Most languages create and destroy variables automatically. To gain manual control over exactly when our objects will be constructed and destructed, and how long they will last, we perform dynamic memory allocation with new and delete.

To keep track of which objects currently exist, we preview a topic which we will cover in greater depth in INFO1-CE9265: containers of objects, and containers of pointers to objects. The two most widely used containers are vector (for speed of access) and list (for speed of insertion and deletion). We review the pros and cons of each.

Examples of inheritance

Inheritance is another way of deriving bigger classes from smaller classes. We start with a trivial example of single public inheritance without virtual functions to illustrate the syntax, order of construction and destruction, scoping rules, and header file layout.

Inheritance with virtual functions lets you operate on objects (i.e., call their public member functions) without needing to know their names or even their data types. We present two simple situations in which the programmer is forced to operate under these conditions of ignorance: looping through an array of pointers to objects of unpredictable classes, and calling a function whose argument can be a pointer or reference to objects of unpredictable classes. Inheritance with virtual functions is called object-oriented programming, and virtual functions are sometimes called polymorphic functions.

Object-oriented programming

After this breathtaking start, we backtrack to the details. When would you want to build bigger classes via inheritance rather than via aggregation or templates? What would the same code look like without inheritance? What are the rules for gathering a group of member functions into one polymorphic function? What happens if you break some of the rules: mismatched arguments, return values, omission of the keyword virtual?

How hard is it to retrofit an existing class so that it can be a base class for inheritance? We derive more sophisticated classes from our original class date to handle leap years, the absence of a Year Zero, and the Julian-Gregorian switch-over in 1752. Part II continues to deploy the features of C++ in one large, evolving video game.

The varieties of inheritance

Abstract base classes and pure virtual functions

Often a family of related classes are derived from a single base class: fast date and small date are derived from a basic date. This basic date is an abstract base class: it is intended only as a building block for the derived classes, not as a class of which you can create objects. This restriction is enforced with pure virtual functions.

Virtual functions let the behavior of the derived classes influence the bahavior of their base classes. At what what point in the construction of a derived object are the virtual functions in its base class overridden? How can you avoid accidentally calling a pure virtual function?

Public vs. private inheritance

We add a metric interface to an English class using public inheritance. Both interfaces exist side by side while the organization adjusts to the new culture. After a transition period, we yank away the English interface by switching to private inheritance. Public and private inheritance are also called interface inheritance and implementation inheritance.

Single vs. multiple inheritance

A class can be derived from more than one base class. We state the rules for the order of construction and destruction, and for conflicting names in the two parents.

When a derived class inherits from the same ancestor along two or more different blood lines, we let the ancestor be a virtual base class to avoid giving the derived class unwanted extra copies of the ancestor’s genes.

For example (at least in New York State), a nurse-practitioner has everything that a nurse has, plus more: there’s a nurse inside a nurse-practitioner. Similarly, a nurse-midwife is another enhanced form of nurse. Finally, a nurse-practitioner-midwife has everything that a nurse-practitioner has, plus everything that a nurse-midwife has. But there must be only one nurse inside the nurse-practitioner midwife. In oher words, the nurse-practitioner and the nurse-midwife inside the nurse-practitioner-midwife must overlap, and this overlap is the original nurse.

Rewrite the video game using inheritance

Many classes of objects move around the screen: wolf’s, rabbit’s, etc. We write their common code once and for all in an abstract base class named wabbit (à la Elmer Fudd). wabbit has missing pieces (called pure virtual functions) which will be filled in to endow the derived classes with individual motions and appetites.

There are many ways to fill in the missing pieces. First we’ll fill them in all at once using single inheritance: wolf and rabbit will be derived directly from wabbit. Then we’ll fill them in in stages using multiple inheritance: wolf will be derived from a general-purpose carnivore and a general-purpose mobile animal, both of which in turn will be derived from the virtual base class wabbit. The repetitious code that results from mixing and matching appetite and motion will be consolidated using templates.

Exceptions

An exception transmits information from the level of a program that detects an error up to the level that takes corrective action or prints a message. To fix the error, we often have to backtrack or dismantle some of the program’s work. An exception accomplishes this by destructing all the objects it encounters on its way from point B back to point A.

A simple example shows the syntax: try, throw, and catch. We show how an exception can carry information, and how exception classes can be nested or grouped into a hierarchy using inheritance.

We catch exceptions at two or more levels: less severe exceptions down near the point where the error was detected, more severe exceptions up near main if more backtracking is necessary before recovery can begin. What happens if an exception is thrown but not caught? Can two exceptions be thrown simultaneously? How can an object tell if it’s dying of old age or cut down prematurely by an exception?

The C++ standard library throws exceptions: vector::at throws out_of_range, new throws bad_alloc.

We retrofit exceptions into our video game to send reports of errors up to the main function.

C++ Part III: INFO1-CE9266

Templates

Function templates let us avoid writing the same function over and over. Our examples are the functions min, swap, and sort for a variety of data types: int, date, etc. Technical details include template arguments, default values, data type arguments vs. literal arguments, explicit arguments, and specialization. We compare the C standard library function qsort with the C++ standard library template sort.

Similarly, class templates are first presented as merely a way to avoid writing the same class over and over. Our example is a class stack that stores and retrieves a variety of data types. The class numeric_limits provides information about each numeric class (int, double, etc): maxiumum value, minimum value, etc.

We then reconsider class templates as a means of inserting smaller classes into bigger ones to specialize their behavior. For example, we insert different memory allocation strategies into a vector or case-sensitive vs. case-insensitive comparison into a search. Finally, we use templates to insert different styles of motion and appetite into our wabbit’s.

The C++ Standard Template Library (STL)

Containers

A container is a data structure that stores and retrieves other objects. A container can be an object, an input file, an output file, etc.) The STL is the part of the C++ standard library that implements containers.

We review the similarities and differences between the two most important containers, vector and list. We show how to subscript a map (i.e., associative array or “hash”), and then use the pair class and the find and insert member functions to avoid the inefficiencies of subscripting.

Iterators

An iterator is an object that loops through a container. For example, a pointer is an iterator. There are several categories of iterators: read-only vs. read-write, forward-only vs. iterators that can backtrack; sequental vs. random access. For example, the iterators that loop through a list must be sequential, while those that loop through a vector can be random access. The class iterator_traits provides information about each type of iterator.

Not every algorithm works with every kind of iterator. For example, the find algorithm will search a container that has only forward iterators, but the sort algorithm requires iterators that can backtrack.

Finally, we take pre-STL data structures (a singly-linked list; the screen of the video game) and turn them into STL-compliant containers by creating iterator classes for them.

Algorithms

We show simple examples of sort, find, find_if, and copy. We construct function objects or predicates to tell find_if what to look for in the video game and to tell sort what order to use. Finally, we rewrite sort as a template that can take any pair of random access iterators, not just a pair of pointers. This shows how to write your own STL-compliant algorithms.

Miscellaneous topics with little interaction with the rest of the course

Runtime Type Identification (RTTI)

RTTI lets you interrogate a totally unknown object to discover what class it belongs to, i.e., what services it can perform for you. This is usefull when dealing with objects that have arrived over a network. We cover the dynamic_cast and typeid unary operators, and the type_info returned by the latter.

Namespaces

A namespace lets us gather variables, functions, classes, etc. into families by giving them last names: “Bill” vs. “Bill Clinton”. Before namespaces were invented, they were faked by classes all of whose members were static.

We specify which namespace we’re using by means of explicit qualification, using declarations, and using directives. The unnamed namespace replaces C static variables. A namespace alias lets us transparently upgrade to new versions of software. We state the naming conventions for header files, e.g., string.h vs. string vs. cstring.

Internationalization (I18n)

We output numbers and dates using the conventions of other languages (German, etc.) for decimal points, a.m. vs. p.m., etc. This is called switching to a different locale. We then revert to English.