ACCU Home page ACCU Conference Page
Search Contact us ACCU at Flickr ACCU at GitHib ACCU at Google+ ACCU at Facebook ACCU at Linked-in ACCU at Twitter Skip Navigation

pinLetters to the Editor(s)

Overload Journal #59 - Feb 2004 + Programming Topics   Author: Frank Antonsen

Regarding "A more flexible container" by Rich Sposato, Overload 58 (December 2003)

Although it is certainly interesting to consider alternative implementations of standard containers, I think Rich has chosen the wrong solution to the problem.

What he want to do is to extract all members of a collection satisfying a given condition. In his driving example, he has a set of Employee records, and he wants to extract those elements of the container that matches a given surname, say. If one only ever wants to deal with sets of such records, Rich's solution is probably the best one can do. But if one later wants, as Rich does in the article, to perform a similar operation on another type of container, the limitations of his approach become clear.

Instead of modifying each container by defining a new one built upon the standard containers, it is much better to have a generic algorithm working with any container (standard or not).

So it seems to me, a better, or at least more generic, solution would be to define an algorithm working roughly like this:

result = filter(collection,comparator);
  // filter elements of a container

where result and collection are containers of the same kind and comparator is a function, or functor, taking an element and returning a Boolean value.

A template version would look something like this (in pseudo- C++ to show the structure more clearly)

template<class Coll, class Comp>
Coll filter(Coll coll, Comp cmp) {
  Coll res(0); // create empty result set
  for (iterator it=coll.begin();
       it != coll.end();
       ++it)
    if (cmp(it))
      res.insert(it);
  return res;
}

This will then work for any container having a standard iterator interface and an insert() member function as well as for any cmp having an operator() defined taking a container element of the right type as argument and returning something which can be interpreted as a Boolean.

All the extra work now goes into defining the comparator function or functor, which is probably precisely where the effort should be concentrated anyway.

While this solution is simpler and more generic than Rich's, it is not purely object oriented. In fact, it wouldn't be possible to carry it over directly to Java or C#. Instead, it is an example of what one might call a "functional programming design pattern". The filter algorithm above is a C++ analogue of a so-called "higher order function" in functional programming (FP), i.e. a function taking another function as argument. Actually, very often OOP design patterns can be translated into FP higher order functions.

The particular higher order function used here, filter, exists in all major FP languages (Lisp, Haskell, ML) and in some other multi-paradigm ones (Perl, Python).

What this illustrates is the idea that, however powerful a concept, OOP just isn't the right solution in all circumstances. Luckily, C++ is a multi-paradigm language, supporting not just OOP and C-style procedural programming, but also FP-style programming as above. That being said, C++ has a very, very strong support for efficient OOP code, allowing most compilers to make very efficient assembler code. In contrast, the FP-aspects, although introduced with the STL, have received less attention, and not all compilers will generate efficient code in these cases. This, however, may be compensated by the optimisations made for the standard containers.

On the other hand, such an FP-like solution is easier to maintain, the code is concentrated in one place instead of being duplicated in all containers. Moreover, the FP-like solution above is more generic. Suppose, for instance, that you defined an iterator interface for files, with the "elements" being the individual lines. The filter algorithm can then be turned into a utility like UNIX's grep, extracting lines meeting a specific criterion.

Whether to put something into a member function or not is a difficult question to answer in general. All sorts of issues may be involved: design principles, maintainability, and efficiency etc. My own pragmatic rule of thumb is, if the same code is copied with very little change in many classes, it is probably worth considering putting it outside, either in a special class or as an algorithm.

Overload Journal #59 - Feb 2004 + Programming Topics