Boost logo

Boost :

From: David Abrahams (dave_at_[hidden])
Date: 2008-06-26 09:34:17

Dean Michael Berris wrote:
> On Tue, Jun 24, 2008 at 2:22 PM, David Abrahams <dave_at_[hidden]> wrote:
>> Dean Michael Berris wrote:
>>> On Tue, Jun 24, 2008 at 4:02 AM, David Abrahams <dave_at_[hidden]> 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 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.


Dave Abrahams
BoostPro Computing

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