Designing Algorithms that Require Scratch Space

Question

The C++ Standard Library separates data structures from algorithms, such as with std::sort:

template< class RandomAccessIterator >
void sort( RandomAccessIterator first, RandomAccessIterator last );

I would like to maintain separation of algorithms and data structures when the algorithms require intermediate scratch space.

With this goal in mind I wanted to implement an image algorithm that requires intermediate scratch space between the input and output image. One could allocate the necessary scratch space in the function call, however due to the size and frequency of these calls with images of identical size it would severely degrade performance. This makes it much more difficult to separate the data structure from the algorithm.

One possible way to achieve this is as follows:

// Algorithm function
template<typename InputImageView, typename OutputImageView, typename ScratchView>
void algorithm(
  InputImageView inputImageView, 
  OutputImageView outputImageView, 
  ScratchView scratchView
);

// Algorithm class with scratch space
template<typename DataStructure>
class Algorithm {
public:
  template<typename InputImageView,typename OutputImageView>
  void operator()(
  InputImageView inputImageView, 
  OutputImageView outputImageView
  ){
    m_scratch.resize(inputImageView.size());
    algorithm(inputImageView,outputImageView,makeView(m_scratch));
  }

private:
  DataStructure m_scratch;
}

Is the above an effective algorithm + scratch space design to follow, or is there a better way?

Side note: I am using the boost::gil library

Answer 1

I think in such a case, I'd have the algorithm allow you to pass (a reference or pointer to) a structure for the scratch space, and give that argument a default value. This way the user can call the function without passing a structure when/if the extra time to allocate the structure isn't a problem, but can pass one if (for example) building a processing pipeline that can benefit from reusing the same space repeatedly.

Answer 2

If you use a function object, you can carry whatever state you need.

Two useful algorithms are transform and accumulate.

transform can take a function object to perform the transformation on each object in the sequence:

class TransformerWithScratchSpace {
public:
    Target operator()(const Source& source);
};

vector<Source> sources;
vector<Target> targets;
targets.reserve(sources.size());

transform(sources.begin(), sources.end(),
          back_inserter<Target>(targets),
          TransformerWithScratchSpace());

accumulate can take a function object which accumulates all the objects into itself. The result is the accumulated object. The accumulator itself doesn't have to produce anything.

class Accumulator {
public:
    Accumulator& operator+()(const Source& source);
};

vector<Source> sources;

Accumulator accumulated = accumulate(sources.begin(), sources.end(),
                                     Accumulator());