Deterministic Parallel Haskell

A comparison of different approaches to deterministic parallel programming in Haskell

---

Introduction

When I started out with Parallel Haskell I saw that there where many different ways of doing it (Eval Monad, Par Monad, Accelarate, Repa) and along with that came a whole lot of new terminology, as it often is with Haskell. With this tutorial I hope I can help prospective students of Parallel Haskell understand a part of it that I consider to be key to understanding the rest of the ways. So if you wonder what the heck the difference is between Conservative parallelism and Speculative evaluation, why we need the Eval Monad when we already had a good model with par and seq, or what the difference between the Par Monad and the Eval Monad in practice is, how the spark pool works and nevertheless WHAT IT IS, continue reading…

This tutorial assumes some prior knowledge of functional programming in Haskell (specially function composition), what Monads are and Lazy evaluation (i.e the difference between Normal Form and Weak Head Normal Form). I will mostly focus on par/seq/pseq, Strategies, the Eval Monad, and then the Par Monad. I will also defer intentionally from some important aspects of parallel computation like the NFData type and the force function (even if I will slightly touch upon it). I think in the beginning it would only add more confusion to get into it and make the reader miss the forest for the trees. I would recommend a student to start with this tutorial and then afterwards move on to these topics to have a separation of concerns ;-).

Deterministic, parallel, what?

We distinguish between parallelism and concurrency. A parallel program is simply a comuptation of a problem that is split into different parts, where each part is computed in parallel on different CPU:s like when rendering an image. A concurrent program is a program that is split into independent threads that can do the same thing or different things (not necessarily in parallel) and can communicate with eachother, a server taking requests or sending replies, for instance.

A parallel program is by definition deterministic since the result of it always should be the same regardless of wheather you run it today or tomorrow. A concurrent program is non-deterministic by nature since the time for the individual computations on the separate threads can´t be known beforehand. In this tutorial we only focus on deterministic parallelism, for which Haskell is specially very well suited.

A Brief history lesson

par and seq was introduced into Haskell before the Monad had come along. This is the main reason for why there is a Eval Monad today with a similar rpar and rseq. When monads came along the old way was found to be insufficient. But before we look at the new model we will start by looking at the old models components, par and seq. These are the most low level parts of parallel Haskell, the other parallel models build on top of these. We start with par.

par :: a -> b -> b

par simply sparks its first argument and returns its second argument. This function only tells the compiler that the first argument can be evaluated in parallel with something else, nothing more. It does not say with what or when or that it must be evaluated in parallel at all. The spark could still be garbage collected and thus be evaluated in the normal sequential way. This is why we also have seq.

seq :: a -> b -> b

seq helps us with the evaluation order. It says that only b can be evaluated if a has been evaluated. The use could be illustrated when doing a heavy computation like calculating a fibonacci series. The crux is that this evauation will be to WHNF (Weak Head Normal Form) so the work will in most cases be lesser than you think. Here is an example.

maximum' [x]    = x
maximum' (x:xs) = max x (maximum' xs)

minimum' [x]    = x
minimum' (x:xs) = min x (minimum' xs)

homogenList []    = error "Lack of elements"
homogenList [x,y] = x == y
homogenList xs    = (min `par` max) `seq` (min == max)
    where min = minimum' xs
          max = maximum' xs

This is a stupid example, but still, it illustrates the point. In the example par evaluates to max and seq evaluates to min == max so the whole expression evaluates to a boolean. Now this definition of homogenList must surely mean that min and max are evaluated in parallel before their results are compared for equalitey, RIGHT?

Well, think again…

Remember that par does not make any guaranties of when to run the first argument, only telling the runtime system that it is possible to do it in parallel if there are idle processors ready to work. So while the processor starts evaluating max it will probably start evaluating min in parallel in this case, but there are still no guarantees. 2 good rules of thumb when thinking of using par are:

• The value of 'a' in par a b is likely to be required later, but not immediately.
• 'a' is not a trivial computation, so the cost of running it in parallel does not overshadow the benefits obtained by running it in parallel.

Some definitions you must understand

Control-oriented parallelism

forceList :: [a] -> ()
forceList [] = ()
forceList (x:xs) = x `seq` forceList xs

pQuicksort []      = []
pQuicksort [x]     = [x]
pQuicksort (x:xs)  = (forceList losort) `par`
                      (forceList hisort) `par`
                      losort ++ (x:hisort)
                          where
                            losort = pQuicksortF [y|y <- xs, y < x] 
                            hisort = pQuicksortF [y|y <- xs, y >= x]

pQuicksort is an example of (divide-and-conquer) control-oriented parallelism where part of the functions are evaluated in parallell (since x is not evaluated in parallel). The use of forceList may be slightly confusing but you can think of it as forcing the List argument to be fully evaluated to Normal Form. This is also what the function force does, btw. Forcing the evaluation of parts of the datastructure is often necessary when doing parallel programming in Haskell because if you dont that lazy basterd of Haskell will only evaluate expressions to WHNF in parallel => Not much Parallelism. Also remember that you dont want to do too much forcing since then you loose the beautiful aspect of laziness, not doing unecessary stuff. But we wont speak of that any more, promise, and I think this is all you need to know by now. Let´s stick to the point.

Data-oriented parallelism

Data-oriented parallelism is an alternative approach where elements of a data structure are evaluated in parallel. It is about doing the same computation to every element of the data structure and can therefore be done independently from eachother.

parMap :: (a -> b) -> [a] -> [b]
parMap f [] = []
parMap f (x:xs) = fx `par` fxs `seq` (fx:fxs)
                      where
                        fx = f x
                        fxs = parMap f xs

fx is sparked, before recursing down the list (fxs), only returning the first constructor of the result list after every element has been sparked.

3 important aspects

Parallelism control which specifies what threads should be created, and in what order, using par and pseq.

Evaluation degree which specifies how much evaluation each thread should perform, i.e how lazy you should let it be. In the examples above, forcing functions were used to describe the evaluation degree.

Thread granularity is important to spark only those expressions where the cost of evaluation exceeds the overhead of creating threads. This is usually controlled with the help of a threshold accompanying the function telling it when it should stop sparking new threads.

Conservative parallelism and Speculative evaluation

Conservative parallelism defines parallelized programs where the evaluation degree is the same as in the lazy counterpart. Speculative evaluation is when the evaluation-degree may usefully be more strict than the lazy function. So the more strictness is allowed compared to the lazy counterpart the more speculative the program is (The more of the program is evaluated unlazily). BTW, that´s why we also have pseq and not only seq. pseq is semantically identical to seq but is not strict in both its arguments, only in its first argument.

Parallelizing a program with strategies

par, seq and pseq are the main building blocks of the original parallel model. On top of this we have the Strategies abstraction, that helps us separate the algorithm that solves our problem from the strategy for parallelizing that (no pun intended). Strategies are composable, meaning that smaller strategies can be combined with other stratgies to form newer bigger strategies.

type Strategy a = a -> ()

So a strategy is simply a function from a -> () and all it can do is evaluate parts of 'a' and return unit. To apply a strategy we normally use the using function.

using :: a -> Strategy a -> a
using x s = s x `pseq` x

Notice what the function does. It takes the argument x forces, does something and returns x. This something could be done in parallel or not, the function is not interested, only that it does it sequentially (therefore the pseq). Here is an quick example of how to use it.

parList :: Strategy a -> Strategy [a]
parList strat []     = ()
parList strat (x:xs) = strat x `par` (parList strat xs)

parMap :: Strategy b -> (a -> b) -> [a] -> [b]
parMap strat f xs = map f xs `using` parList strat

This shows how strategies can be composed (parList takes a strategy and returns a strategy for lists), and it also shows how strategies can separate the algorithm from the evaluation strategy (on the left of using we have the algorithm for lists and on the right the strategy).

Memory management and the Sparkpool

So what does it actually mean that the expression 'a' in par a b is sparked? How is it implementation look like?

Well, in practicality it means that a pointer in the Sparkpool is created that points to the same expression in your program (the heap) so the runtime system knows what the programmer wants to run in parallel. A spark is a kind of lightweight thread (a thread spawned on application level with help of an API and therefore not a OS threadx). The sparkpool consist of all the expressions that the idle processors can take from and evaluate in parallel. If the sparkpool would be empty and a processor become idle it could "steal" a spark from another processors queue of sparks. So whenever an idle processor starts evaluating a spark it only needs the pointer to start evaluating it, very simple, isn´t it?

The Garbage Collector can treat sparks as either WEAK or ROOT. WEAK means that the garbage collector will throw away sparks if they are not referenced by some other pointer in the heap. If we apply a WEAK policy for the sparks then no parallelism will occur in the case of, for instance, parList since all the elements in the list are only sparked for the purpose of being evaluated in parallel. ROOT means that the garbage collector will always consider sparks as being live, and because not all expressions will be evaluated this means that the garbage collector will retain unecessarily many sparks which leads to a space leak.

Fizzled sparks are sparks that already refer to values and cant no longer be evaluated in parallel. This could be because of the time the value of an expression was needed no idle processors was available and the expression had to be evaluated in the normal sequential order. The garbage collector should throw away all fizzled sparks since they are unnecessary but since the expressions are wrapped in expressions of 'using' strat x and therefore are only partly evaluated they are almost never fizzled (refering to a value instead of an expression). The new parListWHNF is noncompositional in contrast to parList which makes the strategy apply directly to the datastructure and makes it possible to fizzle.

Speculative parallelism will under the ROOT policy become a space leak, whereas under WEAK policy will be reclaimed by the garbage collector, if not used, and therefore we can only use the WEAK policy. So what we want at this point is to somehow reclaim unecessary sparks but without reclaiming the useful ones.

So, in conclusion when a spark is created there is a pointer in the sparkpool pointing to the spraked expression but nothing in the heap (your program) that points to the sparked expression. In your heap you only have the pointer to the expression you passed to the strategy. And this is the main problem. We need somehow to still have a pointer to the expression in our program to the same expression that the spark in the sparkpool points to so that the garbage collector can do its normal work with the space leaks: the unnecessary unevaluated expressions and the fizzled sparks.

Eval Monad to the rescue

The root of the problem with the old strategies was that it returned the unit type (). By just delegating the expression to the spark pool there was no way of reaching the expression in the heap. Therefore the authors of the new model created the Eval Monad which makes it possible to return the new expression together with the sparked computation, so that the sparked expression now is reachable from both spark pool and the heap. Sounds pretty sweet, huh. Well, yes and it is…

This means that we can actually do specaulative parallelism, since a speculative spark will only be retained as long as it is reachable from the heap, thereafter it will be garbage collected even if it still is pointed to by the sparkpool. Ok, enough talk, this is mama´s brand new bag!

data Eval a = Done a

instance Monad Eval where
    return x = Done x
    Done x >>= k = k x

runEval :: Eval a -> a
runEval (Done a) = a

Eval is our new Evaluation Monad. And anothing important difference is that the new strategies are now the basic building blocks.

rpar :: Strategy a
rpar x = x ‘par‘ return x

rseq :: Strategy a
rseq x = x ‘pseq‘ return x

And this is how we use them

homogenList []    = error "Lack of elements"
homogenList [x,y] = x == y
homogenList xs    = runEval $ do
    min <- rpar (minimum' xs)
    max <- rseq (maximum' xs)
    return (min == max)

Here we see the stuff we were discussing before. min and max are now the new sparked expressions that we could not reach before and consequently not garbage collect. min and max will now not be garbage collected as long as our program is using does variables. Nice to know, huh. Yes it is… Yes it is.

Also, before we did not know when, and with what the spark would be parallelized with, but now the evaluation order is in respect to eachother which brings back some of the control to the programmer. The using function to separate the strategy from the algorithm now looks like this.

using :: a -> Strategy a -> a
x ‘using‘ s = runEval (s x)

parList and parMap that we looked at before now are defined in the following manner.

parList :: Strategy a -> Strategy [a]
parList s = evalList (rpar . runEval . s)

evalList :: Strategy a -> Strategy [a]
evalList s [] = return []
evalList s (x:xs) = do 
    x’ <- s x
    xs’ <- evalList s xs
    return (x’:xs’)

parMap strat f xs = map f xs `using` parList strat

All this is sound very promising, I think I´ll buy it… Wait, there are unfortunately still some problems with this. Remember the determinism stuff I mentioned before? Well, unfortunately this new model breaks those guarantees of determinism that COULD be kind of important, of course depending on the program, if it´s responsible for the cooling of a nuclear reactor or cooling of a sweaty monkeys butt. Here is what I mean.

a `par` b  ==  b

is still true.

x `using` strat == x 

is FALSE. In the original strategies model it was true but now 'strat' could return a different value. Look back at the definition of using and think about it for a while. In that monadic computation a different value could be returned. That was also the reason for creating the Eval Monad. The authors wanted the a new value that contained the sparked expression. But now there is no way of controlling weather that value is the same as before.

Wait, don´t worry. There is a remedy to this. But it will cost you, just a little bit. The cost is that you won´t be able to construct your own strategies now, but you will still be able to use them. This is done by restricting the user to a subset of the API that is safe for use so that this guarantee of determinism is upheld. Most uses of the strategies will only need this safe API to do their thing. This doesn´t sound so bad, does it? Consider the gains.

Par Monad?

WTF! A NEW Monad for parallelism, what was wrong with the one I just saw? I guess that you think that by now you are missing some big point. But don´t worry. You aren´t. The reason for the Par Monad is to gain some other advantages that the Eval Monad misses, as it is being used for lazy datastructures.

The Par Monad could be said to handle fully evaluated bulk data, where the programmer knows laziness won´t help. The Eval Monad or strategies consumes lazy datastructures, so the programmer needs to know where to force the evaluation and where to let it be non-strict. With the List type this is often not so hard since we know that the head is often evaluated by patternmatching or something, while the tail is zipping pina coladas. It becomes harder to guess this, though, the more complex the datastructure becomes.

The Par Monad is a high abstraction that helps us with this.

newtype Par a
instance Applicative Par
instance Monad Par

runPar :: Par a -> a

The Monad does not do any IO or something crazy like that, it only runs the parallelism of the computation and returns the expression. Like the Eval Monads strategies we are abstracted from the details so that the computations are guaranteed to be deterministic. To create parallelism we use fork.

fork :: Par () -> Par ()

We use the same terminonlogy as in concurrent programming. We say that function fork is the parent of the argument (the child). To get the results from the child to the parent we use a I-stucture called IVar.

data IVar a

new :: Par (IVar a) 
get :: IVar a -> Par a
put :: NFData a => IVar a -> a -> Par ()

put takes an IVar writes to it a value 'a' to it. This can only be done once. get takes the IVar and returns the value when put has computed it. Remember that this is done in parallel. So this models what is called futures and promises. Do you see that NFData type in put, wonder why its there? You maybe noticed it before? Well it is a class type that says that the argument a can be forced to Normal Form (NF, get it?). The reason for having it is that put is strict and evaluates its argument to Normal Form. If you don´t want this you can use the less strict little brother put_, that evaluates to WHNF. This is an example of how it works.

homogenList []    = error "Lack of elements"
homogenList [x,y] = x == y
homogenList xs    = runpar $ do
    minVar <- new 
    maxVar <- new
    fork (put minVar (minimum' xs))
    fork (put maxVar (maximum' xs))
    max <- get maxVar
    min <- get minVar
    return (min == max)

fork and IVar form a dataflow network.

Another example of when

Some other comparisons with Strategies

Some "behind the scenes"-looks tells us that the runPar function is a little bit more expensive than the runEval, that is free of charge. So when using the Par monad you should try to put the Par monad around to all the places that need parallelism and avoid multiple calls to runPar. Because of this high overhead cost you should try to control ranularity more carefully with the Par Monad by putting a threshold on when a forking should stop. Where to put this threshold is usually found by expermintation with threadscope. The Eval monad has more diagnostics in ThreadScope. There are graphs that show different aspects of sparks: creation rate, conversion rate, and so on. The Par monad is not currently integrated with ThreadScope.

Thing not mentioned but worth looking up

High performance, regular, multi-dimensional, shape polymorphic parallel arrays: Repa

GPU programming: Accelerate

I hope you enjoyed the tutorial and that some of the confusion was diminished.

References

Paper: Algorithm + Strategy = Parallelism P. Trinder, K. Hammond, H.-W. Loidl, and S. Peyton Jones

Paper: Seq no more: Better Strategies for Parallel Haskell S. Marlow, P. Maier, H.-W. Loidl, M. Aswad, and P. W. Trinde

Paper: A Monad for Deterministic Parallelism S. Marlow, R. Newton, and S. Peyton Jones

Paper: Parallel and Concurrent Programming in Haskell S. Marlow

hackage: pseq/par

Paper: Deterministic parallel programming with Haskell D. Coutts and A. Löh

Book: Parallel and Concurrent Programming in Haskell S. Marlow

4. Iterators and functionobjects

Container classes, Iterators, Function objects and their algorithms

First class containers and adapter classes

Container classes are another word for builtin abstract datatypes. They live in the C++ Standard Template Library (STL). When we talk about sequential container classes we talk about vector, deque (double ended queue) and list.

• template <class T> class vector
• template <class T> class deque
• template <class T> class list

And then we have the asscociative container classes map, multimap, set and multiset. The difference between the two classes map and set and their corresponding multi-counterparts is that in the single case, a stored key must be unique and in their multi-counterpart the class can store the same key multiple times.

• template <class Key, class T, class Cmp=less<Key> > class map
• template <class Key, class T, class Cmp=less<Key> > class multimap
• template <class T, class Cmp=less<T> > class set
• template <class T, class Cmp=less<T> > class multiset

These classes are all builtin template classes and can therefore be instantiated with different class types, they are therefore referred to as container classes. For example vector can be instantiated like:

vector<int> intvec;
vector<Person> persvec;                
// Assuming we have a Person class

And a set can be instantiated like:

set<string, int> set1;                 
// sorted by ascending alphabetic keys
set<string, greater<key> > set2;       
// sorted by descending alphabetic keys

And map:

map<string, int> map1;                 
// sorted by ascending key
map<string, int, greater<key> > map2;  
// sorted by descending key

They all represent data in different ways, why they have different methods for access and modification.
Then lastly we have the container adaptors. They are constructed by using one of the sequential containers (vector or deque) and adapting its interface to provide the desired behaviour.

• template <class T, class Container = deque<T> > class stack
• template <class T, class Container = deque<T> > class queue
• template <class T, class Container = vector<T>, class Cmp=less<T> > class priority_queue

The Container type deque and vector are only default for the adaptors and if you want to change the underlying container type, you can.

Iterators and Functionsobjects

Iterators

The concept of an iterator is fundamental to understanding the C++ Standard Template Library (STL) because iterators provide a means for accessing data stored in container classes such a vector, map and list. Since all containers have different representations C++ provides iterators for all the container classes that act as pointers do when used together with arrays. You should know by now that you instead of using array[3] can use *(array+3) and iterate through an array using the idiom array++ and array--. This functionality is what iterators provide for all the containerclasses. You use iterators the same way you use pointers to an a array when iterating over it.
All containers supports the function called begin(), which will return an iterator pointing to the beginning of the container (the first element), and the function end(), that returns an iterator corresponding to having reached the end of the container. You access the element by "dereferencing" the iterator with a *, just as you would dereference a pointer. In fact, because of the similarities between pointers to arrays and iterators you can use pointers to arrays in the same functions that require an iterator to a collection.
Example usage of an iterator over vector:

using namespace std;

vector<int> myIntVector;
vector<int>::iterator myIntVectorIterator;  // Declare the iterator

// Add some elements to myIntVector
myIntVector.push_back(1);
myIntVector.push_back(4);
myIntVector.push_back(8);

for(myIntVectorIterator = myIntVector.begin(); 
    myIntVectorIterator != myIntVector.end();
    myIntVectorIterator++)
{
    cout<<*myIntVectorIterator<<" ";
    //Should output 1 4 8
}

Example usage of an iterator over map:

#include <iostream>
#include <map>
#include <algorithm>
#include <string>

int main()
{
  string word;
  map<string, int> wmap;

  // Add some word and increase the counter associated to it
  while (cin >> word) wmap[word]++;

  for( map<string,int>::iterator i=wmap.begin(); i!=wmap.end(); ++i)
    cout << i->first << " " << i->second << endl; // first=key, second=value

}

Many of the algorithms in the STL expect iterators as arguments. Here we use the function reverse from the STL.

vector<char> vec(string str)
{
    const char *s = str.c_str();              // returns a (char *) 
    vector<char> x;
    while (*s != '\0')
        x.push_back(*s++);                    // put the char at the end of the vector
    return x;
}

int main()
{
    vector<char> vector1 = vec("mark twain");
    reverse(vector1.begin(), vector1.end());  // reverse uses iterators
    for(int i=0; i<vector1.size(); i++) 
        cout << vector1[i];                   // outputs "niawt kram"
    cout << endl;
}

The function reverse requires iterator pointers to reverse the container, what ever it might be, and like we stated before, you could instead of using an container use an array with the same function that requires an iterator like reverse(array, array+7) if the array was of size 7, or reverse(array, array+4) if you only want to reverse the first 4 elements.
To end this section we illustrate the power of iterators when used together with streams. Here we introduce the isteam_iterator and the ostream_iterator.

#include <iostream>
#include <fstream>
#include <list>
#include <vector>

#include <algorithm>

class BookEntry {
private:
  char name[32]; // let's skip dynamic allocation for once
  int num;
public:
  BookEntry() { strcpy(name,""); num = 0; }
  BookEntry( char *nam, int nu ) : num(nu) { strcpy(name,nam); }
  const int number() const { return num; }

  friend ostream& operator<<(ostream &os, const BookEntry &be )
    { return os << be.num << " " << be.name;  }

  friend istream& operator>>(istream &is, BookEntry &be )
    { return is >> be.num >> be.name; }
};

bool lessthan( const BookEntry &b1, const BookEntry &b2 )
{
  return b1.number() < b2.number();
}

int main()
{

  ifstream is1("book1");
  ifstream is2("book2");
  ofstream os("book1and2");

  istream_iterator<BookEntry> in1(is1);
  istream_iterator<BookEntry> in2(is2);
  ostream_iterator<BookEntry> out(os,"\n");
  istream_iterator<BookEntry> eofin;

  list<BookEntry> lbe( in1, eofin );
  vector<BookEntry> vbe( in2, eofin );
  sort( vbe.begin(), vbe.end(), lessthan );
  lbe.sort( lessthan );
  merge( lbe.begin(), lbe.end(), vbe.begin(), vbe.end(),
         out, lessthan);
}

So if book1 has the following content:

150919 Andersson
451209 Eriksson
560912 Johansson
401210 Karlsson
132816 Nordin
110111 Persson
331122 Svensson

And book:

567891 Alfredsson
120912 Edvardson
121212 Lundberg
119991 Nilsson
811111 Olsson
980912 Zaric

Then book1andbook2 will look like:

110111 Persson
119991 Nilsson
120912 Edvardson
121212 Lundberg
132816 Nordin
150919 Andersson
331122 Svensson
401210 Karlsson
451209 Eriksson
560912 Johansson
567891 Alfredsson
811111 Olsson
980912 Zaric

Functionobjects

Imagine we want to iterate through an vector of ints until we find an element greater than 4, and return a corresponding vector that starts with this value, so that if we give [1,2,3,4,5,6,7] we get [5,6,7]. For this we could use find_if that takes two iterators and a predicate (a function that returns either true or false given a certain input).

bool GreaterThan4( double v )
{
  return v > 4.0;
}

void myfunc( vector<double>& v )
{
  vector<double>::iterator f = find_if(v.begin(),v.end(), GreaterThan4);
  // do something with f
}

But what if we now want to find an element greater than 5 or 6. We would now need to write GreaterThan5 and GreaterThan6. This is what functionobjects alleviate us from. Functionobjects are objects whose classes have overloaded the ()-operator (the function call operator). Now when the object is called with the ()-operator it does something with its data or anything it wishes. This is sometimes more practical than passing a function to a function which you also can do, in a typical functional style.

#include <iostream>
#include <vector>
#include <algorithm>
#include <iterator>

using namespace std;

template <class T>
class GreaterThan {                                      // our function class
    public:
        GreaterThan( T cv ) : compValue ( cv ) {}        // set the value to compare with
        bool operator()( T v ) { return v > compValue; } // function call operator
    private:
        T compValue;
};

template <class T>
void myfunc( vector<T>& v, T val)
{
    GreaterThan<T> gt(val);                              // our function object
    typename vector<T>::iterator f = find_if(v.begin(), v.end(), gt);
    // do something
    cout << *f << endl;
}

int main()
{
    int arr[] = {1,2,3,4,5,5,6,7};
    vector<int> vec(arr, arr+7);
    myfunc<int>(vec, 4);
}

Algorithms

We have now seen the the power of algorithms such as find_if from the STL that takes iterators and functions/functionobjects as parameters. There are ofcourse many more algorithms that provides similar functionality for us to take advantage of. We will loke briefly at foreach that helps us do something "foreach" element in the container.

template <class In, class Function>
Function for_each (In first, In last, Function f)
{
    while (first != last) 
        f(*first++);
    return f;
}

You maye will find the class In and Function confusing. Function only implies that the function requires a class that has overloaded the ()-operator (a functionobject) or get passed a function (not a member function) to use over the elements. In specifies that the parameter in the actual call expects an Iterator. Here are the typical meanings of the parameters in C++ built in algorithms:

• In - InputIterator
• Out - OutputIterator
• For - ForwardIterator
• Bi - Bidirectional iterator
• Ran - Random-access-iterator
• T - element type
• Op - function/functionobject
• Pred - predicate (function/functionobject) (true/false)
• BinOp - binary operation
• BinPred - binary predicate
• Cmp - compare like binary predicate
• Gen - function that takes no parameters with returntype T
• Size - int

Here are some examples of algorithms from the <algorithm> file:

• For search(For,For,For2,For2); - serches for the sequence For2 in the sequence For.
• bool equal(In,In,In2); - true if all elements in the sequence In is pairwise equal to In2.
• Out transform(In,In,Out,Op); - apply Op on all elements.
• For remove_if(For,For,Pred p); - delete all elements in sequence that fulfills the predicate.
• bool binary_search(For,For,T& v); - return true if v is in sequence.
• Out merge(In,In,In2,In2,Out); - merges 2 sorted sequences.
• void sort(Ran,Ran,Cmp); - sorts the elements with Cmp.

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

class Sum {                   // Functionobject class for summing
    public:
        Sum(int i=0)  { sum = 0; }
        void operator()( int x ) { sum += x; }
        int operator()(void) const { return sum; }
    private:
        int sum;
};

class Printer {               // Functionobject class for printing
    public:
        Printer(ostream& oss) : os(oss) {}
        void operator()( int x ) { os << " " << x; }
    private:
        ostream& os;
};

int main()
{
    int arr[] = { 1, 3, 4, 2, 9, 7, 8, 6, 5 };
    vector<int> vec( arr, arr+9 );        // vec = arr

    Printer printer(cout);
    for_each( arr, arr+9, printer );
    cout << endl;

    sort(arr,arr+9);
    for_each( arr, arr+9, Printer(cout) );
    cout << endl;
    Sum sum = for_each( vec.begin(), vec.end(), Sum() );
    //The function object is passed by-value! 
    // we must use the return value!
    cout << sum() << endl;
}

In the include file <functional> there are builtin function objects that we can use with the algorithms in the inlclude file <algorithm>. Here is an example of the usage of multiplies and greater. Yes, greater also exists, so what we did before was indeed unnecessary.

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
using namespace std;

template <class T> class printer
{
    public:
          void operator()( T v ) { cout << v << endl; }
};

int main()
{
    vector<int> ivec;
    ivec.push_back(2);
    ivec.push_back(1);
    ivec.push_back(5);
    ivec.push_back(10);
    ivec.push_back(4);

    multiplies<int> mul;
    cout << accumulate( ivec.begin(), ivec.end(), 1, mul ) << endl;
    cout << accumulate( ivec.begin(), ivec.end(), 1, multiplies<int>() ) << endl;

    sort(ivec.begin(), ivec.end(), greater<int>() );

    for_each( ivec.begin(), ivec.end(), printer<int>() );

}

Here is a summary of some common and useful function objects

• plus<T>
• minus<T>
• multiplies<T>
• divides<T>
• modulus<T>
• equal_to<T>
• not_equal_to<T>
• greater<T>
• less<T>
• greate_equal<T>
• less_equal<T>
• logcal_and<T>
• logical_or<T>

You can ofcourse write your own template functions that can either take functions or functionobjects as parameters. Here is an example of how you can make a function like this. We have called the function compare for simplicity, which is used for making a comparison between usage of this function together with functionobjects and functions.
With functions:

#include <cctype> // for toupper!
#include <iostream>
#include <string>

using namespace std;

template <class LT, class EQ>      // LT and EQ are either functions or functionobjects
int compare( string &str1, string &str2, LT lt, EQ eq )
{
    for (int i=0; i < str1.length() && i < str2.length(); i++)
        if ( !eq(str1[i],str2[i]) ) return lt(str1[i], str2[i]);
    return str2.length()-str1.length();
}

//template <class T> int lt(T a, T b) { return a<b; }
//template <class T> int eq(T a, T b) { return a==b; }

int eqcss( char a, char b) { return a==b; }
int ltcss( char a, char b) { return a<b; }

int eqcis( char a, char b) { return toupper(a)==toupper(b); }
int ltcis( char a, char b) { return toupper(a) < toupper(b); }


int main()
{
    string a = "Big", b = "bigiiie";
    cout << compare(a,b, ltcss, eqcss ) << endl;
    cout << compare(a,b, ltcis, eqcis ) << endl;
    return 0;
}

With functionobjects:

#include <cctype> // for toupper!
#include <string>
using namespace std;

template <class LT, class EQ>
int compare( string &str1, string &str2, LT lt, EQ eq )
{
      for (int i=0; i < str1.length() && i < str2.length(); i++)
              if ( !eq(str1[i],str2[i]) ) return lt(str1[i], str2[i]);
        return str2.length()-str1.length();
}

template <class T> class ltcss {
    public:
          int operator()( T a, T b) { return a<b;}
};

template <class T> class eqcss {
    public:
          int operator()( T a, T b) { return a==b;}
};

template <class T> class ltcis {
    public:
          int operator()( T a, T b) { return toupper(a)<toupper(b);}
};

template <class T> class eqcis {
    public:
          int operator()( T a, T b) { return toupper(a)==toupper(b);}
};

int main()
{
    string a = "Apple", b = "aple";
    cout << compare(a,b, ltcss<char>(), eqcss<char>() ) << endl;
    cout << compare(a,b, ltcis<char>(), eqcis<char>() ) << endl;
}

3. Operator overloading and Streams

Operator Overloading

Is a specific case of polymorphism in which some or all operators like +, = or == are treated as polymorphic functions and as such have different behaviors depending on the types of its arguments. Instead of writing:

add (a, multiply (b,c));

You can simply write

a + b * c;

The way to overaload a oprator (unary or binary) is (where @ represents a valid operator):

return_type operator@(argument_list)
{
    // ... definition
}

For example we have the following definition for our own array type.

arr.set(5, 19); // Element 5 gets value 19
int a = arr.get(7);

And now we want the following usage that we are used to.

arr[5] = 19;    
int a = arr[7];  

Then we would need to overload the []-operator like this:

// DynArray.h
class DynArray 
{
public:
  double & operator[](int index) { return array[index]; }
  double operator[](int index) const { return array[index]; }
private:
  double * array;
  int bufSize;
};

The reason for having two operator overloads is that we could create a method in our class DynArray later that would take another DynArray as parameter which is marked as const. Then we could not use methods that aren´t const methods. We would need this function then and the compiler would know we refer to this method when we index the const array.

Binary operators

Ex: +, -, *, /, +=, *=, ==, `!= etc.

DynArray operator+(const DynArray & arr) const;

Both the parameter and the object for the operation are declared as const. We make the addition to a third array and return that array. To save unecessary copies and memory we pass the parameter by "call-by-reference".

DynArray a,b,c;
c = a + b; 
c = a.operator+(b);  // both are equivalent

If you don´t want to return a new object but modify the existing object (*this).

const DynArray & operator*=(const double scale);

But why return a const DynArray? Well the reason could be that you simply dont want to enable modification of the result of the computation. With the declaration above the following is not possible.

 (v1 *= 3) = v2; // Not possible
 v1 = (v2 *= 5); // Possible

A best practice when deciding wheather to define a function or method is if the operator is changing the current object or not.

DynArray operator+=(const DynArray & arr) const; //method
DynArray operator+(const DynArray & arr1,        //func
                   const DynArray & arr2);

friend functions are functions declared to be friends of the class and can therefore access private variables and so on, but their definitions would be outside of the class.

class DynArray 
{
public:
  double & operator[](int index) { return array[index]; }
  double operator[](int index) const { return array[index]; }
  friend int sum (const DynArray&);
private:
  double * array;
  int bufSize;
};

//main.cpp
int main() 
{
    DynArray arr;
    ...
    ...
    sum(arr);
}

int sum (const DynArray& param)
{
    int sum = 0;
    for(int i = 0; i < param.bufSize; i++)  // bufsize is private 
        sum += param[i];
    return sum;
}

Unary operator

Writing unary operators is, thankfully, a little bit easier. Here we use the increment and decrement functions as examples. If you have methods where order of execution is important like postfix or prefix the way of doing it is by adding a dummy parameter to the postfix method (int).

DynArray operator++();       // prefix
DynArray operator++(int);    // postfix

Assignment operator

This one is a little bit special. The reason is that sometimes the inner variables of the object cannot so easily be copied.

DynArray objekt1, objekt2;
.....
objekt1 = objekt2; //makes a shallow copy

Here the inner array of object1 is a pointer to an array, this pointer will be copied over to object2. This is definitively not what we want. To make our own assignment operator we write:

const DynArray & DynArray::operator=( const DynArray &a);

//implementation
const DynArray & DynArray::operator=(const DynArray &arr)
{
  if (this != &arr) // allow self-assignment: a = a;
  {
      bufSize = arr.bufSize;
      delete[] array;
      array = new double[bufSize];

      for(int i = 0; i < bufSize; i++)
      {
         array[i] = arr.array[i];
      }
  }
  return *this;
}

The reason for returning *this is that you want to allow chained assignments objekt1 = objekt2 = objekt3;.

The copy constructor

There is a built in copy constructor in C++ for all objects, but this too has the same defect as the assignment operator, its shallow. This is constructor is usually called when:

1. initilizing objects with an other intance of the same class.
2. when passing arguments to functions without reference (call-by-value).
3. when returning objects from functions.

Example:

int main()
{
  string a = "Mickey", b = "Mouse";
  string Mickey(a);         // 1. copy constructor called
  string Mouse = b;         // assignment operator
  a = add(Mickey, Mouse);   // 2. copy constructor called
}

string add( string a, string b)
{
  string temp = a+b;
  return temp;              // 3. copy constructor called
}

Resolve for our array.

DynArray( const DynArray & a ); 
// defined copyconstructor (NOT "const DynArray a" => infinite loop)

int main()
{
  ...
  DynArray arr1;           // default.constr.
  DynArray arr2( 2, -99 ); // overloaded.
  DynArray arr3(arr2);     // copy.constr.
  DynArray arr4 = arr2;    // copy.constr.
  ...
}

The problem of not having one copy constructor can be quite hideous. Look at the following example.

int sum( DynArray a, int num)
{
  int sum = 0;
  for (int i=0; i < num; i++)
    sum += a[i];
  return sum;
}

int main()
{
  DynArray array;
  ... // put values
  cout << sum(array, nrOfElem);
  ... // do something else
}

Seems harmless, right. The parameter a in sum copies the array object. If you haven´t defined your own assignment operator then it will use the built in shallow copy operator which means that the private array pointer in the object will be copied too. Here comes the problem; the destructor of the copied object is called when sum ends at }. This means that everything will be destoryed and so the original array will not exist anymore either!
When passing parameters by reference to functions or constructors, be VERY careful about const correctness. Pass by non-const reference ONLY if the function will modify the parameter and it is the intent to change the caller's copy of the data, otherwise pass by const reference. There is a small clause in the C++ standard that says that non-const references cannot bind to temporary objects. A temporary object is an instance of an object that does not have a variable name.

 std::string( "temporary string" ); // temporary
 std::string s("object string");    // non temporary

Usually when you dont want outer classes or functions to use the copy constructor or assignment operator you could declare these as private to simply avoid these issues.

Streams

A 'stream' is internally nothing but a series of characters. Streams work with built-in data types, and you can make user-defined types work with streams by overloading the insertion operator << to put objects into streams, and the extraction operator >> to read objects from streams. For example to output "hello world" you write:

cout << "hello world" << endl;

Here cout is an instance of ostream. And for writing to a file you would use an ofstream:

ofstream file( "test.txt" );
if ( !file ) {
    cout << "An error occurred opening the file" << endl;
} else {
    file << "text written to the file: test.txt";
}

And if you for example are reading input from a istream:

int x;
if ( cin >> x ) {
    cout << "Please enter a valid number" << endl;
}  

And if you would like to copy the contents of a file to another:

ifstream infile("src");
if (infile)  
{
    ofstream outfile("destination");
    char c;
    while (infile.get(c)) 
      outfile << c;
}

And if you instead would like to read from a file you would instead use an ifstream and the >> operator. Here is a picture of the hierarchy.

The underlying low-level interface that corresponds to the actual medium is a character buffer (technically called the streambuf). Being a buffer, it does not hold the entire content of the stream (if the stream is large enough) so you can't use it for random access (but we will later see an example of an oddity of a stream that DO HAVE random access).
First, the stream is initialized with the appropriate type (like a std::string for a stringstream and the filename for an fstream) of values and suitable modes (like ios::in for input and ios::out for output and many more depending on the type of the stream). After that, you can specify where the I/O should occur, through the get and put pointers.

• seekg(0); seekg(0,ios::beg) //sets the get pointer to the beginning.
• seekg(5,ios::beg) //sets the get pointer to 5 chars forward of the beginning.
• tellp(); tellg() //returns the current value of the put/get pointer
• seekp(-10,ios::end) //sets the put pointer to 10 chars before the end
• seekp(1,ios::cur) //proceeds to next char

For all streams the put and getpointers have a natural position from the initialization for doing IO. But it is good to know how to modify them.
So when you want your class to be able to read input streams or write to outputstreams you always do it the same way. This is the beuty of streams, its always the same interface. If you want for example a Loggclass to be able to output to whatever storage you would need to only overload the << operator and take a ostream as parameter.

class LogStatement
{
public:
        LogStatement(std::string s): data(s), time_string( timestamp() ) {};

        //This method handles all the outputs.    
        friend ostream& operator<<(ostream&, const LogStatement&);   
private:
        std::string data;
        std::string time_string;

}; 

ostream& operator<<(ostream& ost, const LogStatement& ls)
{
        ost<<"~|"<<ls.time_string<<'|'<<ls.data<<"|~";
        return ost;
}

A thing to notice is that the << operator takes in an ostream object, modifies it and then returns it. This is an expected behaviour so that all streams can be called and chained together:

cout<<"Hey, I'm "<< n <<" years old.";

Remember we said that you can´t use streams for random access since the underlying buffer is hidden in the interface. Well there is a class of streams called random streams (rsteam) that allow the user to access this buffer. We will look at an example of rsteam called fstream that allow random access to a file. It is done by letting the fstream class be a hybrid between ifstream and ofstream and thus be able to do both input and output:

#include <iostream>

class testclass {
  double a[2];
  int b;
 public:
  testclass( void ) { a[0] = a[1] = 0.0; b = 0; }
  testclass( double a1, double a2, int i) 
    { a[0] = a1; a[1] = a2; b = i; }
  friend ostream& operator<< ( ostream &os, const testclass &tc)
   {
    return os << "{ " << tc.a[0] << ", " << 
       tc.a[1] << ", " << tc.b << " }";
   }
};

main()
{
  fstream<testclass> f1("testclass.data");
  fstream<int> f2("int.data");

  testclass t1(0.0, 1.0, 1);
  testclass t2(0.0, 2.0, 2);
  testclass t3(0.0, 3.0, 3);

  f1(2,t1);  f1(1,t2);  f1(0,t3); // index the underlying buffer

  cout << f1(0) << endl << f1(1) << endl << f1(2) << endl;
  f2(12,1200);
  f2(6,600);
  f2(0,0);

  cout << f2(0) << endl << f2(6) << endl << f2(12) << endl;
}

The output of this program would be:

{ 0, 3, 3 }
{ 0, 2, 2 }
{ 0, 1, 1 }
0
600
1200

2. Classes and templates

Classes

Classes in C++ is not very different from any other OO-language, besides the syntax and the preferable separation of implementation and definition of functions. Another thing to take into consideration is that instances of classes can either be statically instantiated or dynamically instantiated with pointers, like we saw being done with arrays. We have different kind of classes: composition, association and ofcourse inherited classes. We will look at these types and how they differ. After that we will delve into the topic of polymorphism.

Composition

A class that consist of other classes and belongs to the "has-a"-category.

class Dinner {
    public:
        Dinner();
        Dinner(char *name, char *name, int weight, );
        bool eat(int w);
    private:
        Food food;
        Drink drink;
};

class Food {
    ...
};

class Drink {
    ...
};

Association

"Use-a"-category. A class that is not composed of the other object but uses it, like when a manager employs a person. Both the employee and the manager are temporarily connected. The class has a pointer to the other class in practicality.

class Employee{
    int age;
    int name[30];
public:
    Employee()
    {
       cout <<" I am Employee" << endl;
    }
    // other stuff

};

class Manager{
    int x;
    Employee *ptr;
public:
    // other stuff
};

Inheritance

person.h

#ifndef PERSON_H
#define PERSON_H

#include <string.h>
#include <iostream>

using namespace std;

// copy strings
inline char *copyOf(char *s) {
  if (!s) return 0;
  char *n = new char[ strlen(s)+1 ]; // allocates spaces
  strcpy( n, s);
  return n;
}

class Person {
public:
  Person(char *n);
  Person(const Person &p);
  ~Person();
  bool equal(const  char *n);
  void show();
protected:
  char *name;
};

#endif

person.cpp

#include "person.h"

Person::Person(char *n) : name(copyOf(n)) 
{ cout << "Person " << name << "s constructor" << endl; }

Person::Person(const Person &p) : namn(copyOf( p.name)) 
{ 
  cout << "Person " << name << "´s copyconstructor"
    << endl; 
}

Person::~Person() 
{
  cout << "Person " << name << "´s destructor" << endl;
  delete[] name;
}

bool Person::equal(const  char *n) 
{ return ( strcmp(name,n) == 0);  }

void Person::show() 
{ cout << "Person " << name << endl; }

student.h

#ifndef STUDENT_H
#define STUDENT_H

#include "person.h"

class Student : public Person {
public:
  Student(char *n, char *c);
  ~Student();
  void show();
  const char *getCourse();
private:
  char *course;
};

#endif

student.cpp

#include "student.h"

Student::Student(char *n, char *c) : Person(n), course(copyOf(c)) // call to super class
{ 
  cout << course <<  "-student " << name << 
    "´s constructor" << endl; 
}

Student::~Student() 
{ 
  cout << course << "-student " << name <<
    "s destructor" << endl;
  delete[] course; 
}

void Student::show() 
{ cout << course << "-student " << name << endl; }

const char* Student::getCourse()
{ return course; }

and now the test program

#include "student.h"

int main()
{
  Person p1("Adam");
  Student p2("Eve", "Physics");

  p1.show();
  p2.show();
}

//output
Person Adam`s constructor
Person Eve`s constructor
Physics-student Eve`s constructor
Person Adam
Physics-student Eve
Physics-student Eve`s destructor
Person Eve`s destructor
Person Adam`s destructor

We see that in the case of Eve that the Person constructor is first called and then the Student constructor since the student constuctor calls that constructor. When the object is destroyed the Student constructor is first called then the Person since destructors are called up in the hierarchy.

Polymorphism

Polymorphism is used when you let a object be declared as a baseclass (Person) and in runtime let it be specified as a child class (Student). This is also called late-binding as opposed to early-binding. There are some tricks to this, that may be surprising, specially if you come from Java.

#include "student.h"

int main()
{ 
  Student s1("Adam", "Biology"); 
  Person* ptr; 
  ptr = &s1;   // this is polymorphism!   
  s1.show(); 
  ptr->show(); 

  ptr = new Student("Cesar", "Cytology"); 

  cout<<"Program done, delete objects from memory"<<endl; 

  delete ptr;  
}  

//output
Person Adam´s constructor
Biology-student Adam´s constructor
Biology-student Adam
Person Adam
Person Cesars constructor
Cytology-student Cesar´s constructor
Program done, delete objects from memory
Person Cesar´s destructor
Biology-student Adam´s destructor
Person Adam´s destructor

We see that when the ptr-pointer calls the show method, as the pointer is declared as a Person object it calls the Persons show method. Another problem is when we delete the pointer we only call the Person destructor and not the Student destructor, which leads to a memoryleak. This problem is helped with the virtual keyword.

class Person {
public:
  Person(char *n);
  Person(const Person &p);
  virtual ~Person() {};      // inline definition
  bool equal(const  char *n);
  virtual void show();
protected:
  char *name;
};

Now that we declared the show method and the destructor as virtual methods we are telling the runtime system to wait with specifying what kind of class the actual object belongs to until runtime (late-binding). The new output is now correct.

Person Adam´s constructor
Biologi-student Adam´s constructor
Biologi-student Adam
Biologi-student Adam                     // now correct
Person Cesars constructor
Cytologi-student Cesar´s constructor
Program done, delete objects from memory
Cytologi-student Cesar`s destructor      // now called
Person Cesar´s destructor
Biologi-student Adam´s destructor
Person Adam´s destructor

Now you cannot make a constructor virtual because you need to know what kind of object you are creating. But what if you want to create a copy of the object but you don´t know the type? Well a wellknown pattern is to create a virtual clone method in the baseclass that the other childclasses inherit and overwrite.

class Person {
public:
    virtual Person* clone() = 0;  
    // Because of this definition we now call the Person class an abstract class. 
    // It cannot be instantiated itself, only the the child classes.
    ...
};

// Child classes
Student* Student::clone() { return new Student( *this); }
    ...

Employee* Employee::clone() { return new Employee( *this); }

And now you could do the following kind of thing.

 Person *s = new Student("Adam", "Archeology");
 Person *d = new Employee("Cesar");
 Person *s1 = s->clone(); // creates a copy of s
 Person *d1 = d->clone(); // creates a copy of d

If you are working with polymorphic types some time, you´ll maybe find yourself needing a way to cast that polymarphic type to its implementation class. In that case you could use the dynamic_cast<class *> function.

Circle *circle( Shape *s )
{
  return dynamic_cast<Circle *>(s);
}

If the function can´t cast the polymorphic type (Shape) to the implementation class (Circle) because the object is specified as something else (a Rectangle for instance) it will return a null-pointer instead as you would expect, otherwise a pointer to the object. Well, now you maybe wonder when would you need to do this? One example:

#include <iostream>

class Shape {
public:
  Shape( int xin, int yin) : x(xin), y(yin) {}
  virtual bool operator==( Shape &s) = 0;
private:
  int x,y;
};

class Circle : public Shape {
public:
  Circle( int xin, int yin, int r ) : Shape(xin,yin), radius(r) {}
  // bool operator==( Circle &c) WRONG!! You are NOT overriding the original
  // { return radius==c.radius; } 
  bool operator==( Shape  &s) // Right
    {
      Circle *c = dynamic_cast<Circle *>( &s);
      if (c) return c->radius == radius;
      else return 0;
    }
private:
  int radius;
};

class Square : public Shape {
public:
  Square( int xin, int yin, int s ) : Shape(xin,yin), side(s) {}
  bool operator==( Shape  &s) 
    {
      Square *sq = dynamic_cast<Square *>( &s);
      if (sq) return sq->side == side;
      else return 0;
    }
private:
  int side;
};

int main()
{
  Square q1(10,10,5);
  Square q2(20,20,5);
  Circle c1(30,30,5);
  Circle c2(30,30,4);
  cout << (q1==q2) << endl;
  cout << (q1==c1) << endl;
  cout << (c1==c2) << endl;
}

Include files and implementation files

You have now maybe start wondering or even had experience with those nasty definitionfiles and you maybe think of this as a nasty business. Here follows a summary of good habits to follow when working with this issue. I stole this from another blogpost that I thought summarized it very well. If you are interested in the subject this is the blogpost.

Classes you create will often have dependencies on other classes. A derived class, for example, will always be dependent on its parent, because in order to be derived from the parent, it must be aware of its parent at compile time.

There are two basic kinds of dependencies you need to be aware of:

1. stuff that can be forward declared
2. stuff that needs to be #included

If, for example, class A uses class B, then class B is one of class A's dependencies. Whether it can be forward declared or needs to be included depends on how B is used within A:

• do nothing if: A makes no references at all to B
• do nothing if: The only reference to B is in a friend declaration
• forward declare B if: A contains a B pointer or reference: B* myb;
• forward declare B if: one or more functions has a B object/pointer/reference as a parementer, or as a return type: B MyFunction(B myb);
• #include "b.h" if: B is a parent class of A
• #include "b.h" if: A contains a B object: B myb;

You want to do the least drastic option possible. Do nothing if you can, but if you can't, forward declare if you can. But if it's necessary, then #include the other header.

Ideally, the dependencies for the class should be layed out in the header. Here is a typical outline of how a "right way" header might look:

myclass.h

#ifndef __MYCLASS_H_INCLUDED__
#define __MYCLASS_H_INCLUDED__

// forward declared dependencies
class Foo;
class Bar;

// included dependencies
#include <vector>
#include "parent.h"

// the actual class
class MyClass : public Parent  // Parent object, so #include "parent.h"
{
public:
  std::vector<int> avector;    // vector object, so #include <vector>
  Foo* foo;                    // Foo pointer, so forward declare Foo
  void Func(Bar& bar);         // Bar reference, so forward declare Bar

  friend class MyFriend;       // friend declaration is not a dependency
                               //   don't do anything about MyFriend
};

#endif // __MYCLASS_H_INCLUDED__ 

This shows the two different kinds of dependencies and how to handle them. Because MyClass only uses a pointer to Foo and not a full Foo object, we can forward declare Foo, and don't need to #include "foo.h". You should always forward declare what you can -- don't #include unless it's necessary. Unnecessary #includes can lead to trouble.

Templates

Templates could be used by either classes or functions.

template functions

When a function is overloaded by different types, for example when defining a max function.

double max( double a, double b) { return (a>b) ? a : b; }
double max( int a, int b) { return (a>b) ? a : b; }

using a template function could be a better solution.

template <class T> T max(T a, T b) 
{ return (a>b) ? a : b; }

double m = max<double>(5.0, 4.3); // call to template function

If your type now wouldn´t have the compare function, like in the case of strings, you could specialize the function for that special case.

char *max ( char *a, char *s) 
{ return (strcmp(a,b)>0) ? a : b; }

The general syntax for template functions is:

template <class T, class Y, ..>
returntype name(parameterlist)
{
    ...
    return returntype;
}

template classes

For Classes the formal definition look similar:

template  <class T> class Name {...};

Here follows an example using a homegrown Array class.

array.h

#ifndef ARRAY_H
#define ARRAY_H

#include <stdexcept>

template  <class T> class Array
{  
public:
  Array (int sz );
  Array( const Array &arr);
  ~Array();
  T& operator[](int ix);
  Array& operator+=( const Array &arr );
  bool includes( T &item ); 
private:
  int size;
  T *a;
};

template <class T> 
Array<T>::Array ( int sz ) : 
  size(sz), a(new T[sz]) {}

template <class T> 
Array<T>::Array ( const Array &arr ) : 
  size(arr.size), a(new T[size]) 
{
  for (int i=0; i < size; i++) 
    a[i] = arr.a[i]; 
}

template <class T> 
Array<T>& Array<T>::operator+=( const Array &arr )
{
  if (size != arr.size) 
    throw length_error("Array: operator+=");
  for (int i=0; i < size; i++)
    a[i] += arr.a[i];
  return *this;
}

template <class T> 
Array<T>::~Array () 
{
  delete[] a; 
}

template <class T> 
T& Array<T>::operator[](int ix) 
{ 
  return a[ix]; 
}

template <class T> 
bool Array<T>::includes( T &item )
{
  for (int i=0; i < size; i++) 
    if (item==a[i]) return true;
  return false; 
}

#endif

Notice that we put both the implementation and the declaration in the .h file. This is an exception for template classes. We don´t need to declare these memberfunctions or methods with inline since the compiler does that automatically. With this definition we could now write something like the following.

Array<Person> persons = Array<Person> persons(10); // creates a Person array
Array<int> ints       = Array<int> ints(100);      // creates a int array

Just remember that all methods and functions in the template class need support for the functions and methods they assume the template class T has. Besides template classes you can also specify a valueparameter among the template parameters.

template <class T, int sz> class Array {
 public:
   Array();
 private:
   int size;
   T arr[sz]; 
};

//new constructor
template <class T, int sz> Array<T,sz>::Array() : 
  size(sz) {}

//usage
Array<int,50> intarr50;

This value parameter cannot be a float.

1. C++ Basics

C++ the basics

I have always looked upon people with knowledge in C++ as the true "hackers", and considered that you as a programmer really aren´t programming until you learnt to program in C/C++. I have read, as many other programmers probably have done before me, that to write an optimized program you have to write it in C/C++. And since C++ is OO and C isn´t I have also considered it to be even more profitable to learn C++ than C. This view may be true or or not, but because of it I have long had this itch for learning C++. I have mostly experience with Java from school, but I have also some experience of C and have done som basic assembly-programming in courses at my university. And besides my school programming I have mostly had experience in scripting languages such as Ruby, Python and Javascript.

Now, finally, during the spring I took a course on distance in C++ at the University of Uppsala that was very good. I feel I have learnt a lot during that time, but that may mostly be thanks to my teacher and specifically to his lecture notes. They where targeted at a experienced audience. I found that there were very little to be found similar to them online. It was my experience of lacking online-resources on C++ for experienced programmers that led me to create this blog. With experienced programmers I mean; programmers that have done some C, knows what calloc and malloc do and feel they understand the concept of pointers, they are comfortable in preferably Java or some other statically typed OO-language too.

I have created this blog mostly for the sake of documenting my own learning outcome, and also to save some other programmers time who, like me, want to learn C++ but have enough knowledge to skip the tutorials about for-loops and boolean expressions. I found my self a little bit sick of trying to open up a bunch of tabs with the different sections and articles of interest in tutorials, since a lot were too basic, and later find myself having too many tabs to feel I had gotten a thorough overview. I hope this can help them who want just the gist, without the superfluous information.

Pointers

A pointer is an adress to a memory location in the heap, or your RAM, to be more specific. All variables and objects have an adress.

int varible = 10;
int *pointer;           // not pointing at anything
pointer = &variable;    // pointing at variables adress

& operator gets the reference or the adress to a varible.

The pointer gets the reference to to the variable in this case. This means now that the pointer has the power to change the content of the memory adress. You do this by using the * operator, that says to the pointer to refer to the content and not the adress.

*pointer = 11;
std::cout << variable << endl; // outputs 11!

A pointer needs to be initialized before its used if you dont want it to use some other objects adress. In the example above we used the variable adress so we did not need to do this. When initializing a pointer you do it with the new operator. This is called dynamic allocation as it is done in runtime and not compile time.

char *c = new char;      // dynamic alloc (one char)
*c = 'a';
int size; 
cin >> size;             // get size from input
int* myArr; 
myArr = new int[size];   // dynamically alloc (array)

A common mistake is thinking that you can use uninitialized pointers.

int *ip; 
*ip = 12; // Gives error!

If we are using some other objects adress we would normally use the null-pointer until we assign 0 to the pointer to show that it is not pointing at anything:

int pointer = 0;

When you dynamically assign memory to objects you should be careful to return the memory by delete. If you don´t return memory it becomes a spaceleak in your program since no other object can now occupy the space you used.

delete c;        // deletes space pointer used.
c = 0;           // good practice
delete[] myArr;  // deletes space array used.
myArr = 0;

Pointers need to be consistent with their type. You can not use a double pointer to point at a int for example.

int i;
double *dpointer = &i // forbidden!

The * operator belongs to the variable and not to the type, this is something that could be quite confusing too.

int *a, b;  // b == int
int *c, *d; // d == int pointer

To handle this kind of thing a good practice is to use typedef.

typedef int *intPointer;  // new int pointer type
intPointer ip1, ip2;      // both are now int pointers

Arrays

You can use pointers to index an array!

int myArr[6]; 
int* myptr; 
myptr = &myArr[0]; // myptr points at myArr[0] 
myptr++;           // myptr == myArr[1]
myptr++;           // myptr == myArr[2]
*myptr = 9999;     // myArr[2] = 9999

Actually when you are passing an array to a function that expects an array the variable you pass to that function decay to a pointer of the same type as the array.

void printarray (int arg[], int length) {
    for (int n = 0; n < length; n++) {
        cout << arg[n] << " ";
        cout << "\n";
    }
}

int main ()
{
     int firstarray[] = {5, 10, 15};
     int secondarray[] = {2, 4, 6, 8, 10};
     printarray(firstarray, 3); 
     printarray(secondarray, 5);
     return 0;
}

Here firstarray and secondarray in the function call decays to int pointers to the first element in the array. The expression int sum( int a[], int size); == int sum( int* a, int size);. You could also therefore do the following kind of thing as well.

int myArr[6]; 
int* myptr; 
myptr = myArr; // myptr and myArr points to same thing.
myptr[4]=314   // myptr can now be used the same way.
*(myArr+5)=315 // myArr can also be used as an pointer.

The two ways seem almost identical but with a small difference. The sizeof cannot be used on pointers, and you can not use the myArr variable like a pointer in increasing and decreasing the index.

sizof(myArr);   // the size of an array in bytes.
sizeof(myptr);  // space for the pointer in bytes.
myArr++;        // not allowed!

Matrixes

dynamic allocation

In C++ you cannot initialize an matrix dynamically in one statement like in other statically typed languages. Initialization of a matrix can only be done statically.

int *a = new int[3][3];   // forbidden!
int **b = new int[3][3];  // also forbidden!
int **c = new int*[3];    // OK!

What you need to do is to allocate an outer array of inner arrays first, and then in a loop allocate the arrays to the outer array. Tedious, I know, but this is one of those "facts of life"-moments.

int **mtrx = new int*[3]; 
for ( int i = 0; i < 3; i++ )
{
    mtrx[i] = new int[3];
}

And to delete the matrix you need to do it in the reverse order.

for ( int i = 0; i < 3; i++ )
  delete[] mtrx[i];
delete[] mtrx;

By using typedef in this context the benefits of typedef become much clearer.

typedef int intArray[3];  // defined type int[3]
intArray *mtrx = new intArray[3];  // matrix pointer 3*3
delete[] mtrx; 
// delete whole matrix in one statement because we used only one new.

Of course, you could still declare a matrix statically. Lets look at how its done.

static allocation

int[3][3] mtrx = {{1,2,3}, {4,5,6}, {7,8,9}}; //Ok

And the single statement int[3][3] mtrx1; is equivalent to int[9] array;. The reason for this equivalence is that in both cases the memory is allocated consecutively. When you dynamically allocate memory you do it where ever the memory manager finds memory available, meaning not necessarily consequetly. If you declare an matrix:

double a[40][30];

Now 1200 ints have been consecutively placed in memory. Then to find element a[i][j] it uses the formula a+j+i*30 to find the element. This means that the compiler does not need to know the size of the outer dimension, just the inner (30). Therefore you often see declarations like this:

int func( int rader, double a[][30]);

If you don´t statically initialize the array like above the content is garbage but if you would just initialize some part of it the rest would be initialized to 0:

int[3][3] mtrx = {1}; // mtrx[0][0] == 1, rest 0
int[3][3] mtrx2 = {}; // all 0

References

References are some kind of pointers too, but they must always refer to something, and cannot like pointers point to nothing. A common mistake with references is confusing the adress operaton & and the reference operator & that look the same.

int a = 10;
int *pointer = &a; // adress operator

Here the & refers to an adress. The reference operator & is mostly used as a parameter in functions to have an alias for the same varible.

void swap( int& a, int& b) // reference operators
{
  int c = a;
  a = b;
  b = c;
}

int i = 7;
int j = 3; 
swap(i, j); // i = 3, j = 7

Const and pointers

Some explanations regarding const and pointers.

const int a = 5; 
int b = 5;        

const int *p = &a; // a pointer to a const, 
                   // does not allow modification of the data through the pointer
*p = 4;     // Not allowed!

int* const pp = &b; // a const pointer, this pointer need to be assigned a value immediately.
                    // does not allow modification of the adress of the pointer
*pp = 5;    // Ok! 

const int *const ppp = &a;  // neither ppp or *ppp can change

Namespaces and the structure of C++ programs

Namespaces can be used to structure a program into "logical units". For instance, if you had a program that connected to the Internet, you might have a namespace to handle all connection functions.

the headerfile netconnect.h

namespace net_connect
{
  int make_connection();
  int test_connection();
  //so forth...
}

If you now include the header file that contains the namespace in your program file with #inlude "netconnect.h" you can call a function from the namespace with the scope operator ::.

net_connect::make_connection();

You can also introduce an entire namespace into a section of code by using a using-directive with the syntax:

using namespace net_connect;

Doing so will allow the programmer to call functions without having to specify the namespace of the function while in the current scope. (Generally, until the next closing bracket, or the entire file, if you put this in the global scope). This convenience can be abused by using a namespace globally, which defeats some of the purposes of using a namespace. You can typically see std being used this way to be able to handle IO without ever having to specify std::

using namespace std; 

Finally, you can introduce only specific members of a namespace using a using-declaration with the syntax

using namespace_name::thing;

Another trick with namespaces is to use an unnamed namespace to avoid naming conflicts. To do so, simply declare a namespace with the normal syntax, but leave off the identifier; when this is done, you will have

namespace
{
  //functions
}

and within the namespace you are assured that no global names will conflict because each namespace's function names take precedence over outside function names. Great!

Here follows an example of the usage of namespaces and also of how to structure a small C++ project.

The file msg.h (definitions)

#ifndef MSG_H
#define MSH_H

#include <iostream>
#include <string>

namespace msg
{
  void write( string msg );  // definition
}

#endif

The file msg.cpp (implementation)

#include "msg.h"

namespace 
{ 
  string header()
  { 
    return string("Info: "); 
  }
}

void msg::write( string msg )    // implementation
{ 
    cout << header() << msg << endl; 
}

The file error.h

#ifndef ERROR_H
#define ERROR_H

#include <iostream>
#include <string>

namespace error
{
  void write( string msg );
}

#endif

The file error.cpp

#include "error.h"

namespace 
{
  string header()
  { 
    return string("Error: "); 
  }
}

void error::write( string msg )
{ 
    cout << header() <<  msg << endl; 
}

And our example program:

#include "msg.h"
#include "error.h"

int main()
{
  msg::write("this is a message");
  error::write("this is an error");

  int smallerthan10(int i)
  {
    using namespace error;
    if(i > 10) {
        write("it was bigger!"); //will use error write.
        return 0;
    } else {
        msg::write("it was smaller!"); //will use msg write.
        return 1;
    }
  }
}

Intro to Classes, inline and the static keyword

We will not go into the details of how to work with classes but assume that you know what a class is. We will only show you the structure of a class. In the next chapter we will dwelve into how to work with classes in more detail.

If a function is inline, the compiler places a copy of the code of that function at each point where the function is called at compile time. The function should be compiled inline into where it is used (avoiding a function call overhead).

inline int Max(int x, int y)
{
   return (x > y)? x : y;
}

int main( )
{
   cout << "Max (20,10): " << Max(20,10) << endl;  //is now replaced at compile-time
   return 0;
}

If the definition of a method comes directly in the .h file the method is treated like an inline method, therefore when we define the function in the .h file and not only declare it we say we write the definition inline. In the following class declaration, the Account constructor is an inline function. The member functions GetBalance, Deposit, and Withdraw are not specified as inline but can be implemented as inline functions.

class Account
{
public:
    Account(double initial_balance) { balance = initial_balance; }
    double GetBalance();
    double Deposit( double Amount );
    double Withdraw( double Amount );
private:
    double balance;
};

inline double Account::GetBalance()
{
    return balance;
}

inline double Account::Deposit( double Amount )
{
    return ( balance += Amount );
}

inline double Account::Withdraw( double Amount )
{
    return ( balance -= Amount );
}

The staic keyword is a little bit trickier. It can be used in many contexts. static can be used in three major contexts: inside a function, inside a class definition, and in front of a global variable inside a file making up a multifile program.

If used inside a function it simply means that once the variable has been initialized, it remains in memory until the end of the program. You can think of it as saying that the variable sticks around, maintaining its value, until the program completely ends.

for(int x=0; x<10; x++)
{
  for(int y=0; y<10; y++)
  {
    static int number_of_times = 0;
    number_of_times++;
  }
}

In classes it can have different uses. It could be a variable that for example counts the number of the instances created of the class. If a method have the static keyword it could be a method that simply isn´t specific to a instance but to the class in general.

class User
{
  private:
    int id;
    static int next_id;

  public:
    static int next_user_id()  
    // declared static to be able to use next_id
    {
        next_id++;
        return next_id;
    }
    user()
    {
        id = User::next_id++;    // or, id = User.next_user_id();
    }
};
int User::next_id = 0; 

Notice that the next_id variable is initialized outside of the definition of the class. In fact, this must even be outside of the .h file or else you will get errors.

Exceptional programming

An exception is a situation in which a program has an unexpected circumstance that the section of code containing the problem is not explicitly designed to handle.

Exception handling in C++ propagates the exceptions up the calling-stack; therefore, if there are several functions called, but only one function that needs to deal with the errors, the intermidiate functions don't need to return error codes and can be totally oblivious of the errors that bubble up the stack.

When an errors occur, the function generating the error is said to throw an exception.

#include <stdexcept>

double& Vector::operator[](int index)
{
  if(index < 0 || index >= size) 
     throw out_of_range("Vector::operator[]"); // exception thrown
  return arr[index];
}

You can actually throw any object, even int, char and char *. If you include stdexcept we have access to many predefined exceptions like out_of_range. The exceptions you use inherit from either logic_error or runtime_error. You either use these or extend these classes to construct your own.

When you throw exceptions you usually use the try-catch structure. With one try block you can have several catch blocks.

try {
   // protected code
} catch( ExceptionName e1 ) {
   // catch block
} catch( ExceptionName e2 ) {
   // catch block
}catch( ExceptionName eN ) {
   // catch block
}

When you use a catch block a good practice is to catch a general exception so that you cover other cases aswell, maybe an exception thrown from a library function.

#include <iostream>
using namespace std;

int main( )
{
   try 
   {
      // do something
      // if that something was not logic =>
      throw logic_error( "logic error" );
   }
   catch ( exception &e ) // general exception
   {
      cerr << "Caught: " << e.what( ) << endl;
      cerr << "Type: " << typeid( e ).name( ) << endl;
   };
}

Output:

Caught: logic error
Type: class std::logic_error

Where to catch an exception should be given some consideration. Sometimes you just might want to throw from the function and catch at the top of the callstack.

class Student {
public:
  Student( char *namein, char *coursein) : name(0), course(0) 
  {
    try {
        name = new char[strlen(namein)+1]; strcpy(namn, namein);
        course = new char[strlen(coursein)+1]; strcpy(course, coursein);
    } catch (bad_alloc &ba) {
        delete[] name; // if not successful
        throw;         // and throw up the callstack...
    }
  }
private:
  char *name;
  char *course;
};

int main()
{
  try {
      Student student("Patrik", "OOP with C++");
  } catch (bad_alloc &ba) { // final destination of exception
      cout << "ERROR " << endl;
  }
}

Here is an example of how to make usage of a homegrown exception.

#include <iostream>
#include <exception>
using namespace std;

class myexception: public exception
{
  virtual const char* what() const throw()
  {
    return "My exception happened";
  }
} myex;

int main () {
  try {
    throw myex;
  } catch (exception& e) { // we catch anything that passes
    cout << e.what() << '\n';
  }
  return 0;
}