Boost logo

Boost :

From: Dean Michael Berris (mikhailberis_at_[hidden])
Date: 2008-06-24 00:53:30

On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave_at_[hidden]> wrote:
> 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?

Actually, the function object can be as stateful or state-less as you
want. There's an iterative way of computing the nth fibonacci number,
but that's really beside the point here. ;-)

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

Eep. I didn't have a test for that. Let me see what I can do about that. :D

>> 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?

The make_*_iterator family works fine, but the problem becomes one of
semantics/readability. If you just wanted iterators, the above would
be sufficient. For 'prettier' syntax that models the sequence
generators that other programming languages have (think Haskell's list
comprehensions/construction) making something look like a list may be

The idea really is to abstract the function that generates the list
from the list it generates (lazily?) itself. Instead of doing:


Something that looks like


May look more semantically correct. The generator can then abstract
certain details from the 'accessing site' as to things like whether
it's a container that actually contains things or a function that
returns values. Consider for example an adjacency matrix where the
adjacent vertex lists were distributed accross network resources which
you can access by wrapping an accessor client in a generator<>, and
access through the index operator []... Maybe that would make the code
more readable doing:


Instead of maybe something like:


Of course, others may have other ideas as to what other things may be
done with this but the basic idea is the same -- make your function
look like a sequence generator and use the 'sequence' like a real
container. :-)


Dean Michael C. Berris
Software Engineer, Friendster, Inc.

Boost list run by bdawes at, gregod at, cpdaniel at, john at