TITLE: algorithm objects

(Source: comp.lang.c++.moderated, 31 Jan 2001)

KUEHL: Dietmar Kuehl

: I'm apparently about the only person around in favour of
: algorithm objects which basically turn the algorithms kind
: of inside-out: Instead of having the controlling loop being
: a part of the algorithm itself, the algorithms basically
: provides the functionality to execute a single step of the
: algorithm before returing the control to the
: user. Premature termination, arbitrary extra operations,
: pseudo-parallel executation, algorithm persistance,
: ... become just trivial.  --

OOSTRUM: Rene van Oostrum (rene+gnus@cs.uu.nl)

> Could you please elide on this?

KUEHL: "Dietmar Kuehl" <kuehl@ramsen.informatik.uni-konstanz.de>
 
 The basic idea is this: Typical non-trivial algorithms are likely to be
 extended in some form when they are supposed to be used. Since
 non-trivial examples, are, well, non-trivial, I will use a trivial
 example: Iterating over a sequence. This is a pretty basic algorithm
 which by itself does nothing really useful. An application of this
 algorithms will add extra operations to this algorithm, eg. call a
 function for each element. This is what the 'std::for_each()' algorithm
 does:

   template <typename InIt, typename Func>
   Func for_each(InIt beg, InIt end, Func func)
   {
     for (; beg != end; ++beg)
       func(beg);
     return func;
   }

 Although this is a pretty trival example, some questions immediately
 arise on its design:
 - A functor is a reasonable choice to call inside this function but
   can't there be some variations on this theme, eg. a function taking
   more than one argument? Some of these variations can be handled by
   nifty constructions of functors but I'm not sure whether this applies
   to all variations.
 - Why isn't the functor passed around by reference? The approach of
   passing the functor by value actually causes certain problems, mostly
   when the functor holds resources.
 - How can this function be terminated prematurely, if it can at all?

 Things become even trickier if the algorithm is more complex and eg.
 has multiple states where probably different functions are to be
 called. Also, especially for long running algorithms it may become
 desirable to intercept the algorithm to do other work, be it a progress
 bar, executation of more or less unrelated operations (threads may or
 may not be an alternative: there are certain costs associated with
 threds which are undesirable for long running algorithms...).

 An alternative is the use of an object which functions like an iterator
 over the algorithm's states: It makes a more or less atomic operation
 and then hands the control to the user. The interface of the object
 gives the user the necessary access to the algorithm's internal state.
 Here is a simple example:

   template <typename InIt>
   struct for_eacher
   {
     for_eacher(InIt b, InIt e): beg(b), end(e) {}

     operator void const*() const { return beg != end? this: 0; }
     for_eacher& operator++() { ++beg; return *this; }
     InIt& current() { return beg; }

   private:
     InIt beg, end;
   };

 Instead of executing the whole algorithm by itself, this class just
 steps through the algorithm. A use could eg. look like this:

   std::ifstream in("file.txt");
   std::istream_iterator beg(in), end;
   std::vector<int> vec(beg, end);

   for (for_eacher<std::vector<int> >::iterator> algo(vec.begin(),
vec.end());
        algo && *algo.current() < 17; ++algo)
     std::cout << *algo.current() << "\n";

 This small example demonstrates two points:

 - There is no need to write a functor object but instead the code
   looks pretty normal and is local to the actual use. With a functor
   you have to put the implementation often somewhere different than
   where the algorithm is used (well, with one of the lambda libraries
   at least simple functors can be defined right where they are used).
 - It is easy to terminate the algorithm prematurely: It is under the
   control of the algorithm user to just discontinue use of the
   algorithm object.

 For trivial algorithms this is indeed trivial and for "typical" uses
 it is easy to create a functional wrapper using the algorithm object
 inside. For non-trivial algorithms things are unfortunately not only
 bright: The algorithms have states and the user has to react on the
 algorithm's current state. As a result, the algorithm's implementation
 often use Duff's Device to continue executation at their current
 state and another switch is in the user code to determine which
 additional operation is to be performed. I can imagine that a good
 optimizing compiler can effectively reorder the code fragments to
 effectively remove both switches but I haven't experimented with the
 details of this stuff enough to get identical performance :-(


_______________________________________________
cpptips mailing list
http://cpptips.hyperformix.com