Iterators for D

Walter Bright newshound at digitalmars.com
Mon Nov 6 15:33:31 PST 2006


Kirk McDonald wrote:
> Walter Bright wrote:
>> Overloading * doesn't work with D. But, instead:
> What are the arguments against that, again?

Because D has many cases of implicit dereferencing, I thought it would 
cause more trouble than it's worth.

> I do not recall, and it's 
> worth at least reviewing why we don't have opDeref and opDerefAssign.
> 
> As you know, Walter, a major benefit of C++-style iterators is that they 
> are semantically as close as possible to pointers. Would [] be changed 
> to dereference pointers?

You've always been able to:
	int* p;
	p[1] = ...

> I sure hope not. If we go this route, I would 
> suggest adding these unary-* overloads.
> 
>> Overload opIndex for rvalue access
>> Overload opIndexAssign for lvalue access
>>
> 
> I think you mean opSlice and opSliceAssign.

No, I meant Index.

>> Overloading opIndex also will work for random access
>>
>> foreach loops will not be able to have a 'key' parameter.
> 
> So, I would assume these iterators would work something like this:
> 
> If a class provides .begin and .end, and these both return the same 
> type, and that type provides the requisite iterator methods, it is 
> foreach-able.

Yes, though they will return a value, not a type.

> If a class provides .begin, .end, and opApply, one of the two iteration 
> methods has to take precedence. I would hope it's opApply.

I was leaning towards the other way around.

> For a type T, its associated iterator type should be available via 
> T.iterator. This has to be standard.

It's not needed, as typeof(T.begin) will do it.

> An iterable type T MUST provide these methods:
> I begin()
> I end()

Yes.

> An iterator type I MUST provide the following overloads:
> E opSlice()

No. opIndex()

> I opPostInc()

Probably opAddAssign()

> E is the type of an element in the collection.


> These are enough to describe a read-only forward iterator, which is 
> adequate for foreach. In other words, given a type T that meets the 
> requirements outlined above, the following is adequate to iterate 
> through it:
> 
> foreach(e; t) {
>     // ...
> }
> 
> 'e' would be of type E.

Yes.

> We run into a curious problem involving pre-increment, which uses 
> opAddAssign. Classes for which random-access is problematic should not 
> be required to provide this, which is essentially a random-access 
> method. There are two options here:
> 
> 1) Only require that iterators support opPostInc. (This further removes 
> them from actual pointers.)
> 
> 2) Introduce a convention whereby a non-random-access iterator throws an 
> exception if any value other than 1 is passed to its opAddAssign overload.

I could go either way with that.

> Extending these rules for bidirectional iterators and random-access 
> iterators, as well as read-write iterators, is left as an exercise to 
> the reader. (And not a very difficult one.)
> 
> All of these strange edge-cases and differences between pointers and 
> possible iterator types convince me that C++-STYLE ITERATORS ARE NOT FOR 
> D. D, unlike C++, does not supply enough operator overloads for their 
> semantics to be identical to those of pointers, which was the whole 
> point of C++-style iterators in the first place.

I think it does provide enough, in fact, it will be less wacky than in 
C++ (look at the wretched iterator/const_iterator dichotomy). It'll work 
with core arrays, and will not need those typedefs.


> Instead, we should look to other languages for inspiration. I suggest 
> Java and Python, whose iterator semantics are similar. Other posters 
> have already made suggestions on this front. I would only suggest the 
> "opIter" method for getting an iterator, and that the iterator class 
> itself be available via T.iterator (whether it is a nested class or an 
> alias shouldn't matter). Classes can provide methods for returning 
> alternate iterators, as well. (A class providing opIter should be 
> iterated over as easily as an iterator itself.)





More information about the Digitalmars-d mailing list