Re: [Boost-users] Overloading boost::for_each()

Subject: Re: [Boost-users] Overloading boost::for_each()
From: Mathias Gaunard (mathias.gaunard_at_[hidden])
Date: 2010-08-29 19:43:57

On 29/08/2010 17:53, Dave Abrahams wrote:
> On Sun, Aug 29, 2010 at 4:34 AM, Mathias Gaunard
> <mathias.gaunard_at_[hidden]>  wrote:
>
>> So, at the end of this long message, what do I propose to solve the original
>> problem?
>>
>> Have your container provide a step-generator. You can then implement your
>> iterator on top of it, or not, your choice (but I'd recommend using it to
>> avoid unnecessary code duplication and maintenance).
>
> I don't understand your suggestion .  To make your proposal
> understandable, could you please illustrate, in code, what a
> step-generator would look like for std::deque, and how it could be
> used?

I'm not really familiar with the implementation of std::deque, so I'll 
just assume it's a vector of statically-sized arrays. (I'm also assuming 
each statically-sized array is full for the sake of simplicity, but in 
truth the ones on both ends wouldn't be)

I don't know yet what a generator that just runs a step should look 
like, here's a first try:

template<typename T>
struct deque_step_generator
{
     typedef T output_type;
     static const size_t max_output = whatever;

     deque_step_generator(deque& deq_) : deq(deq_), it(deq.begin()) {}

     template<typename Out>
     Out operator()(Out out)
     {
        return copy(*it++, out);
     }

     bool at_end()
     {
        return it == deq.end();
     }

private:
     typedef vector< array<T, max_output> > deque;
     deque &deq;

     typename deque::const_iterator it;
};

One solution for the caller to detect it has reached the end is to have 
an at_end member function. Another solution could be to generate nothing 
at the end -- in a similar fashion to the 'read' POSIX function. What's 
the best design remains to be evaluated.

It might also be needed to have a way to integrate right-to-left 
generation to allow for bidirectional ranges.

Of course, for certain data structures, providing a step-generator, as I 
call it, can still be too complicated, and they could only have a 
'global' generator, which, in the case or our deque, would be:

template<typename T>
struct deque_generator
{
     typedef T output_type;

     deque_generator(deque& deq_) : deq(deq_) {}

     template<typename Out>
     Out operator()(Out out)
     {
        for(typename deque::const_iterator it = deq.begin(); it != 
deq.end(); ++it)
             out = copy(*it++, out);
        return out;
     }

private:
     typedef vector< array<T, whatever> > deque;
     deque &deq;
};

In the case of a global generator, implementing algorithms such as 
std::accumulate should be basically the same thing as the 
string_appender example here:
<http://www.boost.org/doc/libs/1_44_0/libs/iterator/doc/function_output_iterator.html>
In the case of the step one, it's the same except you need to do it in a 
loop.

In order to be converted to a flat iterable range, a global generator 
would require a coroutine, while a step one could be converted using 
either the coroutine or the buffered technique.

Writing the code that does that generic conversion could be a bit harder 
to write than that, so I'm not really up to the task at this late hour 
(to the point where I even cheated a fair bit on the deque generators...).