Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 2:22 PM, David Abrahams <dave@boostpro.com> wrote:
Dean Michael Berris wrote:
On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave@boostpro.com> wrote:
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.
The inefficiency is actually inherent in the underlying function implementation, and not directly as an effect of using the generator to wrap the function.
I know; I was just trying to find out if solving that problem was part of your domain.
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.
Accessing the generator wouldn't be inefficient whether you access it using operator[] or sequentially. Unless you're thinking that somehow the generator will cache results of previously accessed data and encapsulate an appropriately random-accessible container (like an std::vector) to mitigate the recomputation of already previously accessed data; would this be something that would be considered a value-add for a general-purpose utility?
No, I was just thinking that operator++ would see if there was a cache of the previous two numbers and add them together.
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.
Almost does it, but not necessarily. Constructing an instance of the transform iterator would require the instantiation of the counting_iterator as well.
So?
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.
I think it's more semantics than anything -- something that looks and acts like a container can't just be an iterator.
You can always build an iterator_range.
I guess the notion of an iterator is directly tied somehow with collections and containers, but seeing just an iterator somehow doesn't give the same semantics -- at least as how I see it.
OK -- Dave Abrahams BoostPro Computing http://www.boostpro.com