Advanced C++, generic programming & STL
Introduction
People claim that to design a large and complex system requires an experienced programmer. Though I feel to design such a system you only need a programmer that understands how to take the complexity out of complex problems. To do this the programmer needs to recognize the problem, isolate the problem, and then apply the appropriate solution to the problem. Simple. Cookbook recipes. Unfortunately, to be able to recognize, isolate, and apply the appropriate solution usually does take an experienced programmer. Though my intentions of this tutorial is to take the programmer from writing foobar() and class Cat{ void Meow(); } code to writing complex systems.
The type of knowledge needed to transition from the inexperienced coder to the design guru can be categorized into the following: the C++ language, generic programming, and design patterns. The latter of the two topics are very generic, that is, can be applied into all of your code in the future. Nothing will be covered in this article on how to write socket programming, or include any fancy windowing system, or make use of any libraries besides the STL. What you will learn here is implementation independent knowledge that can be applied through out your coding career whether it is in python, lisp, C++ or whether using a graphic library in Windows or Unix.
To be able to solve problems you need to be able to fully express your ideas. Fortunately, C++ offers the ability through the language’s semantics to express these ideas. The combination of C++ low-level memory model, polymorphism, and template-generated code gives the language its expressiveness while maintaining lighting fast performance which makes this language a perfect choice to discuss generic code and patterns. Though understanding all the quirks of the language can be quite difficult even for a long time veteran of C++. So a majority of the beginning of the article will focus on the more advanced side of the language and any examples through out the article that contains any tricky context will be explained or referenced.
Once you understand the rules of the language we can move on to the real meat of the steak. We can start moving into generic programming and design patterns. Generic programming is essentially defining a single interface that can work across a wide variety of types. Generic programming is taking the complexity out of the code; it lets you focus on the algorithms rather then details. As I’m explaining to you how all the generic code works I will be sneaking in some very useful design patterns. Design patterns are your generic solutions that work on common problems. They describe the problem, the solution set and all the possible outcomes of the solutions and each of their differences for choosing the outcome. Remember if you can isolate and recognize the problem there is probably already a solution to it. It just involves rewriting your code to fit the design pattern once that is done then you just have to apply the appropriate idiom and bam you’ve got yourself one elegant design.
Finally, I will be creating a lot of example problems that loosely match how the internal’s of the STL works. The STL (standard template library) is a set of generic algorithms that work on the most common containers in computer science and the real beauty of the design is that it is easily extendible to work on new types. I feel that the STL is a library with a design that is light years a head of its time. Understanding the STL is not only essential to becoming a competent C++ programmer but learning from their design can help bring your code to a more top-notch professional level. Hopefully after reading this article you will have a better understanding and a better appreciation for C++ built in standardized library.
Audience
This tutorial is aimed at both experts and intermediate programmers a like. For the intermediate programmers this article supplies plenty of code and examples of using the languages more advanced features while not going too fast or making too many assumptions of any of C++ tricky concepts. While some of the details of the languages constructs may be quite deep and examine some arcane rules these can always be skimmed over and referenced to back in a later date.
While the more advanced programmer should also benefit from this article even in the beginning sections, which cover the language details. The standard is 732 pages long (actually my copy is 750 pages but I paid for 732 pages) and a lot of details of the language that I discuss are quite exotic that most textbooks do not cover. More importantly I discuss plenty of design patterns that will keep you busy for quite a while.
Finally, it would also benefit non-C++ users to read this article, whether you program in Python, LISP, Scheme or any other language that has support of poylmorphic semantics. By skimming over the non-relevant C++ parts and focusing only on the theory behind this article the reader could apply these idioms to there own language. Design Patterns are usually not illustrated in any specific language often pseudo-language and UML is used to describe these idioms. The intent is to try to offer enough theory but also maintain balance with enough application so the programmer can apply the theory but there should be enough theory to keep any non-C++ programmer happy.
Compiling Example Programs
There are a few issues to bring up with compiling these example programs. I will not always include the driver program[1] to complete the example problems especially if it does not help further demonstrate the current issue. I will often only include the class definition but not include all the methods[2] but will leave an ellipse … to show that not all of the details are included. This is for brevity and to help the reader focus on the topic and not on any irrelevant details.
Quote:
class Widget
{
public:
… Foo( … _bar );
…
private:
… bar;
};
Only when the code contains complicated irrelevant details will the extra code be left out. Of course the above example is on the extreme end of ellipse usage. The intent was that even the novice coder should always have enough code to be able to execute the example program but not have too much code to clutter the article or take away from the topic.
[1] Definition
driver program: Through out this article I’ll make reference to the driver program, it can be any program that makes use of the functions that we define. Typically to compile these examples you will write an int main( ) { /*example functions*/ return 0; } that will use the functions or classes developed in the example so you can successfully execute the examples.
[2] Definition
method: Simply an alias for the name function or procedure except it also implies that the function or procedure is being used within an object orientated design.
The second issue with compiling the example code is a bit more frustrating. Most of the examples use the latest design patterns that stretch the languages constructs to their ends. Many compilers will not be able to handle all of the examples but it is not entirely the compiler manufacturers fault. The standard was released in 1998 and only this year has there been a release of a totally standard compliant C++ compiler. I’ve had the best luck compiling the code under Microsoft’s C++ .NET 2003 compiler so if you happen to own a legal copy you will be in luck. Though that doesn’t mean everyone else should stop reading this article for Comeau has released their online compiler for testing. Their compiler conforms fully to the ISO C++ standard and can be used at http://www.comeaucomputing.com/tryitout/
Comments and Critique
Feedback is always welcome. If you have any comments or complaints please send them via one of the channels provided below. You can ask questions about code, tell me how god-like I am, or tell me how badly I suck. I am pretty good at responding to questions within the day or if I’m really swamped it may take two days. Also if you notice and send any technical or grammatical errors your name will be included in the next revision of this article.
email: [email protected]
AIM: surftherocks
MSN: [email protected]
[size = 3]Introduction to templates[/size]
You’ve probably noticed that when writing your programs you’re always concerned with the data type you are using. This is because C++ is a statically typed language, which means that all data types are determined at compile time. Other languages such as Python and LISP are dynamically typed meaning the types they are used are determined at run-time. In C++ you are always forced to declare which data type you are using before you use it.
Quote:
int main()
{
x = 3 + 4; // ERROR: No type declared for x
return 0;
}
int main()
{
int x = 3 + 4; // OK: x declared as int
return 0;
}
In this example if C++ were a dynamically typed language both examples would be able to compile. It is obvious that x is an int and the compiler would easily be able to deduce the type because of the rhs[1] of the expression, which contains 3 and 4 which both are int. The arguments for dynamically typed languages are should the language care what type the variable is as long as the type can be deduced and the type has the defined operations. The arguments for statically typed languages such as C++ are that you can place the burden of catching errors on the compiler and not on the programmer. An elementary example of the benefits of statically typed languages included in most Introductory C++ books of const
char* GetString( );
If the function was returning a string literal, which are read-only, then the string cannot be modified and if it is it will result in an access violation. Rather then waiting for the program to crash during a demonstration to your clients you could force the compiler to catch any attempts to modify the returned string.
char const* GetString( );
Now any attempts to modify the read-only string would result in a compiler error and will save you from any access violations at runtime.
[1] Notation
rhs: Right hand side, which refers to the right side of an expression. In the expression int x = 3 + 4; the right had side is 3 + 4 where the left hand side (lhs) is int x.
Though C++ is a statically typed language it does not mean that we can’t make use of generic types. If you are from a language like C I’m sure you’ve come across making generic containers by using macro definitions like
#define int ListType
Though the problem with C’s macros is it is just a stupid text replacing mechanism and does not follow any of the rules of the language. It is also possible in C++ to achieve a generic type by have a common base type like void* but the problem of this is the same of a dynamically typed language there is no static-type checking.
C++ through the languages semantics offers static type checking and the ability to have a generic type. The use of C++ template construct allows the programmer to specify functions and classes that are type independent and without losing static typing(errors are still caught at compiler time). This allows the programmer to focus on the algorithm and not on the details.
Function Template Basics
Let’s look at a basic function template Sum that takes two types and returns the sum of the two. This function generates a family of functions. That is a bunch of functions that at the algorithmic level all look the same but use different types.
Quote:
template <typename T>
const T Sum( const T& first, const T& second )
{
return first + second;
}
Let’s try and dissect the code. What you should notice that is different then the non-template version of the function Sum, is that it has the keyword template followed by the template parameter list.
template < parameter list >
The template parameter list has a single parameter of typename T.
template < typename T >
The keyword typename introduces a type parameter with the actual type parameter being the identifier[1] T. A parameter also referred to in some textbooks as formal-parameter is a variable that isn’t defined until the function is called. So a type parameter is a type variable(int, float, std::vector) that isn’t defined until the function is called. Any type can be used in the Sum function that supports the operator < because both types use that operator for comparison.
[1] Definition
identifier: A name that can have only letters, underscores and numbers. It also may not start with any numbers or be any identifier that is a keyword.
[1]Note
The T identifier is a convention used by most C++ programmers to separate defines and ADT[2] from typenames, it is not required to use the identifier T you could use myType or any other valid identifier name for templated code.
[2] Definition
ADT: Abstract Data Type, refers to any data type that is not a primitive, built in language type. Examples of ADT’s are std::vector<list>, class MyADT{};
Using Function Templates
Quote:
#include <string>
#include <iostream>
template <typename T>
const T Sum( const T& first, const T& second )
{
return first + second;
}
int main( )
{
std::string hisFirst, herFirst;
std::cout << “What is your first name: “;
std::cin >> hisFirst;
std::cout << “The first name of the girl you like: “;
std::cin >> herFirst;
int hisAge, herAge;
std::cout << “What is your age: “;
std::cin >> hisAge;
std::cout << “What is her age: “;
std::cin >> herAge;
std::string fill = “ “;
std::string combinedNames = Sum( Sum( hisFirst, fill),
herFirst );
int combinedAge = Sum( hisAge, herAge );
std::cout << combinedNames << “s combined age is “
<< combinedAge << std::endl;
return 0;
}
Output:
What is your first name: John
The first name of the girl you like: Jane
What is your age: 12
What is her age: 13
John Jane’s combined age is 25
This program uses the Sum function for two different types but is defined only once. The function can take any type that has the operator + defined and as shown by std::string class in the example.
combinedNames = Sum( Sum( hisFirst, fill), herFirst );
The code above shows a combination of two functions with the first function dependent on the result of the inner function. The first function takes two arguments[1] the first being Sum( hisFirst, fill) and the second being herFirst. Sum( hisFirst, fill) returns a temporary std::string so the two arguments are now some temporary std::string and fill which are both of types std::string. Since the function takes two std::string arguments the compiler makes an instantiation[2] of
const std::string Sum( const& std::string, const& std::string );
At a later point in the example code the function is called with two integers as the arguments this instantiates the function with int
const int Sum( const& int, const &int );
[1] Definition
arguments: Arguments are the values being passed to a parameter list it is very important to note the distinction because the two will be used quite often in this article and without understanding the distinction between parameters and arguments you will get lost easily. To solidify this knowledge here is an example
// Here int x is the parameter list containing one
// parameter int
int square( int x ) { return x*x; }
// Here you pass the argument 3
square(3);
[2] Definition
instantiation: Not to be confused with an object’s instance or instantiation, the context in which it is used through out the article is the process a compiler goes through to generate the function based on the arguments it was passed.
:: resolution operator
I would like to go on a brief tangent and discuss the resolution operator because of the amount of times it veers its ugly head in this tutorial. If you are already a pro on scope and name resolution then you can skip this section. Names in c++ taken out of context can be very ambiguous. If you see the statement x*y you probably think multiplication but if x is the name of a type then it would be a pointer named y pointing to type x. C++ in this sense is a context sensitive language which means in certain instances a line of code can be totally different then another line of code on the same page.
To remove ambiguity from a name you can use a qualified name. A qualified name is a name that explicitly states the scope the variable came from using the :: scope resolution operator, or (. or ->). Examples of qualified names are
this->count; // OK: qualified name resolving to the current class
count; // Ambiguous: non-qualified name
Cat.Meow(); // OK: qualified name resolving to the cat class
::Meow( ) // OK: qualified name resolving to the global namespace
max(); // Ambiguous: non-qualified name
std::max() // OK: qualified name resolving to the std namespace
cont<T>::X // OK: qualified name resolving to the member X of cont<T>
In the example program above that uses the Sum function I use the std:: qualifier to resolve all std functions and variables to the std namespace. I could have easily used
1) using namespace std; // OK but bad coding practice
2) using std::cout; // OK and better
When you use the keyword using you are resolving the variable or function into global namespace or the entire namespace as we did in part 1. If we use method 1 we take all the names inside the namespace std and resolve them to the global namespace effectively cluttering the namespace. Then if our Sum function was defined in the std (which its not) it would lead to ambiguity did we mean to call the std::Sum() or did we mean to call ::Sum()? By resolving only the names you need in to the translation unit[1] you lead to less clutter of the global namespace and less ambiguity.
[1] Definition
translation unit: A translation unit consists of a .cpp file and all of its includes. A cpp file cannot see variables across different translation units. If you declare a global variable in one .cpp file and use it in another you will get a declaration error.
Function Template Parameters
At the previous example Sum the template parameter list consisted of one parameter typename T. While the call parameters had two parameters const& T first and const& T second. It is important to distinguish between a call parameter(also sometimes referred to as formal parameters) and template parameters. The template parameters are contained within the angled brackets < and > while the call parameters are contained within ( ) after the functions name.
// call parameters int a and int b
int func( int a, int b )
// template parameter typename T
template <typename T >
A template parameter list is just that a list of parameters, in the previous example we only used one parameter T.
// finish this later
Nontype Template Parameters
The power of templates extends beyond being a generic implementation of an algorithm. Template parameters are not restricted to using a typename there can also be nontype parameters, or ordinary values. As you will see later being able to use an ordinary value can lead to some very powerful metaprogramming and design patterns. Normally when using templates you define what type to use and not the value of the type, with a nontype template you are defining the value to use and not the type. A template parameter is like function parameters that way, as it allows you to pass values. Though there is a key exception being that with a function you pass a value to the same instance of the function but with a nontype template function you are instantiating a function for every value you use.
A good example of a nontype parameter is defining the size of C++ built in array. One of the weaknesses of C++ built in array is it is statically allocated and can’t be of a variable size. Meaning that once you declare an array to be size 10 you can’t re-declare the array to be size 20. Since templates are static in nature, they are instantiated during compile time, we can use this to our advantage and allow the client of our code to declare the size of the array.
Quote:
template <int n>
void SizeOfArray()
{
int array[n];
}
int main( )
{
SizeOfArray<10>();
return 0;
}
We declare our nontype parameter with the variable n, so that when we specify the value of n the compiler will instantiate, or generate, a function with the variable we specified.
template <int n>
To use the function you must explicitly state what the nontype value is, the compiler can’t deduce what it should be. Before when you passed the templated function Sum two int the compiler could deduce that the typename T was int and so the function Sum<int> was instantiated. Though with nontype the compiler cannot deduce the value of the nontype and it must be explicitly stated. You explicitly tell the compiler the value the nontype will be when you call the function with angled brackets < and > before the parameter list with the value of the nontype.
SizeOfArray<10>( );
This explicitly[1] tells the compiler that the template function should be instantiated with a nontype value of 10.
[1] Definition
explicit: To explicitly define a template is to tell the compiler exactly what arguments to use. While implicit refers to letting the compiler deduce what arguments to us. You can also explicitly convert an int to a float or implicitly allow the compiler to do it for you, an example of both.
Quote:
void foo( float x ){}
// Explicitly convert the argument
int arg = 3;
foo( float(arg) );
// implicitly let the compiler convert it to float for you
int arg = 3;
foo( arg );
There are some restrictions on what nontype template parameters you can use and mostly these restrictions have historical reasoning. Probably with the next iteration of the C++ standard C++0x, most of these restrictions will be gone. The rules are
1) The nontype may be constant integral value or a value that can be evaluated as an integral value, such as bool, char and enum.
2) The nontype may be pointers to objects with external linkage
Unfortunately you cannot use objects as a nontype parameter or any primitives that have floating point representation such as float and double.
Full Specialization
It is not always desirable to use the default behavior of a template function. If you want to have a family of functions define a certain behavior for all types except for a few you need to specialize the behavior of the few. Suppose that you wanted to have a function create an array with the type you explicitly state to have.
Quote:
template < typename T >
void CreateType( )
{
T array[10];
}
// call the template function
CreateType<int>();
This creates an array of int with 10 elements but if you tried explicitly instantiating the function with char* it would create an array of 10 pointers not a pointer to an array of 10 chars. To fix this behavior you would have to specialize the case for char*. The syntax to do this is have template <> with empty brackets and after the function name use state the type your are specializing.
Quote:
template <>
void CreateType<char*>( )
{
char* array = new char[10];
delete [] array;
}
CreateType<int> 10;
CreateType<char*> 10;
The first function instantiates the first generic behavior of CreateType and initializes the array on the stack, while the second function instantiates the second behavior of CreateType and initializes an array of 10 chars on the heap.
First Design Pattern: Compile-time if statements, ASSERT
Specialization can deliver some powerful idioms including designing a compile-time if statement. It is not always preferable to if statements during runtime. The main reason is it costs CPU cycles to evaluate an if condition and if the if condition is being evaluated in an intensive loop then checking the condition at runtime could be very costly. This is where specialization comes in you can allow a condition to be evaluated at compile time and it will cost you 0 runtime performance. Imagine you write a square route function, obviously you shouldn’t be taking the square root of any number less then or equal to 0. To prevent this you check the value that is passed to the parameters to ensure the value > 0.
Quote:
double square_root( const double value )
{
// declared in cmath
if( value > 0 )
return sqrt( value );
else
return –1;
}
This validates the value passed is always going to be greater then 0 but it also requires an if statement to check every time the function is called. A neat little trick to check at compile time is to declare but not define a function template that takes a bool as a nontype parameter. Then specialize that function for true and define it. That way if you try to pass a value that evaluates to false the compiler will issue an error saying that the template function for false was never defined.
Quote:
// declared a family of bool functions but did not define its implementation
template <bool>
void assert();
// Full Specialization of bool with true as the argument and defined its implementation
template <>
void assert<true>() {}
double square_root( const double value )
{
assert< (value > 0) >();
return sqrt( value );
}
The assert template function is called and explicitly states its parameter. If the condition evaluates to true then the function called is instantiation of assert<true> which has a definition. If the condition evaluates to false the compiler tries to instantiate assert<false> but fails to because the implementation was never defined. Viola! Compile-time assertion.
MetaProgramming with Nontype Parameters
Metaprogramming is the ability to have your code program itself. The code that you write programs itself by generating new code, cool huh? Metaprogramming allows the user to solve problems during compiling time rather then during runtime. This means lighting fast performance when calculating certain functions because it is computed at compile time. An example I will use to illustrate metaprogramming is how to calculate the factorial of a number at compile time. This trick relies on nontype template parameters and full specialization, without those two constructs metaprogramming would not be possible.
Quote:
template<int n>
int factorial()
{
return n + factorial<n-1>();
}
template<>
int factorial<1>()
{
return n + 1;
}
// determine factorial of 10
int ans = factorial<10>();
This simple little exercise shows how the recursive nature of template instantiation. When you compile this program the compiler instantiates recursively 10, 9, 8, 7, 6, 5, 4, 3, 2 and finally 1. Because of full specialization we could define the behavior of 1 to be different then the behavior of the rest of the family of functions for factorial<int n>. The answer is computer for you before you hit the run button.
Class Templates
The most elementary use of class templates is the container class of type T also known as a value[1] type. Similar to function templates you can parameteratize classes to accept any types. By being able to use any type for a class you can write generic data structures that has no knowledge of the data type it is operating on. This is powerful and intuitive. Take the data structure vector for example; with a vector you are holding data that acts like an array. Does it matter if the data is a collection of strings, int, double, MyObject? It makes sense to write one container that can hold any data type. The operations in the container is the same across all containers so you shouldn’t have to worry about what type to use and that is where the power of container class templates come in to play. The ability to abstract the type away from the container lets the programmer write one implementation of a class that works on all types. The container class holds a type and whether it’s holding a giraffe or my collection of my Eric Clapton CD’s should be of no relevance of how the class is implemented.
[1] Definition:
value: According to Jim Hyslop and Herb Sutter in their article “Value Lesson’s” published in the C++ User Journal, a value type is an object that depends on its state, more than its behavior. An object type relies more on its behavior and identity, than on its state. A value type with emphasize it’s state by having it’s member functions modify or provide access to it’s data members, it is concerned with data it’s holding. Classes that represent strings and dates are good examples of a value type. Another side note, in the article the author’s try to make it clear that you should never mix a value type and an object type together in one class. That is don’t make a class that implements behavior and a class that holds it’s state.
Vector
One of the more elementary data structures to grasp is the vector and not only is it easy to understand it is also one of the most widely used and useful data structures in the standard template library. It only makes sense that when covering a container class that I should cover how the standard template library designed and implemented the vector value class. Just a forewarning, all data structures and algorithms found in the standard template library have constraints put on them so the programmer is guaranteed how the algorithm or data structure will work. This means that I will have to use Big O notation and if you have not taken a class in algorithms or data structures this may be foreign to you. Simply put the Big O notation describes the time and space efficiency of an algorithm. An example of Big O notation is O(n) meaning that the time of the algorithm is based on the size of the list. It isn’t that important that you get stuck up on the exact semantics of the notation. It is just important that you understand the constraints applied to the data structure so you can have an understanding on how to design the vector class.
In C++ according to SGI’s[1] implementation of the C++ standard, a vector is a value type that supports random access to all its elements, constant time insertion and removal of elements at the end, and linear time insertion and removal of elements at the beginning or in the middle. The number of elements in a vector may vary dynamically; memory management is automatic. Vector is the simplest of the STL container classes, and in many cases the most efficient. The important part to remember about a vector is that it is a dynamic array it’s size isn’t determined at compile time. Though these constraints on how a vector acts are important because we will be building a vector class through out this article and will need to make reference to them later. So here they are for reference:
Constrains of a vector
1) Random Access to all of it’s elements
2) Amortized constant time insertion and removal of elements at the end
3) Linear time insertion and removal of elements at the beginning or in the middle
[1] Definition:
SGI: Silicon Graphics, Inc is a company that specializes in software and hardware one could say their company is roughly equivalent to Sun Microsystems. They helped developed a good portion of the standard template library and are still developing extensions for it. In fact in the next iteration of the C++ standard it will be likely that most of the extensions developed by SGI will become standard. SGI also offers a most excellent documentation of the standard template library that can be found at http://www.sgi.com/tech/stl/
The first rule states that if you must have random access to all of its elements meaning that you must contain the vector’s elements in an array. This is the easiest part because we all know how to write an array. Though managing the array so it is dynamic can be the tricky part.
The second rule is a little bit more complicated then the first, it states that you must have amortized constant time insertion and removal of elements at the end. The word amortized may confuse you a bit because if you look up the definition in the dictionary it will refer to the term that bankers use. Dictionary.com definition of amortized is “To write off an expenditure for (office equipment, for example) by prorating over a certain period.” In reference to our vector, this means that when you insert an element at the end of the vector the work used to prepare for insertion should be spread over time.
What does it mean to have constant time insertion, and what exactly is constant time? That means no matter how many elements are in the list it will take the same amount of time to insert into the back of the list if there was 500 elements or if there was none. Particularly in Big O notation it should only take O(1) to insert into the back of the list. Though luckily the rule doesn’t state just pure constant time insertion it asks for amortized constant time insertion. This means that when we insert elements in the back of the vector there may be some extra work to prepare for the insertion so it wont always be O(1) to insert, but by some magic hand wavery we are able to do constant time insertion.
Finally the last rule states that we must have linear time insertion and removal of elements at the begging or middle of the vector. So what’s the difference between linear and constant time insertion? Well constant time insertion says that when inserting an element it must take the same time independent of the size of the vector. On the other hand linear time insertion will allow insertion to take a certain time depending on the vector size. So if the size of the vector was 10 then linear insertion may be O(10) and if the size of the vector was 100 it would take O(100). Formally the Big O notation used is that linear time insertion on a vector should take O(n+1).
Templated Class Definition
Enough talking about all this theory jibberish, let’s drive the nail through the wood by seeing some code. So let’s get straight to business and look at how a generic class is defined. It doesn’t look much at all different then a function declaration ( or definition for that matter ) so this should be easier to comprehend.
Quote:
template <typename T>
class Vector
{
public:
Vector( );
~Vector( );
T& operator [] ( const unsigned int index );
private:
T elements[100];
unsigned int size;
};
