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.
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?
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. template <class ResultType, class InputType> struct generator { typedef transform_iterator< function<ResultType(InputType)>, counting_iterator<InputType>
iterator; typedef iterator const const_iterator;
iterator begin() { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; const_iterator begin() const { return make_transform_iterator( counting_iterator<InputType>(), _function ); }; iterator end() { return iterator(); }; const_iterator end() const { return const_iterator(); }; generator() : _function() { }; generator(function<ResultType(InputType)> const & f) : _function(f) { }; ResultType operator[](InputType i) const { return _function(i); }; private: mutable function<ResultType(InputType)> _function; }; The generator now adapts the function provided into a 'pseudo-container' of sorts which provides you with a means of indexing elements in the 'container' using the index operator. However, I suppose that it's a matter of convenience really whether or not to use a transform_iterator instead of the provided utility above. Looking at the counting_iterator documentation, I suppose the generator wrapper provides non-void unary functions an index operator and begin()+end() iterators to make it look like an infinite* lazily generated random-access container. * - well of course, the bounds would be dependent on the valid range of values of InputType.
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.
I think it's more semantics than anything -- something that looks and acts like a container can't just be an iterator. 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. -- Dean Michael C. Berris Software Engineer, Friendster, Inc.