Boost logo

Boost Users :

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();

     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;

     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:
In the case of the step one, it's the same except you need to do it in a

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...).

Boost-users list run by williamkempf at, kalb at, bjorn.karlsson at, gregod at, wekempf at