foreach vs. iterators
Sean Kelly
sean at f4.ca
Sat Nov 4 16:16:34 PST 2006
Oskar Linde wrote:
> Sean Kelly wrote:
>
>> From this it seems clear that foreach is not sufficiently adaptable
>> to meet the needs of all sequential algorithms and opIndex is not a
>> reasonable substitute for all cases where foreach may not be used.
>> What alternatives do we have? So far, iterator variants are all I've
>> been able to come up with.
>
> I agree, and I have been saying this countless times. :)
>
> Why don't we come up with a standard iterator concept for D?
> For a forward iterator, C++ has:
>
> *i
> i++ / ++i
> i != end
>
> In the post "Iterators (Was: Re: Lazy eval -- an example issue)" in
> digitalmars.D (
> news://news.digitalmars.com:119/ecmvec$ksl$1@digitaldaemon.com ) I
> suggested a simple java-style variant:
>
> *i.next()
> i.hasNext()
I think a Java style iterator is the way to go for D. Personally, I
basically never find a need for bidirectional iterators, and I only use
random access iterators with vectors, which correspond to D's built-in
dynamic arrays. Also, a single iterator that knows when it's reached
the end of the sequence better suits being used with foreach than the
pointer-style iterators of C++. About the only thing I don't like about
Java iterators is how they work ;-) Only being able to access the
referenced data by calling next() is a bit irritating. That said, it
does eliminate the need for iterators to potentially cache the current
value when iterating across sequences that don't inherently store data,
such as an input stream. Still, I think it's useful to have in an
iterator, so perhaps something roughly like this:
interface Iterator(T)
{
T val();
T next();
bool hasNext();
}
interface WriteIterator(T) : Iterator(T)
{
T val( T n );
}
> A generic opApply could then be implemented as:
>
> template opApplyMixin() {
> int opApply(int delegate(inout ValueType v) dg) {
> ValueType *t;
> while(hasNext()) {
> t = next();
> if (auto status = dg(*t))
> return status;
> }
> return 0;
> }
> }
>
> And a simple array iterator wrapper (Could of course be more efficiently
> implemented):
>
> struct ArrayForwardIterator(T) {
> T[] arr;
> alias T ValueType;
>
> T* next() { arr = arr[1..$]; return arr.ptr-1; }
> bool hasNext() { return arr.length > 0; }
> mixin opApplyMixin;
> }
Looks good.
> If pointers should be avoided, and since D doesn't have an opDeref, but
> has lhs/rhs overloads for indexing, another iterator variant could be to
> use
>
> i[]
> i[]=
>
> for rhs, and lhs iterator dereferencing.
I prefer the 'val' approach. It seems a bit more meaningful than
something with operators.
> i++ / ++i could be used instead of .next() if it is any clearer, and so
> on...
I'm not sure how I feel about using structs for iterators (instead of
classes). With classes, we can retain some semblance of control over
copy semantics, but we can't with structs. And I'm not entirely sure I
think we should be able to copy iterators at will--consider Walter's
case of an iterator for a traditional binary tree, for example. Also,
using structs forces user code to either be hard-coded to work with a
specific iterator type or to use templates. And I'll admit I do sort of
like the idea of:
void myFunction( Iterator!(int) x ) {}
being possible.
> It doesn't really matter what convention we pick. For better rather than
> worse, D doesn't allow us to do as C++ does, make iterators
> interchangeable with pointers. We may as well pick anything we like as
> long as the compiler is able to make reasonable efficient code out of it.
Agreed.
> As I said in the above referenced post, I have been toying with making a
> template iterator/array algorithm library. I've got a quite substantial
> proof of concept working, but have not had much time lately. I do love
> discussions about this though. :)
I've been focusing on arrays thus far, but am getting to the point where
I'd like to extend some algorithms to work for user-defined containers
as well. And that obviously requires a decent convention for how
iterators should be implemented. Also, I'll admit that I really enjoy
algorithm talk as well :-)
Sean
More information about the Digitalmars-d-announce
mailing list