Boost logo

Boost :

From: Eric Ford (eford_at_[hidden])
Date: 2001-08-04 18:33:00


--- In boost_at_y..., "David Abrahams" <david.abrahams_at_r...> wrote:
> > I created a directory "recurrence relation iterator" which has my
> > first crack at pseudo iterator and container classes for
> > (mathematical, not stl) sequences generated on the fly using a
> > recurrence relation (e.g. infinite sequences). If people are still
> > interested, I'd be interested in getting comments.
>
> Doesn't a range of STL input iterators model a mathematical sequence?
> These don't have to be stored in memory all at once. In fact, that's
also
> true of bidirectional and random-access iterators, since they are
allowed to
> cache their lvalue internally. Do we need a new concept?

For the iterators, it's not so bad. I've merely implemented something
that attempts to be close to a STL bidirectional input iterator. I
have not implemented all the typedefs (e.g. itterator_traits).

One isssue is I'm not sure how the distance_type should be handeled.
I think there should be a way to do this without storing the index of
the element, but for relations involving floating point types, it's
not obvious. I'm not even sure if there's a real need for
distance_type for these sequences. Yet, even a forward input STL
itterator is suppose to define this type. Maybe someone more familair
with the standard could comment on this.

Another issue is that for bidirectional itterators, *j=*i; ++i; --i;
return (*i==*j); is supposed to be true, right? Given floating point
arithmetic, that may not be the case.

A random_access_iterator would be even more complicated. If you
access an element near the current one, a recurrence relation would
probably be used. But if you access an element quite far from the
current one, you might you an asympotic expression. Therefore the
same element could have different values depending on the previous
operations and their ordering. That in turn could make comparisons
difficult. If you test for equality between the 100th term in a
sequence generated by itterating one at a time and the 100th term
generated by using it as an index, do you want to get true, even if
the floating point values are different?

Anyway, my recurrence_relation_iterator class seems like it is quite
close to the STL bidirectional input iterator concept, although there
may be some technicalities to work out. It would be nice if no new
concept were necessary, but it might be decided a new concept was
warranted. My class's purpose is to make it easier to implement such
itterators. I think the examples demonstrate that it does. I'm
hoping this will be useful for things like series expansions for
evaluating (mathematical) functions.

For the infinite_sequence, it's more complicated. It's certainly not
an stl sequence. It can't insert x^3.5 or erase x^5. It doesn't
always make sense to specify the size to the constructor.

Even an stl container doesn't really work. Say you have a sequence 1,
x, x^2, ..., x^n... . What's the end, size, max_size? When is it
empty? Even the begin may not make that much sense, if it goes from n
= -\infty to \infty. For a forward container, how do you compare such
sequences? Which element do you compare first?

So, yes, I beleive the container for a sequence generated via a
recurrence relation will need a new concept. My infinite_sequence
class does not attempt to be a real stl container. It is presently
only a straw man for discussing the issues. I beleive it will
probably need to be broken into several clsases (e.g. math_sequence,
terminating_math_sequence, infinite_math_sequence,
semiinfinite_math_sequence). Eventaully, people will probably want
both caching and non-caching versions, but I think this should wait.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk