Thoughts about 2009
3. Software Development Day in Wien

Separation of Algorithms and Containers (Collections)

The C++ Standard Template Library (STL) separates algorithms from containers. C++ algorithms are defined within the header file can be used with containers depending on the iterator that is needed by the algorithm and the iterator supported by the container. search, search_n, reverse, rotate, copy, count, count_if, find, find_first_of, for_each, max, min, merge are just a few of the algorithms. These are global functions that accept iterators from container classes to iterate all elements.

With .NET 3.5 algorithms are separated from collections as well. Static methods such as Count, Max, Min, First, Skip… are implemented by the Enumerable class. These methods are all extension methods based on the IEnumerable interface and thus can be used with every collection.

Let’s compare the implementation of C++ accumulate with .NET Aggregate. Both have several overloads, but I just want to compare just one. The others are very similar.

C++ aggregate is a template function with four parameters. The first two parameters mark the begin and end of the iteration. This algorithm requires an Input Iterator that implements the operators !=, ++, and *. The third parameter is used as initialization of the aggregation, and the last parameter accepts a function object that has two parameters (BinaryOperation). With a for loop every element that is enumerated is accessed, the binary operation invoked, and the result of the operation accumulated.

Type accumulate(InputIterator _First, InputIterator _Last, Type _Val, BinaryOperation _Binary_op) 
   for (; _First != _Last; ++_First)
      _Val = _Binary_op(_Val, *_First);
   return (_Val);
Using the accumulate method a binary function can be defined that is invoked by accumulate, e.g. a simple multiplier.
int action(int x, int y)
   return x * y;

Calling the accumulate function requires the begin and end for the iteration that is returned from the begin and end methods of the vector class. For multiplying every integer in a vector, the initial value is set to 1, and the address of the action function is passed: int result = accumulate(v1.begin(), v1.end(), 1, action); The .NET version of the C++ accumulate does not differ a lot. Instead of having a begin and end of an iterator, here the IEnumerable interface is used. With C++ iterators just a naming convention is used to give the requirements of the iterator. C++ differentiates input, output, forward, bidirectional, and random access iterators that define what operators must be implemented. With .NET it’s clearly defined what methods must be implemented by the collection by the definition of the IEnumerable interface. The initial value that is passed is similar to the C++ implementation. The last parameter defines the signature of the method that is invoked by Aggregate: a method with two input parameters and a result. Instead of a for loop, .NET makes use of the foreach loop that is converted by the compiler to use the methods of the IEnumerable interface.
public static TAccumulate Aggregate(this IEnumerable source,  
   TAccumulate seed, Func func)
   TAccumulate local = seed;
   foreach (TSource local2 in source)
      local = func(local, local2);
   return local;

Because the Aggregate method is an extension method, it can be invoked like a member of the collection class to aggregate all values from the collection. The functionality that is invoked with every instance can be implemented by using a Lambda expression.
int result = coll.Aggregate(1, (x, y) => x * y);

C++ and .NET have very similar implementations to separate the algorithms from containers. Lambda expressions are not yet available with C++, but will be with a future version C++0x. Algorithms that are available in one place (e.g. C++) can easily be implemented in the other (e.g. .NET).



Feed You can follow this conversation by subscribing to the comment feed for this post.

The comments to this entry are closed.