Re: [boost] function based associative generator

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-23 16:02:02

Dean Michael Berris wrote:
> Hi Everyone,
> 
> I've recently been playing around with a relatively simple idea:
> creating a generic associative generator.
> 
> For some background, here's a simple problem (which is quite common in
> mathematics):
> 
> I want to be able to pull out the nth fibonacci number in the
> fibonacci sequence. To do this, the traditional implementation in C++
> would be to create a function that yields the nth fibonacci number.
> This seems fine, because as C++ programmers we would be used to the
> notion of using functions. However, the traditional notion of a
> sequence in mathematics is a collection of values that can be indexed
> by a subscript. Consider:
> 
> struct fibonacci {
>   int operator () (int n) const {
>     // ...
>   };
> };
> 
> boost::generator<int, int> const & fib = boost::generator<int,
> int>(fibonacci());
> std::cout << fib[1] << std::endl; // prints 1st fibonacci number
> std::cout << fib[2] << std::endl; // prints 2nd fibonacci number
> ...
> 
> Now consider that you want to deal with the generator using an STL algorithm:
> 
> std::copy(fib.begin(), fib.end(), ostream_iterator<int>(std::cout, "
> ")); // prints the infinite sequence

If you're using Binet's formula, that's a pretty inefficient way to
compute all those Fibs, isn't it?  Or does your generator cache nearby Fibs?

> The iterator implementation requires that the InputType (in this case,
> the second 'int' template parameter to the generator) be default
> constructable and has a defined prefix and/or postfix increment
> operator. The iterator models an InputIterator.
> 
> Given this, I've attached the implementation which I'm opening up for
> comments. 

Interesting; a const_iterator that can't be incremented ;-)

> If there is interest in this utility, I'm willing to write
> documentation and submit it for a formal review.
> 
> The basic idea for this utility is to map a non-void unary function to
> a generator interface that provides an associative index operator
> (operator[]) which passes the sole argument as the argument to the
> wrapped function. This utility requires only the Boost.Function
> library, and has been tested with MSVC 2008 Express Edition.

Is this basically

  make_transform_iterator( make_counting_iterator( start ), f )

or is there more to it?

-- 
Dave Abrahams
BoostPro Computing
http://www.boostpro.com