Welcome!

So. CS225. This is probably the most important (and FUN! YAY!) class of your undergrad career. Data structures are really, really, really neat toys, and the ability to use them effectively is what separates poor to average programmers from the best. If you pay attention, go to class (and section) every day and do the MP's, it will make you into a great programmer. For those of you who were bored in CS125, this class will teach you something new.

On the other hand, if you do a really half-assed job, don't care, and try to just skate by, you will most likely fail. This class is worth 4 hours for a reason. It will require a fair amount of work. But so long as you stay current and do the MP's on time, you should be just fine.

This means I'm your friend! Yay! I will do my best to keep things interesting in here. The notes are on the web, but it's to your advantage to show up. You'll see more examples, and get to ask questions. Plus I'll show you cool tricks that Jason skips over if there's time.

So in this class, we will be using C++. It's a whole lot like Java, except better. Jason's already gone through the spiel of why C++ in lecture. My reason for liking the language is the surge of power you get from your code running directly on the hardware, instead of in some wussy virtual machine.

Superficial differences between C++ and Java

• Classes end in a semicolon.
  If you forget the semicolon at the end of a class, you will get all kinds of odd, undecypherable errors.

• Access specification is done with labels and in groups.
  Instead of having a public or private label for each function and variable, you specify it once with a label ending in a colon, and access remains the same until you say otherwise.

• Default access in C++ is private, where as in Java it's package (public).

• Separation of definition and implementation
  In C++, you can (and should) separate your class definition from the implementation of the functions. Definition goes in a header (.h) file, and implementation goes in the C++ (.C) file.

• main() is not in any class.
  In C++, main is a function by itself, without a class. It usually goes in it's own .C file still, but it doesn't have to.

• You don't need an interpreter to run your programs.
  CC is the C++ compiler, and like I said, programs run natively in the OS.

I/O in C++ is a bit cleaner than in Java. It is done by three predefined objects called the Standard Input Output streams. They are cin, cout and cerr.

In order to handle include files, C++ has an extra stage to its compilation process. Before the compiler converts C++ code into asm, a program called the preprocessor runs through your code and interprets the following directives, among others:

• #define IDENTIFIER value
  This directive allows you to enact a direct substitution for an identifier in your program. It also lets you define pseudo-functions called macros (but we won't worry about that right now). It is convention to write the identifier for defined constants in all uppercase, and sometimes with two underscores on each side. #define by itself is useful for elimination "magic numbers" such as array sizes and such, to make the code more readable and to keep it bug-free. It can also be used in combination with #ifdef to prevent multiple inclusions of the same file, as we shall see.

• #include "filename" or #include <filename>
  #include stuffs the contents of its argument into the current file.

• #ifdef IDENTIFIER, #ifndef IDENTIFIER, #if defined(IDENTIFIER)
  These three all check if IDENTIFIER is defined. If it is, the code inside the body (up until #endif, or #else) gets passed to the compiler. If not, the code is tossed aside. This is useful to prevent include files from being included twice.

• #else, #elif
  These tie in with the #ifdef and #if directives, and work just like their equivalent keywords.

• #endif
  ditto.

Pointers kick ass. Jason said that Java doesn't have pointers in lecture. This is not entirely true. Every object variable in Java was in fact a pointer. A limited, wussy pointer, but a pointer nonetheless. (The converse, as we shall see, does NOT hold. A regular object variable in C++ is allocated on the stack, without the need to call new).

Pointers allow you direct access to the computers memory. A pointer variable holds NOTHING other than a numerical (in this case, 32 bit) value. This number is an address in memory. Real, honest to god memory. In fact, it helps if you actually think of pointers as integers with no type, only an address. If you forget to assign an pointer to an address, bad things happen. You can write to random areas of memory, and make things go crazy in a hurry. CS just got a little more interesting.

new and delete

So in Java, when you wanted memory for an array or an object, you requested it with new. This is still the case in C++. What is NOT the case is that this memory is automatically cleaned up for you during the program's lifetime. For every piece of memory you allocate with new in C++, you must keep track of it and eventually return it to the system with delete.

Common pitfalls:

1. Forgetting to free memory
   All this may seem simple, but things can get tricky later on, when there aren't pointer variables for each memory location in more complicated data structures. You have to keep the layout of things in your head (or better yet, on paper).
2. Using already freed memory
   delete does NOT change the value of a pointer. You must do that yourself with NULL. If you use already freed memory, your program will eventually crash at an unexpected location (usually an unrelated call to new or delete).
3. Freeing already freed memory
   Some C++ implementations will catch this, others will corrupt themselves and eventually crash.
4. Freeing unallocated memory
   Sometimes you forget to call new. Calling delete on an unallocated pointer causes the C++ library to write to random areas of memory, leading to an eventual crash.

Back in my day, they forced us all to use a system called PSP, or the Personal Software Process. I loved it. I organized my whole life around PSP charts. I went insane. It was great.

The PSP process divides development into 5 stages: Planning, Design, Code, Compile, and Test. You record how much time you spend in each stage, and how many bugs you introduce into each stage, and what these bugs were. (Bug classes included Documentation, Syntax, Build System, Assignment, Interface, Checking, Data, Function, System, Environment). After doing this analysis for a while, you got really good at predicting how long something would take you, and also which bugs you were most prone to make where.

They forced us to do it, and everyone hated it. Like I said, I followed it religiously though, and it worked. By the end of the semester, I was writing MP's that ran and passed all test cases on the first try. By the end of the following summer, I was writing large software projects for the NCSA that did the same. If you want to be a great programmer, I highly recommend this process.

At the very least, do what Jason suggests. Before rushing off to compile something, check it over. Keep a log of what mistakes you make, and turn that log into a simple checklist. It takes something like 10X less time to find bugs in code review than it does through debugging.

Sample Checklist:

• Did I include the proper include files?
• Did I remember to scope (::) all my functions?
• Do all my classes end in ;?
• Do I allocate and free all memory?
• Do I use == instead of = in boolean expressions?
• Are my loops correct? (Fencepost errors?)
• Are my arrays the right size?

More Example Code