Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> 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,
Well of course; that's the easy way to do it... but it makes random access with fib[n] very inefficient.
but that's really beside the point here. ;-)
Well, _my_ point was to find out whether your proposal was going to figure out how to handle both random access and sequential iteration efficiently. Sounds like it isn't.
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 important.
The idea really is to abstract the function that generates the list from the list it generates (lazily?) itself. Instead of doing:
fib(n);
Something that looks like
fib[n];
May look more semantically correct.
But... you can already use operator[] on a random access iterator. So if you're not going to explicitly solve the problem of efficient sequential and random-access traversals, boost::transform_iterator< boost::counting_iterator<T>, boost::function<T(T)>
already does what you want, I think.
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:
adjacency_matrix[n];
Instead of maybe something like:
get_adjacent_vertices(n);
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. :-)
So far this doesn't seem to have much of substance that isn't already in the iterators library, but I could be missing something. -- Dave Abrahams BoostPro Computing http://www.boostpro.com