DIY C++ Preparation Course

Admissions

DIY C++ Preparation Course

Introduction

As mentioned in our Guildhall Preparation page, not everyone has the opportunity to take enough C++ related courses in their undergraduate study to get to the proficiency level required by The Guildhall. To increase your chances of being admitted to The Guildhall, and to make your stay there more productive, it may be required that you spend some quality time with C++ on your own. Remember, you can only improve your programming by doing. The more time you invest, the more you will get out of it.

This document is here to serve as a guideline for a "self taught course" in reaching higher proficiency levels in C++, especially for those that do not know where to start. Everyone has a different background and starting level, of course, so use the following material as you wish.

Organization

We have collected different categories of materials that will help you broaden your C++ knowledge in different ways:

Web reading: the amount you can learn here is tremendous, we have collected what we think are the best links
Book reading: some of the highest quality reading still comes in the form of books
Open Source: there is a tremendous amount of code out there, and you can learn a lot by reading and playing around with other people's code.

Programming Exercises: ideas for medium size programming projects where you can flex your C++ muscle

What we have done is order resources in each category in order of usefulness to learning, and quality. The way we would like you to work through the materials in this course is do the different activities above in parallel (so mix reading with writing, etc), but start in each category from #1 and work your way down. This way you will have maximum benefit from the time you put in.

The amount of material collected here will be too much for most to go through in its entirety, so do not attempt to "finish" it. Instead, work at your own pace, focussing on items that give you trouble, skipping items that are "too easy".

You will find that the majority of resources do not focus on game programming, and that is intentional. By wanting to apply to The Guildhall, you likely have a high interest in this area, but this material is purely focussed on improving your C++, which works much better without details of 3D API's and such getting in the way of you becoming a stronger programmer. During your stay at the Guildhall you will have plenty of time for pure game & engine programming.

1. Web Reading

Some good starting points for web browsing on interesting C++ material:

Good online C++ courses: 1, 2, 3, 4
References/links: 1, 2, 3
Boost: extension library to the STL
Codeguru
Some good general advice: 1, 2
Stroustrup's homepage (the guy that designed the language!)
Alexandrescu's site: recommended articles are "Traits: The else-if-then of Types" and "Traits on Steroids" - good introductions to generic programming.
Herb Sutter's GotW examples: nice to read one every day.
Software engineering links: c2 wiki (patterns), Erik Raymond's writings, Artima (interviews with people like Stroustrup), code as design
Learn C the hard way

2. Book Reading

These are some valuable books that provide insight hard to find elsewhere:

The C++ Programming Language: Special Edition (3rd Edition)
Memory as a Programming Concept in C and C++
Effective C++: 50 Specific Ways to Improve Your Programs and Design (2nd Edition) (and if you want more of this kind of book, there is More Effective C++, Exceptional C++ and many more)
Accelerated C++: Practical Programming by Example
Design Patterns
C++ Coding Standards
Numerical Recipes in C (full book text online!)
Modern C++ Design
Large-Scale C++ Software Design

3. Open Source

With the amount of Open Source out there, the opportunity for learning by studying other people's code is greater than ever. Of course, not all code is of equal quality, but reading code in a variety of styles will help broaden your perspective. We have picked what we think is a good selection, spanning a variety of code styles and application domains.

How do you read code? This question is not as straightforward as you may think, since reading it like a book, from start to finish, is very inefficient and will make the code hard to understand. You therefore have to read in in multiple passes, each time going in more detail than the pass before it:

1. Start acquiring a global overview by browsing through the source code files, seeing what sources there, how they are organized, what sizes they are etc. This should give you a broad impression.
2. Then do a very quick first impression on the code... start with the header files, as this is often where you'll find most declarations that matter. Make a mental note of data structures and systems you come across, and you'll now have a slightly better picture of what the code base consists of.
3. You are now ready for looking at code in more detail. Choose a particular subsystem you want to understand better, find its corresponding .cpp files, and browse through the code. Note browse, not read: you want to focus on what helps you understand what the code does, not read a .cpp line by line. Skip over things that appear not relevant to your current interest.
4. You're now getting to a point where you could start playing around with the code and make some modifications, but to make modifications safely a deeper understanding of the exact control and data flow of the code surrounding your point of modification is required. A great tool for this is using the visual studio debugger: put breakpoints around the code of interest, and when it breaks there, use the step function to understand the control flow. Use variable inspection to see what the run-time data looks like and understand even further what the code does.
5. Once you're comfortable you understand the code to a good degree, try and make a modification and see how it works with the existing code.

Some of the projects below may seem overwhelmingly big. Even the greatest programmers will take a long time to comfortably find their way around a large new code base, so if you feel it takes you a long time to find your way around, that is natural. But that is also why this is such a good exercise, so take it seriously. Most any codebase underlying games of today is huge, so learning to deal with large codebases is an essential skill.

Depending on the project, you may have to change visual studios project settings to get what you want. Getting comfortable with the whole C++ programming pipeline (visual studio IDE, projects, compiler, linker, debugger) is something else these exercises help with.

Projects to read and play around with:

zlib: zlib is a general purpose compression library, something that your code can use to directly read and write compressed files. Read up on zempel-liv style compression if you fancy. If you want to try yourself to write a compression algorithm, try the Huffman exercise in section 4 below.

wxwidgets: this is a large API that provides functionality for creating GUIs, and then some. Navigating its code will be a challenge, and reading some of the documentation first may be a good step to see what is there. Then, read some of the code of whatever component interests you most (or try a simple starting point like the button widget). This being an API, it doesn't come with a "main" program to run, so you can either use one of the included example programs for that purpose, or create your own (see the wxwidgets exercise in section 4 below).

enet: this is a small networking library designed for games. It transfers data over UDP (TCP is unsuitable for games) either reliably (coordinating resends for you in case of packet loss) or unreliably (for example, position updates in FPS games). Play around with the example program included. Though the code is small, it will be hard to understand as it does a lot of special purpose work that may not be obvious, don't worry if you can't follow it. Debugging networked applications is a special challenge, because not only does the code run in two seperate processes, since it is networked, the connection can time out if you halt either processes in the debugger, and data can be different every time depending on timing. Try it out!

STL/Boost: if you thought you understood C++'s template feature and want a challenge, have a browse of your favorite STL containers. The source for STL comes with the compiler, Boost comes seperately but can be seen as an extension of STL.

Only if you have already done the above and want more: there are a great number of open source game engines out there. As mentioned above, this text is about exercising your C++, not about game or engine programming in specific. So if you have a look at these projects, focus on their code structure, their use of C++, data structure management, and general software engineering aspects. Worth looking at:

quake 3
ogre
sauerbraten
Open Scene Graph

4. Programming Exercises

Before we look at the exercises, some general tips on how to get the most out of your learning while writing code:

Focus on your weaknesses: if you come to programming C++ from Java or C#, your weakness may be in your understanding memory management and other low level features. If you come from C you may not know how to structure larger programs with classes. If you started with C++ but simply haven't done much yet, your weakness will lie in knowing how to deal with the "growing pains" of programs becoming bigger (larger scale software engineering). Seek out projects that stress these items rather than our natural human tendency to avoid them.

Treat code quality seriously: these exercises are not against a deadline or for pay, so don't work on them just to get them done. Instead, once you have created code at any stage during development, keep working on it until you feel the code is in its best form you can think of. Do not be afraid to restructure the way you organize code and data in your program to make it work more optimal as you learn. While learning, you will discover new techniques, and your understanding will grow to the point where you see ways in which old code can be done better. Always improve that code to the point where it is up to your new standards immediately, the longer you wait, the harder it becomes.

Think about code structure: this is a difficult topic for most programmers, as there are a myriad of ways to organize code, and it is hard to know what is best up front. So the best tip I can give any programmer: don't repeat yourself (aka Once and Only Once). choose the structure that allows you to write all code exactly once. In simple words, it means that once you need a piece of code or data twice, make a function (or class) for it. Conversely, it also means you shouldn't create/keep structure for things you need just once. This is a rather simple principle, and if you apply it aggressively, you will attain a good code structure almost automatically, one that is simple, and easy to modify. And it is easy to see when you're not doing things right: whenever a single change you make requires you to make changes in 2 places.

Don't stand on other people's shoulders: In the real world, programmers often have to reuse code from others, which can be a good thing, certainly from a productivity stand point. But when learning, try to avoid basing your work on other people's code. It is ok to learn how to do something by reading other people's code, but then construct your actual program yourself, in your own way. You'll learn lots more.

So here are some fun programming exercises to train yourself with. As mentioned before, they are ordered roughly from the easy/short towards the more complicated ones. These exercise descriptions don't come with full step-by-step instructions on how to implement them, for most you will need to use google to find information on relevant algorithms. Doing research is a part of being a programmer, and is part of these exercises.

Write a Huffman compressor (and decompressor, if you feel like it). Huffman is a compression algorithm, called an entropy encoder, that stores a series of bytes in the least amount of bits, depending on frequency. So, for english text, it would want to use less bits for "e" than for "q". The compressor works by loading a file, counting the frequency of occurrence of each byte (try with english text), and then constructing a binary tree to determine how to assign sequences of bits to each character. Then, it writes out each byte in the file as the sequence of assigned bits, often shorter, sometimes longer than the original byte (which always had 8 bits). This exercise will stress file IO, bitwise operations, and data structures. This chapter from the numerical recipes book (see above) may be useful.

Write a tree editor using wxWidgets. A lot of programs (including games) use general tree structured data to specify properties about objects. XML is an example of a general tree file format that is used by a lot of applications. Make sure you have first done the Open Source code reading exercise on wxWidgets, above. Start a new project from scratch, and create a gui with a tree view, a toolbar (for save/new node/delete and such), and a list view. Allow people to create new nodes in the tree view, as a child of the currently selected node. This way, any tree structure can be created. Provide additional operations like delete, copy, paste, and if you can, the ability to move nodes around. Use the list view (or other widgets of your choosing) to show additional properties of the current node (make them editable). Now write functionality to save these trees and their properties in a binary file format of your own design. The binary is important, this exercise is meant to also stress your ability to "flatten" pointered data structures, memory management etc. If you want a bigger challenge, make your editor additionally read and/or write XML (simple XML, ignoring schemas etc). If you want yet more to add, try and write your binary files using the zlib library (see above).

Write a memory manager. Look up (in the Stroustrup book above, for example) how you can overload the new and delete operators. Then implement new versions of these by allocating memory from a fixed size memory block. You'll have to devise a scheme to keep track of what parts of that block are in use, and which are not. What scheme you choose affects efficiency (both time and space), and robustness (after many operations, your block may get fragmented) . Once you think you have an implementation that works well, add it to any of the previous exercises. Gather some statistics on memory usage (number and sizes of allocations/deallocations, fragmentation etc.) to understand better how your allocator is performing. Resources: Doug Lea's well known free allocator, a very thorough survey of memory allocation. Anton's samples related to memory management.

STL (and by extension, Boost) contain the majority of container classes most programmers will ever need. Just relying on them without understanding how they are implemented internally, however, is a bad idea. Many of the containers have a lot of "gotcha's" that have to do with C++'s relatively unsafe type system, and understanding them is vital if you want to avoid long debugging sessions. Every programmer should implement their own version of the most common container at least once. It will also help you with your understanding of memory management & overloading/constructor features of classes. Try making your own version (and then using, in your code) of, in this order: vector, string, hashtable, a doubly linked list, and a (tree based) map. They don't have to have the exact same functions or implementation, but some similarity will be useful such that you can switch back to STL later.

If you still need more exercise, one good idea is to try and re-implement past programs from CS courses in other languages, such as Java. The fact that you have already implemented them will allow you to do a much better job on these programs than any exercise you do for the first time, like the above. You'll be able to think about how to represent the code well in the new language (C++), and hopefully your general programming ability will have improved since you first did them, so you can probably make the programs a lot more simple and elegant.