www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Are iterators and ranges going to co-exist?

reply Peter Alexander <peter.alexander.au gmail.com> writes:
I've been following the D programming language for quite some time now, 
and only recently decided to dive in and start using it. My first 
impressions are that it is a very nice language (despite the library 
bugs), but one thing in particular that confused me was the lack of 
iterators, and their near complete replacement by ranges.

I did notice that there is an std.iterator library, which is said to be 
"growing" in the documentation.

What is the plan for this library? Will the std.algorithm start to use a 
mixture of iterators and ranges (as it should, in my opinion)?

In his article, "On Iteration" 
(http://www.informit.com/articles/article.aspx?p=1407357&seqNum=12) 
Andrei admitted that ranges had weaknesses when compared to iterators, 
so I would be very disappointed if iterators weren't to make it into the 
standard library.

In the thread on improving std.algorithm.find, there were mentions of 
making find (or some findFirst) that returned a single element. Would 
this be an iterator, or a single value range?
Jul 19 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/19/2010 03:37 PM, Peter Alexander wrote:
 I've been following the D programming language for quite some time now,
 and only recently decided to dive in and start using it. My first
 impressions are that it is a very nice language (despite the library
 bugs), but one thing in particular that confused me was the lack of
 iterators, and their near complete replacement by ranges.

 I did notice that there is an std.iterator library, which is said to be
 "growing" in the documentation.

The existence of std.iterator is a mistake on my part.
 What is the plan for this library? Will the std.algorithm start to use a
 mixture of iterators and ranges (as it should, in my opinion)?

The plan is to use ranges everywhere. Sorry to disappoint. If you can find solid arguments for introducing iterators, of course it would be great if you discussed them in this group.
 In his article, "On Iteration"
 (http://www.informit.com/articles/article.aspx?p=1407357&seqNum=12)
 Andrei admitted that ranges had weaknesses when compared to iterators,
 so I would be very disappointed if iterators weren't to make it into the
 standard library.

 In the thread on improving std.algorithm.find, there were mentions of
 making find (or some findFirst) that returned a single element. Would
 this be an iterator, or a single value range?

The result of find() is (and is planned to be after the overhaul of find) the balance of the searched range positioned on the found element. I don't think a singleton range would hold an advantage over that. Andrei
Jul 19 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:
 The plan is to use ranges everywhere. Sorry to disappoint. If you can
 find solid arguments for introducing iterators, of course it would be
 great if you discussed them in this group.

Well, you mentioned a few yourself in your article. - With ranges, you double the size of "iterators", which increases the memory usage of something like Boost.MultiIndex. - It makes certain algorithm interfaces awkward, such as rotate. I know you proposed to pass in two ranges, but to me that seems like an desperate attempt to force ranges into an interface that wants iterators. In the case of rotate, you've now burdened the programmer with assuring that the ranges are adjacent (which will probably involve introducing a local variable for maintenance/readability reasons), and you've also increased the amount of data you need to pass into the function by 33%, violating the "Don't pay for what you don't use" philosophy. - You're returning more data than is often wanted from some functions (such as the planned find). - It makes something like STL's std::list::splice *very* awkward. To do splice in constant time (as you should) the "range" is going to need to know about the previous element to its front so that it can update the linked list. What is the planned interface for this? My biggest objection to this is that it is essentially an awkward attempt at abstracting iterators. Ranges are brilliant, and maybe you could even call them a superset of iterators, but just like we have vectors despite having matrices, and points despite having lines, we still want iterators even though we have ranges. They are simply different things.
Jul 19 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/19/2010 04:24 PM, Peter Alexander wrote:
 On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:
 The plan is to use ranges everywhere. Sorry to disappoint. If you can
 find solid arguments for introducing iterators, of course it would be
 great if you discussed them in this group.

Well, you mentioned a few yourself in your article. - With ranges, you double the size of "iterators", which increases the memory usage of something like Boost.MultiIndex.

Agreed.
 - It makes certain algorithm interfaces awkward, such as rotate. I know
 you proposed to pass in two ranges, but to me that seems like an
 desperate attempt to force ranges into an interface that wants
 iterators. In the case of rotate, you've now burdened the programmer
 with assuring that the ranges are adjacent (which will probably involve
 introducing a local variable for maintenance/readability reasons), and
 you've also increased the amount of data you need to pass into the
 function by 33%, violating the "Don't pay for what you don't use"
 philosophy.

Phobos' bringToFront does not assume the ranges are adjacent. bringToFront is a strict generalization of STL's rotate.
 - You're returning more data than is often wanted from some functions
 (such as the planned find).

That's not necessarily a disadvantage, and I think in practice it's seldom an issue.
 - It makes something like STL's std::list::splice *very* awkward. To do
 splice in constant time (as you should) the "range" is going to need to
 know about the previous element to its front so that it can update the
 linked list. What is the planned interface for this?

splice is an internal method of the doubly-linked list. As such, it has knowledge and access to the list range's implementation and therefore has no problem wiring the pointers appropriately. (Note that splice does not work with just any ranges.)
 My biggest objection to this is that it is essentially an awkward
 attempt at abstracting iterators. Ranges are brilliant, and maybe you
 could even call them a superset of iterators, but just like we have
 vectors despite having matrices, and points despite having lines, we
 still want iterators even though we have ranges. They are simply
 different things.

I think the comparison is tenuous - I do agree that we have vectors vs. matrices etc., but that doesn't necessarily translate in convincing me that there should iterators vs. ranges. Pointers don't have a line-specific operation that may make them explode :o). Andrei
Jul 19 2010
next sibling parent Peter Alexander <peter.alexander.au gmail.com> writes:
On 19/07/10 11:09 PM, Andrei Alexandrescu wrote:
 Phobos' bringToFront does not assume the ranges are adjacent.
 bringToFront is a strict generalization of STL's rotate.

My point still stands: if you want to rotate then you need pass in adjacent ranges, which burdens the programmer and increases the size of the algorithm input. Generalizations are good, but specializations are just as important.
 - You're returning more data than is often wanted from some functions
 (such as the planned find).

That's not necessarily a disadvantage, and I think in practice it's seldom an issue.

Ok, I agree that's not a very good argument.
 splice is an internal method of the doubly-linked list. As such, it has
 knowledge and access to the list range's implementation and therefore
 has no problem wiring the pointers appropriately. (Note that splice does
 not work with just any ranges.)

True.
 I think the comparison is tenuous - I do agree that we have vectors vs.
 matrices etc., but that doesn't necessarily translate in convincing me
 that there should iterators vs. ranges. Pointers don't have a
 line-specific operation that may make them explode :o).

The analogy was in reference to the unintuitive interfaces: // Plots a point at the beginning of the line void plotPoint(Line line) This is very much like many of the library functions in Phobos: e.g. from Array: size_t insertBefore(Stuff)(Range r, Stuff stuff) Why do we need to give it a range, if we only want to specify one place in the array?
Jul 19 2010
prev sibling parent reply Joaquin M Lopez Munoz <joaquin tid.es> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 On 07/19/2010 04:24 PM, Peter Alexander wrote:
 On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:
 The plan is to use ranges everywhere. Sorry to disappoint. If you can
 find solid arguments for introducing iterators, of course it would be
 great if you discussed them in this group.

Well, you mentioned a few yourself in your article. - With ranges, you double the size of "iterators", which increases the memory usage of something like Boost.MultiIndex.

Agreed.

I'd like to state that Boost.MultiIndex internal implementation is *not* based on iterators, so the whole discussion iterators vs. ranges does not impact Boost.MultiIndex memory usage in any manner. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo
Jul 21 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Joaquin M Lopez Munoz wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 On 07/19/2010 04:24 PM, Peter Alexander wrote:
 On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:
 The plan is to use ranges everywhere. Sorry to disappoint. If you can
 find solid arguments for introducing iterators, of course it would be
 great if you discussed them in this group.

- With ranges, you double the size of "iterators", which increases the memory usage of something like Boost.MultiIndex.


I'd like to state that Boost.MultiIndex internal implementation is *not* based on iterators, so the whole discussion iterators vs. ranges does not impact Boost.MultiIndex memory usage in any manner. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Welcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks! Andrei
Jul 21 2010
parent reply Joaquin M Lopez Munoz <joaquin tid.es> writes:
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Joaquin M Lopez Munoz wrote:
 I'd like to state that Boost.MultiIndex internal implementation is *not*
 based on iterators, so the whole discussion iterators vs. ranges does
 not impact Boost.MultiIndex memory usage in any manner.

 Joaquín M López Muñoz
 Telefónica, Investigación y Desarrollo

Welcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks!

The implementation is based on nodes interlinked with pointers, just as say your favorite std::set implementation. I'll elaborate a bit on this: A std::set is usually implemented as an rb-tree where nodes look like struct node { // header color c; pointer parent,left,right; // payload value_type value; }; Well, A multi_index_container's node is basically a "multinode" with as many headers as indices as well as the payload. For instance, a multi_index_container with two so-called ordered indices uses an internal node that looks like struct node { // header index #0 color c0; pointer parent0,left0,right0; // header index #1 color c1; pointer parent1,left1,right2; // payload value_type value; }; (The reality is more complicated, these nodes are generated through some metaprogramming etc. but you get the idea) There are no iterators involved in the implementation of a multi_index_container. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo PS: I'd be delighted if some bold sould took the challenge of porting Boost.MultiIndex to D. My collected reports show that the lib is quite popular in C++, so having it in D could be welcome. I can't program in D, but if someone decides to go down this path I'd love to assist with discussions on the design and internals. J
Jul 21 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/21/2010 01:18 PM, Joaquin M Lopez Munoz wrote:
 == Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article
 Joaquin M Lopez Munoz wrote:
 I'd like to state that Boost.MultiIndex internal implementation is *not*
 based on iterators, so the whole discussion iterators vs. ranges does
 not impact Boost.MultiIndex memory usage in any manner.

 Joaquín M López Muñoz
 Telefónica, Investigación y Desarrollo

Welcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks!

The implementation is based on nodes interlinked with pointers, just as say your favorite std::set implementation.

That's very illuminating, thanks for the explanation. So there are nodes in fixed positions and they are wired in various ways as dictated by the respective orderings. Very cool.
 PS: I'd be delighted if some bold sould took the challenge of
 porting Boost.MultiIndex to D. My collected reports show
 that the lib is quite popular in C++, so having it in D could
 be welcome. I can't program in D, but if someone decides to
 go down this path I'd love to assist with discussions on
 the design and internals.

That sounds great. I, too, think that multi_index is a very useful structure. It should be quite easy to generalize the up-and-coming RBTree implementation (Steve... :o)) into accepting multiple ordering predicates. Since the number of predicates is available during compilation, the Node structure should be easy to implement by using a fixed-size array for the header. Andrei
Jul 21 2010
prev sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Monday, July 19, 2010 14:24:24 Peter Alexander wrote:
 On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:
 The plan is to use ranges everywhere. Sorry to disappoint. If you can
 find solid arguments for introducing iterators, of course it would be
 great if you discussed them in this group.

Well, you mentioned a few yourself in your article. - With ranges, you double the size of "iterators", which increases the memory usage of something like Boost.MultiIndex. - It makes certain algorithm interfaces awkward, such as rotate. I know you proposed to pass in two ranges, but to me that seems like an desperate attempt to force ranges into an interface that wants iterators. In the case of rotate, you've now burdened the programmer with assuring that the ranges are adjacent (which will probably involve introducing a local variable for maintenance/readability reasons), and you've also increased the amount of data you need to pass into the function by 33%, violating the "Don't pay for what you don't use" philosophy. - You're returning more data than is often wanted from some functions (such as the planned find). - It makes something like STL's std::list::splice *very* awkward. To do splice in constant time (as you should) the "range" is going to need to know about the previous element to its front so that it can update the linked list. What is the planned interface for this? My biggest objection to this is that it is essentially an awkward attempt at abstracting iterators. Ranges are brilliant, and maybe you could even call them a superset of iterators, but just like we have vectors despite having matrices, and points despite having lines, we still want iterators even though we have ranges. They are simply different things.

The only time that I'm aware of where it makes any sense to have an iterator rather than a range is when you need to refer to a single element. And in almost all cases, a range with one element fits the bill just fine. For instance, I don't think that there is any problem whatsoever with find() being entirely range based. It gains nothing by doing anything with iterators. Ranges do become awkward in some places - like if you want to remove what you're searching with find() from the container that you're searching in; you're forced to use take() on the range to feed it to the remove function rather than just giving it the result like you would in C++. However, you do gain a lot in genericity, and trying to force iterators into it would harm that. It may be that something else needs to be done in addition to ranges as they stand (like maybe putting a wrapper around a range which effectively turns it into an iterator on its first element for those few algorithms which would do better with an iterator), but I really haven't found there to be a problem with the lack of iterators. It does require some changes in thinking, but I'd hesitate before trying to mix iterators into the mix. - Jonathan M Davis
Jul 19 2010
prev sibling next sibling parent reply "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 Jul 2010 16:37:22 -0400, Peter Alexander  
<peter.alexander.au gmail.com> wrote:

 I've been following the D programming language for quite some time now,  
 and only recently decided to dive in and start using it. My first  
 impressions are that it is a very nice language (despite the library  
 bugs), but one thing in particular that confused me was the lack of  
 iterators, and their near complete replacement by ranges.

 I did notice that there is an std.iterator library, which is said to be  
 "growing" in the documentation.

 What is the plan for this library? Will the std.algorithm start to use a  
 mixture of iterators and ranges (as it should, in my opinion)?

You may want to check out cursors from dcollections. I apologize, the online docs are still for the D1 version, but you can learn about D2 cursors here: http://www.dsource.org/projects/dcollections/browser/branches/d2/concepts.txt#L21 Note that cursors are still ranges, but enjoy many of the benefits that iterators are used for in STL, such as referring to single elements and using as endpoints for slices. I'm unsure whether Andrei will admit them into phobos. All correspondence I have with him both private and public indicates they will not be admitted. But they are still ranges, so they effectively can be used in some alogrithms (though the usefulness in that capacity remains to be seen). They should make 3-legged algorithms much easier to write, and code that gets ranges from a container much more natural. -Steve
Jul 19 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 19/07/10 10:06 PM, Steven Schveighoffer wrote:
 You may want to check out cursors from dcollections. I apologize, the
 online docs are still for the D1 version, but you can learn about D2
 cursors here:

 http://www.dsource.org/projects/dcollections/browser/branches/d2/concepts.txt#L21


 Note that cursors are still ranges, but enjoy many of the benefits that
 iterators are used for in STL, such as referring to single elements and
 using as endpoints for slices.

 I'm unsure whether Andrei will admit them into phobos. All
 correspondence I have with him both private and public indicates they
 will not be admitted. But they are still ranges, so they effectively can
 be used in some alogrithms (though the usefulness in that capacity
 remains to be seen). They should make 3-legged algorithms much easier to
 write, and code that gets ranges from a container much more natural.

 -Steve

Thanks Steve. That looks good to me :) Andrei, can we convince you to add these into Phobos? P.S. I prefer the name cursor as opposed to iterator (for this usage).
Jul 19 2010
next sibling parent Mafi <mafi example.org> writes:
I have to say that I'm not a specialist in STL or C++ in general but as 
far as I know an iterator is class mainly consisting of a pointer to the 
container, the current index and the operator-overloadd-function for ++.

So what can you do with a iterator that you can't do with
   KeyType delegate(KeyType,Container /* which is indexed by KeyType */)
Jul 19 2010
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/19/2010 04:26 PM, Peter Alexander wrote:
 On 19/07/10 10:06 PM, Steven Schveighoffer wrote:
 You may want to check out cursors from dcollections. I apologize, the
 online docs are still for the D1 version, but you can learn about D2
 cursors here:

 http://www.dsource.org/projects/dcollections/browser/branches/d2/concepts.txt#L21



 Note that cursors are still ranges, but enjoy many of the benefits that
 iterators are used for in STL, such as referring to single elements and
 using as endpoints for slices.

 I'm unsure whether Andrei will admit them into phobos. All
 correspondence I have with him both private and public indicates they
 will not be admitted. But they are still ranges, so they effectively can
 be used in some alogrithms (though the usefulness in that capacity
 remains to be seen). They should make 3-legged algorithms much easier to
 write, and code that gets ranges from a container much more natural.

 -Steve

Thanks Steve. That looks good to me :) Andrei, can we convince you to add these into Phobos?

This has been discussed in the past, you may want to refer to the discussions containing "container" in the title in this group. I was essentially tasked by Walter with deciding, and I decided to go with a different design than the one promoted by dcollections. This is because I believe hierarchies are too constraining to express the multitude of containers in existence. I opted for a design that prescribes certain named functions for methods of specific complexity, and otherwise leaves containers not regimented. Andrei
Jul 19 2010
prev sibling next sibling parent reply PercentEwe <PercentEwe example.com> writes:
== Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 What is the plan for this library? Will the std.algorithm start to use a
 mixture of iterators and ranges (as it should, in my opinion)?

As far as anyone not coming from C++ is concerned, ranges == iterators. Assuming you're coming from C++, ranges == a tuple consisting of a begin iterator and an end iterator. A great idea, I'll readily admit, but it's existed in Java for the past 15 years, and possibly in other languages before. The example Andrei gave about implementing find(range,value)? It's similar in nature to this problem with C# enumerables (iterators are implementations of IEnumerable in C#): http://ayende.com/Blog/archive/2010/06/10/checking-for-empty-enumerations.aspx Not surprisingly, the fix is identical: create an enumerable consisting of the element you popped and the enumerable that you've partially consumed. As for space usage, well, sometimes ranges can give you an improvement, and in the worst case, a range is a struct with begin and end C++ iterators as its members. It's a space improvement unless you don't actually need to iterate through anything, in which case, why are you using an iterator?
 In the thread on improving std.algorithm.find, there were mentions of
 making find (or some findFirst) that returned a single element. Would
 this be an iterator, or a single value range?

Again, why are you using an iterator? Or a range, or enumerable, or what have you? I guess it's a tad easier than: bool tryFind(range, element, out position); or returning a struct containing a success flag and the element found.
Jul 19 2010
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/19/2010 10:27 PM, PercentEwe wrote:
 == Quote from Peter Alexander (peter.alexander.au gmail.com)'s article
 What is the plan for this library? Will the std.algorithm start to use a
 mixture of iterators and ranges (as it should, in my opinion)?

As far as anyone not coming from C++ is concerned, ranges == iterators. Assuming you're coming from C++, ranges == a tuple consisting of a begin iterator and an end iterator. A great idea, I'll readily admit, but it's existed in Java for the past 15 years, and possibly in other languages before.

Agreed, with one amendment: Java et al. offer iterators for traversal only (strictly forward and access to only one element at a time), whereas STL offers traversaly PLUS access (bidirectional and random in addition to one-pass iteration and forward iteration). D's ranges combine the strengths of the two. I've seen similar comments a la, "Ah, D rediscovers Lisp's cdr or Python's iterator etc." and I think they're based on a misunderstanding. Case in point: you can't reverse, sort, binary search, Boyer-Moore search, etc. etc. an iterator that focuses on traversal. Edit distance _might_ be implementable with Java iterators (they must implement clone() properly), but I couldn't find any such implementations that use iterators or for that matter any Java code that does correct edit distance on UTF-16 (I've seen only some that work with UCS-2) - witness to the underlying multi-layered confusion. Essentially "classic" iterators are very algorithm-adverse and frame their users' mind into limited and stilted usage patterns. Andrei
Jul 19 2010
prev sibling next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 20/07/10 4:27 AM, PercentEwe wrote:
 As for space usage, well, sometimes ranges can give you an improvement, and in
the
 worst case, a range is a struct with begin and end C++ iterators as its
members.
 It's a space improvement unless you don't actually need to iterate through
 anything, in which case, why are you using an iterator?

What else do you propose I use? Pointers will work for arrays, but what about lists? You want to point to nodes in lists. To handle this is a general setting, you need an abstract coordinate structure, a.k.a iterator, or cursor.
 In the thread on improving std.algorithm.find, there were mentions of
 making find (or some findFirst) that returned a single element. Would
 this be an iterator, or a single value range?

Again, why are you using an iterator? Or a range, or enumerable, or what have you? I guess it's a tad easier than: bool tryFind(range, element, out position); or returning a struct containing a success flag and the element found.

See above. Iterator is probably a bad name for describing this concept, as it implies that they have the same usage as ranges, but they do not. An iterator/cursor points to one element -- a generic pointer if you like. Ranges define a self-sufficient machine for iteration, which makes them overkill (and unwieldy) when you just want to refer to one element.
Jul 20 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
Some more arguments for iterators/cursors:

1. How would you implement Floyd's cycle finding algorithm using ranges? 
(http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
It uses two iterators over the same range. You would have to wastefully 
use 2 ranges that have the same end coordinate.

2. I often store C++ iterators in container elements so that I can 
quickly remove them when I want to. How can I do this with ranges? I 
have to waste an extra word?

3. To traverse a sequence in random order, I usually do something like this:

   // C is any container
   C c = ...;

   // Create an array of iterators
   vector<C::iterator> order;
   for (C::iterator i = c.begin(); i != c.end(); ++i)
     order.push_back(c);

   std::random_shuffle(order.begin(), order.end());

   for (vector<C::iterator>::iterator i = order.begin();
        i != order.end(); ++i)
   {
     C::iterator it = *i;
     // do stuff with *it
   }

How can I do this with only ranges? Am I again going to have to double 
my memory usage?

4. As an extension to the above, how would you implement rearrangement 
algorithms with ranges? For example, below is the cycle_to permutation 
algorithm from Stepanov's "Elements of Programming":

   template <typename I, typename F>
   void cycle_to(I i, F f)
   {
     I k = f(i);
     while (k != i)
     {
       exchange_values(i, k);
       k = f(k);
     }
   }

f is a function that maps iterators to iterators (read: not ranges to 
ranges). Again, we see that using ranges here does nothing but increase 
our memory requirements, and unnecessarily complicates the code.

---

The recurring theme here is that there are algorithms and practices that 
call for iterators, and while you could use a range ignoring everything 
but the front or back to do the same job, it is simply an awkward way of 
sidestepping the real issue.
Jul 20 2010
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().
 2. I often store C++ iterators in container elements so that I can
 quickly remove them when I want to. How can I do this with ranges? I
 have to waste an extra word?

Yes. What was the largest container of iterators-in-another-container-that-I-want-to-remove-later?
 3. To traverse a sequence in random order, I usually do something like
 this:

 // C is any container
 C c = ...;

 // Create an array of iterators
 vector<C::iterator> order;
 for (C::iterator i = c.begin(); i != c.end(); ++i)
 order.push_back(c);

 std::random_shuffle(order.begin(), order.end());

 for (vector<C::iterator>::iterator i = order.begin();
 i != order.end(); ++i)
 {
 C::iterator it = *i;
 // do stuff with *it
 }

 How can I do this with only ranges? Am I again going to have to double
 my memory usage?

This is a rehash of the indexing argument. If interested in saving memory, you may want to use pointers, which, agreed, can only point to one element so they aren't as powerful as iterators. (But then you'd seldom want to modify an iterator in such a structure.) I don't think such scenarios are compelling enough to warrant introducing iterators alongside ranges.
 4. As an extension to the above, how would you implement rearrangement
 algorithms with ranges? For example, below is the cycle_to permutation
 algorithm from Stepanov's "Elements of Programming":

 template <typename I, typename F>
 void cycle_to(I i, F f)
 {
 I k = f(i);
 while (k != i)
 {
 exchange_values(i, k);
 k = f(k);
 }
 }

 f is a function that maps iterators to iterators (read: not ranges to
 ranges). Again, we see that using ranges here does nothing but increase
 our memory requirements, and unnecessarily complicates the code.

I've always thought that that chapter is rather weak. When did you use cycle_to last time?
 The recurring theme here is that there are algorithms and practices that
 call for iterators, and while you could use a range ignoring everything
 but the front or back to do the same job, it is simply an awkward way of
 sidestepping the real issue.

I agree (with qualifications) with the truthiness of the statement, but not with the alleged dimension of the problem. Also, like many one-sided arguments, this one presents introducing iterators as an all-win deal and neglects the associated costs. Andrei
Jul 20 2010
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:
 
 On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().

That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.

C-style strings and generally all sentinel-terminated sequences.
 It also makes SList ranges less expressive.  For example, what if I 
 wanted a range between two elements in the list?  Such a range is 
 actually unconstructable.  SList is not a very good example of a 
 container, because it is so unique and limited.

To express such ranges in SList I used Take. Andrei
Jul 20 2010
prev sibling next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 20/07/10 2:52 PM, Andrei Alexandrescu wrote:
 I think there's a confusion somewhere. You may want to check out the
 SList definition in std.algorithm. A SList range is exactly one pointer
 thick. With singly-linked lists it's the iterator approach that is
 wasteful because it canonically transports a null pointer as end().

That wastefulness in C++ does not need to be replicated in D. Iterators/cursors would merely be abstract pointers, with ranges still providing the necessary abstractions for range traversal.
 2. I often store C++ iterators in container elements so that I can
 quickly remove them when I want to. How can I do this with ranges? I
 have to waste an extra word?

Yes. What was the largest container of iterators-in-another-container-that-I-want-to-remove-later?

Arbitrarily large. For example, in a physics system, each physics object might store an iterator to the PhysicsManager's container, so that it can quickly remove itself from the linked-list (or whatever container it uses). There's really no limit to how many physics objects there may be -- could easily be in the tens or hundreds of thousands, if not more.
 This is a rehash of the indexing argument. If interested in saving
 memory, you may want to use pointers, which, agreed, can only point to
 one element so they aren't as powerful as iterators. (But then you'd
 seldom want to modify an iterator in such a structure.) I don't think
 such scenarios are compelling enough to warrant introducing iterators
 alongside ranges.

Pointers are fine for arrays, but not lists, or sets etc. That's why you need iterators/cursors as an abstraction of pointers. And yes, it is a rehash of the indexing argument, because that's the only argument. Indexing is what iterators/cursors do, so no argument could be anything other than an indexing argument. I'm just trying to provide examples of where indexing is needed.
 I've always thought that that chapter is rather weak. When did you use
 cycle_to last time?

It doesn't matter if its rarely (if ever) used; the point is that if you wanted to use it, you wouldn't be able to define it in a way that reflected its purpose.
 I agree (with qualifications) with the truthiness of the statement, but
 not with the alleged dimension of the problem. Also, like many one-sided
 arguments, this one presents introducing iterators as an all-win deal
 and neglects the associated costs.

Well, you asked me to present arguments for iterators, not against ;-) I don't deny that there is an cost in implementing iterators, and I certainly appreciate the effort that you have put into developing Phobos. I wouldn't argue for iterators/cursors if I didn't believe their addition would benefit Phobos, and D in general. Out of interest (with the understanding that you accept at least that iterators are useful in some situations), are there any other reasons that you argue against them, other than implementation costs?
Jul 20 2010
parent reply Walter Bright <newshound2 digitalmars.com> writes:
Peter Alexander wrote:
 Out of interest (with the understanding that you accept at least that 
 iterators are useful in some situations), are there any other reasons 
 that you argue against them, other than implementation costs?

The strongest reason against iterators is that they are fundamentally unsafe, as Andrei explains in his paper about ranges. An iterator (as we all know) is based on a pointer, and is often a thin veneer over a pointer. It cannot be checked mechanically to determine if it is safe to increment or dereference. The problem with supporting a dual range/iterator design in Phobos is the library will lose focus, and will become a confusing morass.
Jul 21 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Walter Bright (newshound2 digitalmars.com)'s article
 The strongest reason against iterators is that they are

 Andrei explains in his paper about ranges. An iterator (as we

 on a pointer, and is often a thin veneer over a pointer. It

 mechanically to determine if it is safe to increment or

 The problem with supporting a dual range/iterator design in

 library will lose focus, and will become a confusing morass.

I don't see how it is a dual design. Almost all the algorithms that use ranges now would remain the same. I don't propose that any of that should be changed. All I would like to see is some way to generically point to a single element in a range. I don't actually care about whether these iterators/cursors can be incremented or not because ranges are more useful for iteration. We just need some way to point to single elements (and as I have said before, pointers are no good in non-arraylike containers). The only algorithms I would change are the ones that want iterators/cursors to individual elements (like insertBefore etc.). I would also add a rotate(Range r, Cursor middle) to *complement* bringToFront. I would personally also create a "Cursor find(Range r)", but I can accept arguments for the more flexible version in the library. This is not a massive change, and ranges would still comprise a good 95% of the algorithm code; I just think it's odd to use ranges for those 5% that would make more sense to use cursors.
Jul 21 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Peter Alexander wrote:
 All I would like to see is some way to generically point to a
 single element in a range. I don't actually care about whether
 these iterators/cursors can be incremented or not because ranges
 are more useful for iteration. We just need some way to point to
 single elements (and as I have said before, pointers are no good
 in non-arraylike containers).

I don't understand this. If all you need is access to one individual element, why are pointers inadequate for non-arraylike containers? Knowledge of the container's topology is needed only if moving the iterator around is needed. Andrei
Jul 21 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Andrei Alexandrescu
 I don't understand this. If all you need is access to one

 element, why are pointers inadequate for non-arraylike

 Knowledge of the container's topology is needed only if moving

 iterator around is needed.
 Andrei

There's lots of reasons you need a cursor rather than just a pointer. I've already mentioned most of them. - You can't do myContainer.remove(pointer). You need the cursor for efficient removal. - You can't do the random_shuffle thing I mentioned earlier with just pointers. - You can't implement cycle_to with pointers (whether you need it or not). - You can't use pointers to construct ranges. For example, if you had a "Cursor findFirst(Range r)", you could use the value to construct before and after ranges. Pointers are no use here.
Jul 21 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Peter Alexander wrote:
 == Quote from Andrei Alexandrescu
 I don't understand this. If all you need is access to one

 element, why are pointers inadequate for non-arraylike

 Knowledge of the container's topology is needed only if moving

 iterator around is needed.
 Andrei

There's lots of reasons you need a cursor rather than just a pointer. I've already mentioned most of them. - You can't do myContainer.remove(pointer). You need the cursor for efficient removal.

Ah, yes. Good point. But then I don't see why removing a range is less adequate than removing a pointer.
 - You can't do the random_shuffle thing I mentioned earlier with
 just pointers.

Random shuffle does work with pointers. Take pointers to elements, shuffle the pointers - and you have a winner. In fact pointers alleviate many instances of the "indexes with ranges are more expensive" problem. Contiguous containers that want to support removal can use integers. Node-based containers generally don't need to worry as nodes preserve their position.
 - You can't implement cycle_to with pointers (whether you need it
 or not).

I think this is a bit of a circular argument. First off, cycle_to is trivially implemented with ranges unless the definition of the problem requires use of iterators: void cycle_to(R, F)(R r, F f) { auto k = f(r); while (k != r) { swap(r, k); k = f(k); } } This doesn't consume more memory than the iterator-based counterpart because the number of range objects involved is constant.
 - You can't use pointers to construct ranges. For example, if you
 had a "Cursor findFirst(Range r)", you could use the value to
 construct before and after ranges. Pointers are no use here.

Good point. Andrei
Jul 21 2010
prev sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
Peter Alexander wrote:
 I don't see how it is a dual design. Almost all the algorithms
 that use ranges now would remain the same. I don't propose that
 any of that should be changed.

If some algorithms used ranges and others used iterators, the poor programmer would find himself then obliged to implement both interfaces for each container.
 All I would like to see is some way to generically point to a
 single element in a range.

range[0] ?
 This is not a massive change, and ranges would still comprise a
 good 95% of the algorithm code; I just think it's odd to use
 ranges for those 5% that would make more sense to use cursors.

There is the massive unsafeness of using iterators. We'd like the whole of the algorithms to be guaranteed memory safe, and that cannot happen with iterators. Being able to statically guarantee memory safety is a huge deal, and the larger a program is and the larger the team working on it, the more this matters.
Jul 21 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
== Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence. There aren't two competing interfaces here. If your interface requires a range of elements, you use a range. If it only needs a single element, you use a cursor. For example, sort would always take a range, as it is sorting a range, not a single element. I *do not* propose that we start writing sort(Iter begin, Iter end) as that is much less flexible than a range, and as you say, it is much harder to validate. An example of an algorithm that would take a cursor is insertBefore. There is no reason for it to accept a range, because you are not traversing elements. You just want to insert something before some single point in the range.
 All I would like to see is some way to generically point to a
 single element in a range.


That only works on arrays, therefore it is not generic.
 There is the massive unsafeness of using iterators. We'd like

 algorithms to be guaranteed memory safe, and that cannot happen

 Being able to statically guarantee memory safety is a huge deal,

 a program is and the larger the team working on it, the more

The iterators would not need to be used for iterations. Ranges do a perfectly fine job of that already. They would only be used for referring to individual elements.
Jul 21 2010
next sibling parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence. There aren't two competing interfaces here. If your interface requires a range of elements, you use a range. If it only needs a single element, you use a cursor. For example, sort would always take a range, as it is sorting a range, not a single element. I *do not* propose that we start writing sort(Iter begin, Iter end) as that is much less flexible than a range, and as you say, it is much harder to validate. An example of an algorithm that would take a cursor is insertBefore. There is no reason for it to accept a range, because you are not traversing elements. You just want to insert something before some single point in the range.

This contradicts the assertion that there's no competition between iterators and ranges. Clearly they share at least some turf. Though I agree "insert before this given element" is sensible, I don't think "insert before this range" is not. Besides, with ranges the notion is easier to generalize to "insert after this range" and "replace this range with another range". Arguably "insert after this one element" and "replace this one element with a range" are less general. There are benefits to having cursors. There are also disadvantages: interfaces and implementations get bloated, users get aggravated, documentation gets thicker, conceptual overhead rises, design options multiply without necessity ("should I provide replace with one iterator in addition to replace with a range?"), writing code becomes more painful ("heck, I need a range here but I only have an iterator (or vice versa), I need to insert this extra construct here to build the other") etc. etc. I understand you want to advocate iterators so you chose to not discuss the disaadvantages, but any plan that would ignore them would not be complete. Andrei
Jul 21 2010
next sibling parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence. There aren't two competing interfaces here. If your interface requires a range of elements, you use a range. If it only needs a single element, you use a cursor. For example, sort would always take a range, as it is sorting a range, not a single element. I *do not* propose that we start writing sort(Iter begin, Iter end) as that is much less flexible than a range, and as you say, it is much harder to validate. An example of an algorithm that would take a cursor is insertBefore. There is no reason for it to accept a range, because you are not traversing elements. You just want to insert something before some single point in the range.

This contradicts the assertion that there's no competition between iterators and ranges. Clearly they share at least some turf. Though I agree "insert before this given element" is sensible, I don't think "insert before this range" is not. Besides, with ranges the notion is easier to generalize to "insert after this range" and "replace this range with another range". Arguably "insert after this one element" and "replace this one element with a range" are less general. There are benefits to having cursors. There are also disadvantages: interfaces and implementations get bloated, users get aggravated, documentation gets thicker, conceptual overhead rises, design options multiply without necessity ("should I provide replace with one iterator in addition to replace with a range?"), writing code becomes more painful ("heck, I need a range here but I only have an iterator (or vice versa), I need to insert this extra construct here to build the other") etc. etc. I understand you want to advocate iterators so you chose to not discuss the disaadvantages, but any plan that would ignore them would not be complete.

Well, yes, you could say they share some turf, but that's common when one can be defined in terms of the other. e.g. double norm(Matrix m); double norm(Vector v); Here, vectors are just special cases of matrices, and the matrix version will handle norms of vectors just fine. norm(Matrix) is undeniably more general. Yet, every linear algebra library I've seen would provide both of these, because it's inconvenient (and unintuitive) to have to write norm(Matrix(myVector)); I also find it unintuitive to write insertBefore(Range). Why is it asking me for a range when it's going to ignore everything but the first element? Why can't I just pass in the single position I want to insert before? The same applies for insertAfter. In the case of replacing ranges with other ranges, I don't think there is any need for a cursor version. If you want to replace a cursor, you just dereference and write to it. Having a function to do that would be totally unnecessary.
Jul 21 2010
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Peter Alexander wrote:
 On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence. There aren't two competing interfaces here. If your interface requires a range of elements, you use a range. If it only needs a single element, you use a cursor. For example, sort would always take a range, as it is sorting a range, not a single element. I *do not* propose that we start writing sort(Iter begin, Iter end) as that is much less flexible than a range, and as you say, it is much harder to validate. An example of an algorithm that would take a cursor is insertBefore. There is no reason for it to accept a range, because you are not traversing elements. You just want to insert something before some single point in the range.

This contradicts the assertion that there's no competition between iterators and ranges. Clearly they share at least some turf. Though I agree "insert before this given element" is sensible, I don't think "insert before this range" is not. Besides, with ranges the notion is easier to generalize to "insert after this range" and "replace this range with another range". Arguably "insert after this one element" and "replace this one element with a range" are less general. There are benefits to having cursors. There are also disadvantages: interfaces and implementations get bloated, users get aggravated, documentation gets thicker, conceptual overhead rises, design options multiply without necessity ("should I provide replace with one iterator in addition to replace with a range?"), writing code becomes more painful ("heck, I need a range here but I only have an iterator (or vice versa), I need to insert this extra construct here to build the other") etc. etc. I understand you want to advocate iterators so you chose to not discuss the disaadvantages, but any plan that would ignore them would not be complete.

Well, yes, you could say they share some turf, but that's common when one can be defined in terms of the other. e.g. double norm(Matrix m); double norm(Vector v); Here, vectors are just special cases of matrices, and the matrix version will handle norms of vectors just fine. norm(Matrix) is undeniably more general. Yet, every linear algebra library I've seen would provide both of these, because it's inconvenient (and unintuitive) to have to write norm(Matrix(myVector));

I refute this analogy. Matrices and vectors are different beasts - there's no obviously defined dot product for a matrix etc. I know there are counter-arguments to this, to which I have counter-counter-arguments to which I'm sure there are counter-counter-counter arguments and so on, so I suggest we continue discussing iterators and not the validity of this analogy.
 I also find it unintuitive to write insertBefore(Range). Why is it 
 asking me for a range when it's going to ignore everything but the first 
 element?

Well a pragmatic answer is that you only have ranges in a consistently range-based interface.
 Why can't I just pass in the single position I want to insert 
 before? The same applies for insertAfter.

Because D's containers don't define a notion of "a single position".
 In the case of replacing ranges with other ranges, I don't think there 
 is any need for a cursor version. If you want to replace a cursor, you 
 just dereference and write to it. Having a function to do that would be 
 totally unnecessary.

Maybe you want to replace one element with an entire range. Andrei
Jul 21 2010
prev sibling parent reply "Jim Balter" <Jim Balter.name> writes:
"Peter Alexander" <peter.alexander.au gmail.com> wrote in message 
news:i27p32$dtt$1 digitalmars.com...
 On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense.



Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?
 I don't understand why you see ranges and iterators as conflicting
 concepts. The cursors/iterators are for referring to individual
 elements, and ranges are for specifying iterations over a sequence.

 There aren't two competing interfaces here. If your interface
 requires a range of elements, you use a range. If it only needs a
 single element, you use a cursor.

 For example, sort would always take a range, as it is sorting a
 range, not a single element. I *do not* propose that we start
 writing sort(Iter begin, Iter end) as that is much less flexible
 than a range, and as you say, it is much harder to validate.

 An example of an algorithm that would take a cursor is
 insertBefore. There is no reason for it to accept a range, because
 you are not traversing elements. You just want to insert something
 before some single point in the range.

This contradicts the assertion that there's no competition between iterators and ranges. Clearly they share at least some turf. Though I agree "insert before this given element" is sensible, I don't think "insert before this range" is not. Besides, with ranges the notion is easier to generalize to "insert after this range" and "replace this range with another range". Arguably "insert after this one element" and "replace this one element with a range" are less general. There are benefits to having cursors. There are also disadvantages: interfaces and implementations get bloated, users get aggravated, documentation gets thicker, conceptual overhead rises, design options multiply without necessity ("should I provide replace with one iterator in addition to replace with a range?"), writing code becomes more painful ("heck, I need a range here but I only have an iterator (or vice versa), I need to insert this extra construct here to build the other") etc. etc. I understand you want to advocate iterators so you chose to not discuss the disaadvantages, but any plan that would ignore them would not be complete.

Well, yes, you could say they share some turf, but that's common when one can be defined in terms of the other. e.g. double norm(Matrix m); double norm(Vector v); Here, vectors are just special cases of matrices, and the matrix version will handle norms of vectors just fine. norm(Matrix) is undeniably more general. Yet, every linear algebra library I've seen would provide both of these, because it's inconvenient (and unintuitive) to have to write norm(Matrix(myVector)); I also find it unintuitive to write insertBefore(Range). Why is it asking me for a range when it's going to ignore everything but the first element? Why can't I just pass in the single position I want to insert before? The same applies for insertAfter. In the case of replacing ranges with other ranges, I don't think there is any need for a cursor version. If you want to replace a cursor, you just dereference and write to it. Having a function to do that would be totally unnecessary.

Jul 24 2010
parent reply Peter Alexander <peter.alexander.au gmail.com> writes:
On 24/07/10 2:13 PM, Jim Balter wrote:
 "Peter Alexander" <peter.alexander.au gmail.com> wrote in message
 news:i27p32$dtt$1 digitalmars.com...
 On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense.



Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?

I have written plenty. Care to elaborate?
Jul 24 2010
parent "Jim Balter" <Jim Balter.name> writes:
"Peter Alexander" <peter.alexander.au gmail.com> wrote in message 
news:i2eqf1$1i69$1 digitalmars.com...
 On 24/07/10 2:13 PM, Jim Balter wrote:
 "Peter Alexander" <peter.alexander.au gmail.com> wrote in message
 news:i27p32$dtt$1 digitalmars.com...
 On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense.



Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?

I have written plenty. Care to elaborate?

Sure: you wrote as if Walter were referring to the user of the container class, whereas he was obviously referring to the implementer. What he wrote made plenty of sense, rather than no sense.
Jul 25 2010
prev sibling parent Jonathan M Davis <jmdavisprog gmail.com> writes:
On Wednesday, July 21, 2010 14:39:38 Peter Alexander wrote:
 I also find it unintuitive to write insertBefore(Range). Why is it
 asking me for a range when it's going to ignore everything but the first
 element? Why can't I just pass in the single position I want to insert
 before? The same applies for insertAfter.

Well, considering that any function that you'd be dealing with at this point would give you a range, it's quite natural that what you'd have to pass to insertBefore() would be a range. And really, that's all you need anyway. The first element of the range is what you'd have had an iterator for anyway, so you're really doing the same thing. It's just that you have a whole range instead of the single iterator. Granted, it does seem a little funny to have whole ranges for this, but it works just fine, and trying to mix iterators into phobos will just make it more complicated, and cause concerns for when iterators should be used vs when ranges should be used, as well as how to convert from one to the other. It may be that we need to find a way to extend the functionality of ranges such that some of the more awkward cases are less awkward, but ranges work, and they generally work very well. It just requires thinking about things a bit differently. - Jonathan M Davis
Jul 21 2010
prev sibling next sibling parent Michel Fortin <michel.fortin michelf.com> writes:
On 2010-07-21 13:00:56 -0400, Peter Alexander 
<peter.alexander.au gmail.com> said:

 An example of an algorithm that would take a cursor is
 insertBefore. There is no reason for it to accept a range, because
 you are not traversing elements. You just want to insert something
 before some single point in the range.

From what I understand, you'd like something like this to work: auto range = container[]; auto sortOfIterator = range.front; container.insertBefore(sortOfIterator); Couldn't this be acheived with a 'smart reference' struct? Something like this: struct SmartRef(T) { ref T value() { return *data.ptr; } alias value this; private: SortOfIteratorData data; } Then you define front (and any function normally returning a reference) as: SmartRef!T front(); and it should work as usual, in addition to carrying the extra data you want in your 'iterator'. It's totally transparent (as long as the user uses 'auto' for its references), but it's more burden to the implementor. -- Michel Fortin michel.fortin michelf.com http://michelf.com/
Jul 21 2010
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence.

Right, so the container programmer is obliged to implement both.
 There aren't two competing interfaces here. If your interface
 requires a range of elements, you use a range. If it only needs a
 single element, you use a cursor.

The algorithm is the one doing the requiring, not the container. So, if there are standard algorithms some of which require ranges and others that require interfaces, the container implementor is obliged to provide both.
 All I would like to see is some way to generically point to a
 single element in a range.



Any range can provide a [0] interface.
 There is the massive unsafeness of using iterators. We'd like

 algorithms to be guaranteed memory safe, and that cannot happen

 Being able to statically guarantee memory safety is a huge deal,

 a program is and the larger the team working on it, the more

The iterators would not need to be used for iterations.

Perhaps calling them iterators, then, is a source of confusion!
Jul 21 2010
next sibling parent KennyTM~ <kennytm gmail.com> writes:
On Jul 22, 10 11:56, Walter Bright wrote:
 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence.

Right, so the container programmer is obliged to implement both.
 There aren't two competing interfaces here. If your interface
 requires a range of elements, you use a range. If it only needs a
 single element, you use a cursor.

The algorithm is the one doing the requiring, not the container. So, if there are standard algorithms some of which require ranges and others that require interfaces, the container implementor is obliged to provide both.
 All I would like to see is some way to generically point to a
 single element in a range.



Any range can provide a [0] interface.

I think it's actually ".front".
 There is the massive unsafeness of using iterators. We'd like

 algorithms to be guaranteed memory safe, and that cannot happen

 Being able to statically guarantee memory safety is a huge deal,

 a program is and the larger the team working on it, the more

The iterators would not need to be used for iterations.

Perhaps calling them iterators, then, is a source of confusion!

Jul 22 2010
prev sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
Steven Schveighoffer wrote:
 The algorithm is the one doing the requiring, not the container. So, 
 if there are standard algorithms some of which require ranges and 
 others that require interfaces, the container implementor is obliged 
 to provide both.

Now you are just misinterpreting :) Nobody said anything about D interfaces.

I meant iterators, not interfaces. Sorry for the confusion.
Jul 22 2010
parent BLS <windevguy hotmail.de> writes:
On 22/07/2010 23:00, Steven Schveighoffer wrote:
 collections has a feature where you can swap the underlying
 implementation for something completely different.

ATM I find it pretty hard to implement an other underlying implementation for dcollections. Say an LL RBTree or an Skiplist for dcollections. 1) You've placed a couple of things into the node structure. and IMO it is not always clear why. 2) I am still not happy with your Node(V) instead of Node(K,V) decision. I know about your reasons, but to be honest with you, I am not sure if it's worh the additional programming effort needed for a key-value implementation OR the reduced lines of code just to generalize the node/tree so that it can also handle a vector. f.i) For me this reduction to c!V . (funny enough) creates old bloated/messed up code void* abc(int i, bool A = true, bool B = true, int in_a_very_special_case_here_another_thingy = 0, int cause_DEF_requires_this_param = 0) But heck I can be wrong. Still, comparing for equality seems to be bloated, and (somebody else raises this up), how to implement multi- index with just having c!(V) my 2 cents Bjoern
Jul 23 2010
prev sibling parent reply "Jim Balter" <Jim Balter.name> writes:
"Steven Schveighoffer" <schveiguy yahoo.com> wrote in message 
news:op.vf5kynqgeav7ka localhost.localdomain...
 On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu 
 <SeeWebsiteForEmail erdani.org> wrote:

 On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().

That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.

zstrings, pipes, and various other streams. Various calculated numeric series. Ropes and other binary trees (threaded trees can be traversed with a single pointer and no stack). Probably other classses of containers. And while SLists are "so (sic) unique", very large amounts of very sophisticated code have been written using just that "limited" datatype.
 It also makes SList ranges less expressive.  For example, what if I wanted 
 a range between two elements in the list?  Such a range is actually 
 unconstructable.  SList is not a very good example of a container, because 
 it is so unique and limited.

 -Steve 

Jul 24 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Steven Schveighoffer wrote:
 No, SList is brand new, not much code has been written with it ;)  You 
 may object, but try using it and see how far it takes you.  SList is 
 like a normal singly linked-list but with all the power removed for 
 safety reasons.

SList is intentionally defined as a run-of-the-mill list with no "smarts". I'd be definitely interested in finding ways to make it more powerful. What primitives do you have in mind? Andrei
Jul 26 2010
prev sibling parent Rainer Deyke <rainerd eldwood.com> writes:
On 7/20/2010 01:39, Peter Alexander wrote:
 Iterator is probably a bad name for describing this concept, as it
 implies that they have the same usage as ranges, but they do not. An
 iterator/cursor points to one element -- a generic pointer if you like.
 Ranges define a self-sufficient machine for iteration, which makes them
 overkill (and unwieldy) when you just want to refer to one element.

I agree with this. Ranges are great for iterating, but iterators are better for defining ranges. This leads to confusion. The great strength of STL-type iterators is that you can easily refer to any single element or any range of elements out of a sequence. Take, for example, the 'find' algorithm. When I use 'find' in C++, I use it to find a position, not an element. I can do any of the following: - Iterate through all the items after the found item. - Iterate through all the items before the found item. - Iterate through all the items before the found item, and then iterate through all the items after the found item, with just a single search. - Find two items (in a random-access range) and compare the iterators to see which one comes first. - Iterate through all the items /between/ two found items. The last one is especially interesting to me. STL-style iterators allow me to easily define a range by specifying two end points, even if the end points come from different sources. I don't think this is possible with D-style ranges. It's certainly not possible in any clean way, because D-style ranges have no provision for specifying individual positions in a sequence. -- Rainer Deyke - rainerd eldwood.com
Jul 20 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().

That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length. It also makes SList ranges less expressive. For example, what if I wanted a range between two elements in the list? Such a range is actually unconstructable. SList is not a very good example of a container, because it is so unique and limited. -Steve
Jul 20 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 20 Jul 2010 13:53:37 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Steven Schveighoffer wrote:
 On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> wrote:

 On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using  
 ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to  
 wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().

other container types have ranges with no end pointer or length.

C-style strings and generally all sentinel-terminated sequences.

As long as the sentinel is null or some invalid value. I have sentinel-style containers that use a specific sentinel element, which must be used as the second endpoint. These ranges are generally more flexible in terms of expressing a range over a container. The OP's point is pretty accurate IMO, *most* ranges require two pieces of info, and I agree with you that the cost of extra storage is worth it for the benefits you get. Your singling out of SList as an example of how some containers can implement falsely implies IMO that there are many containers with that style of range, when in fact, most of the ranges are at least two words thick. SList stands alone in that category, at least for the moment. I also expect the majority of containers to not use single-pointer ranges.
 It also makes SList ranges less expressive.  For example, what if I  
 wanted a range between two elements in the list?  Such a range is  
 actually unconstructable.  SList is not a very good example of a  
 container, because it is so unique and limited.

To express such ranges in SList I used Take.

That is not the same. For instance, removing the tail of such a range from a singly-linked list is O(n), where it could be O(1) if the range was two end points. -Steve
Jul 20 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Jul 2010 17:00:35 -0400, Michel Fortin  
<michel.fortin michelf.com> wrote:

 On 2010-07-21 13:00:56 -0400, Peter Alexander  
 <peter.alexander.au gmail.com> said:

 An example of an algorithm that would take a cursor is
 insertBefore. There is no reason for it to accept a range, because
 you are not traversing elements. You just want to insert something
 before some single point in the range.

From what I understand, you'd like something like this to work: auto range = container[]; auto sortOfIterator = range.front; container.insertBefore(sortOfIterator);

From dcollections: auto range = container[]; auto cursor = range.begin; container.insert(cursor, value); Note that insertBefore is reduced to insert, because the ambiguity is gone (there is only one element in a cursor, so it's obvious where you are inserting). -Steve
Jul 22 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 21 Jul 2010 23:56:20 -0400, Walter Bright  
<newshound1 digitalmars.com> wrote:

 Peter Alexander wrote:
 == Quote from Walter Bright (newshound2 digitalmars.com)'s article
 If some algorithms used ranges and others used iterators, the

 would find himself then obliged to implement both interfaces for

This makes no sense. I don't understand why you see ranges and iterators as conflicting concepts. The cursors/iterators are for referring to individual elements, and ranges are for specifying iterations over a sequence.

Right, so the container programmer is obliged to implement both.

With std.container, nobody is obliged to implement anything. If you look at the model, everything is referred to as Stuff, which can be anything. To further this point, SList accepts *two* types of ranges, a normal SList range, and a Take!(Slist.Range) range. Really, a cursor is a Take range of length 1, so it's not a big leap to add such ranges. Also note that typically, "supporting another range type" can be as easy as adding another branch to the template constraint if statement.
 There aren't two competing interfaces here. If your interface
 requires a range of elements, you use a range. If it only needs a
 single element, you use a cursor.

The algorithm is the one doing the requiring, not the container. So, if there are standard algorithms some of which require ranges and others that require interfaces, the container implementor is obliged to provide both.

Now you are just misinterpreting :) Nobody said anything about D interfaces. And ranges are supersets of cursors. All ranges of containers can provide a cursor of the front element. All dcollections ranges provide both begin and end cursors, so if you have a range and you need a cursor, it's just an accessor.
 All I would like to see is some way to generically point to a
 single element in a range.



Any range can provide a [0] interface.

First, that is patently incorrect. You cannot provide a [0] interface, you can only provide a [int] interface. Which means you must throw on all values other than 0, and that is absolutely appalling. Second, when he says point to a single element, he doesn't mean point to any element picked by the container, he means point to a *specific* element. For example, he may want a pointer to the second element.
 There is the massive unsafeness of using iterators. We'd like

 algorithms to be guaranteed memory safe, and that cannot happen

 Being able to statically guarantee memory safety is a huge deal,

 a program is and the larger the team working on it, the more

The iterators would not need to be used for iterations.

Perhaps calling them iterators, then, is a source of confusion!

Yeah, dcollections changed iterators to cursor early on to avoid the confusion with C++ iterators, which they are not. -Steve
Jul 22 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Thu, 22 Jul 2010 16:13:21 -0400, Walter Bright  
<newshound1 digitalmars.com> wrote:

 Steven Schveighoffer wrote:
 The algorithm is the one doing the requiring, not the container. So,  
 if there are standard algorithms some of which require ranges and  
 others that require interfaces, the container implementor is obliged  
 to provide both.

interfaces.

I meant iterators, not interfaces. Sorry for the confusion.

OK, sorry for my confusion :) The unquoted message that you responded to made me think you intended to type interfaces was: "There aren't two competing interfaces here. If your interface requires a range of elements, you use a range. If it only needs a single element, you use a cursor." From my experience with dcollections, implementing cursors in addition to ranges is very trivial. Most node-based container types use "iterators", or pointers to elements underneath ranges anyways. It's generally not an extra effort to expose them correctly. I think cursors solve the safety issue quite well. If you are using duck typing instead of interfaces, it's even easier, since you can cover both ranges and cursors with one function (you can make a range out of a cursor, or a pair of cursors from a range very easily, and then call your implemented function). Dcollections has a feature where you can swap the underlying implementation for something completely different. The interface between the container class and the implementation is some sort of iterator-like idiom. I plan to homogenize this, and make it better documented. Hopefully it will become much easier to swap implementations in the future. -Steve
Jul 22 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Sat, 24 Jul 2010 09:01:14 -0400, Jim Balter <Jim balter.name> wrote:

 "Steven Schveighoffer" <schveiguy yahoo.com> wrote in message  
 news:op.vf5kynqgeav7ka localhost.localdomain...
 On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu  
 <SeeWebsiteForEmail erdani.org> wrote:

 On 07/20/2010 03:01 AM, Peter Alexander wrote:
 Some more arguments for iterators/cursors:

 1. How would you implement Floyd's cycle finding algorithm using  
 ranges?
 (http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare)
 It uses two iterators over the same range. You would have to  
 wastefully
 use 2 ranges that have the same end coordinate.

I think there's a confusion somewhere. You may want to check out the SList definition in std.algorithm. A SList range is exactly one pointer thick. With singly-linked lists it's the iterator approach that is wasteful because it canonically transports a null pointer as end().

That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.

zstrings, pipes, and various other streams.

Streams are in a completely different category. They are not containers. I personally feel that imposing the range/iterator/cursor idiom on top of a stream is a problematic model that's only done "because you can." Kind of like the one-liner qsort in a functional language.
 Various calculated numeric series.

Those don't have ends afaik, and are read-only. Take works perfectly fine in those cases where you need "n elements", in which case you have an end point ;)
 Ropes and other binary trees (threaded trees can be traversed with a  
 single pointer and no stack).

I'm not familiar with the internal structure of Ropes. Look, technically, any node-based container can have a single-pointer range, but it leaves you with only one type of range -- one that goes to the end. That doesn't sound very useful to me.
 Probably other classses of containers. And while SLists are "so (sic)  
 unique",

I meant 'so'
 very large amounts of very sophisticated code have been written using  
 just that "limited" datatype.

No, SList is brand new, not much code has been written with it ;) You may object, but try using it and see how far it takes you. SList is like a normal singly linked-list but with all the power removed for safety reasons. -Steve
Jul 26 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 23 Jul 2010 20:05:21 -0400, BLS <windevguy hotmail.de> wrote:

 On 22/07/2010 23:00, Steven Schveighoffer wrote:
 collections has a feature where you can swap the underlying
 implementation for something completely different.

ATM I find it pretty hard to implement an other underlying implementation for dcollections. Say an LL RBTree or an Skiplist for dcollections.

I hope we can talk about how to fix it, send me an email. AFAIK, nobody (including myself) has tried to swap out implementations, so the "able to swap out implementations" is only a theory :) Perhaps the feature can't work, I'm not sure.
 1) You've placed a couple of things into the node structure. and IMO it
 is not always clear  why.

Yeah, documentation is poor. Please let me know the issues, and I can explain. Eventually, I want to document everything properly.
 2) I am still not happy with your Node(V) instead of Node(K,V) decision.
 I know about your reasons, but to be honest with you, I am not sure if
 it's worh the additional programming effort needed for a  key-value
 implementation OR the reduced lines of code just to generalize the
 node/tree so that it can also handle a vector. f.i)

 For me this reduction to c!V . (funny enough) creates old bloated/messed
 up code

 void* abc(int i, bool A = true, bool B = true, int
 in_a_very_special_case_here_another_thingy  = 0, int
 cause_DEF_requires_this_param = 0)

 But heck I can be wrong. Still, comparing for equality seems to be
 bloated, and (somebody else raises this up), how to implement multi-
 index with just having c!(V)

Let's work to fix it. I want dcollections to be as usable as possible. -Steve
Jul 26 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 26 Jul 2010 14:27:11 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:

 Steven Schveighoffer wrote:
 No, SList is brand new, not much code has been written with it ;)  You  
 may object, but try using it and see how far it takes you.  SList is  
 like a normal singly linked-list but with all the power removed for  
 safety reasons.

SList is intentionally defined as a run-of-the-mill list with no "smarts". I'd be definitely interested in finding ways to make it more powerful. What primitives do you have in mind?

- O(1) removal (of 1 or multiple elements), insertion, and splicing. - sorting. Can't think of any more right now, but the sorting is somewhat secondary. The O(1) ops are essential to any usable LL impl. -Steve
Jul 26 2010
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 23 Jul 2010 20:05:21 -0400, BLS <windevguy hotmail.de> wrote:

 On 22/07/2010 23:00, Steven Schveighoffer wrote:
 collections has a feature where you can swap the underlying
 implementation for something completely different.

ATM I find it pretty hard to implement an other underlying implementation for dcollections.

Sorry to do this on the D forum, but I don't know how else to contact you. I got your email, but when I send a reply message, it bounces. Not sure why, here is the message from yahoo mail: Hi. This is the qmail-send program at yahoo.com. I'm afraid I wasn't able to deliver your message to the following addresses. This is a permanent error; I've given up. Sorry it didn't work out. <windevguy hotmail.de>: 65.55.37.88 does not like recipient. Remote host said: 550 Requested action not taken: mailbox unavailable Giving up on 65.55.37.88. -Steve
Jul 27 2010
prev sibling parent reply Bruno Medeiros <brunodomedeiros+spam com.gmail> writes:
On 20/07/2010 04:27, PercentEwe wrote:
 As far as anyone not coming from C++ is concerned, ranges == iterators.

Actually, thanks for pointing that out. It took me a while to figure that out, as it wasn't immediately clear. Sure, some D ranges also offer random access and are generally more powerful and better abstracted than iterators in other languages, but the basic functionality is still iterating/traversing and doing something on the current element. Also, when I think of "range" I think of the mathematical range/interval, which have a few aspects that don't match with D ranges: * they always have a length, it is "always" known, and "available immediatly", so to speak... * real ranges (as in real numbers) don't have a set of discrete elements, but rather a infinite set of contiguous elements. (except for the degenerate cases of course) Yeah, this is a very minor issue, and can be just my personal bias. But its worth to keep in mind if ever you want to explain D ranges to a D newbie who is familiar with iterators in languages other than C/C++. -- Bruno Medeiros - Software Engineer
Jul 27 2010
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Bruno Medeiros wrote:
 On 20/07/2010 04:27, PercentEwe wrote:
 As far as anyone not coming from C++ is concerned, ranges == iterators.

Actually, thanks for pointing that out. It took me a while to figure that out, as it wasn't immediately clear. Sure, some D ranges also offer random access and are generally more powerful and better abstracted than iterators in other languages, but the basic functionality is still iterating/traversing and doing something on the current element.

Good point. Two highly related (and interrelated) pieces of work: http://lambda-the-ultimate.org/node/1224 http://okmij.org/ftp/papers/LL3-collections-talk.pdf Oleg makes great points, but there are powerful retorts to many of them. I dream of finding the time to write a retort to that work one day. Andrei
Jul 27 2010
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Mon, 19 Jul 2010 17:54:59 -0400, Mafi <mafi example.org> wrote:

 I have to say that I'm not a specialist in STL or C++ in general but as  
 far as I know an iterator is class mainly consisting of a pointer to the  
 container, the current index and the operator-overloadd-function for ++.

 So what can you do with a iterator that you can't do with
    KeyType delegate(KeyType,Container /* which is indexed by KeyType */)

No, an iterator is a pointer to an *element* in the container. The lookup is a simple dereference, not an indexing operation. They even work on containers that don't support indexing. The benefit of iterators is speed of lookup and reference to a single element. Ranges represent a pair of iterators, with the benefit that they are always properly ordered and are related. Many STL functions accept 2 iterators but are undefined if the two iterators are not related or ordered properly. Ranges have a huge benefit over iterators for this, and most of STL's algorithm is based on pairs of iterators. However, ranges generally refer to *two* elements, a begin and an end element. This has some disadvantages when you want to only refer to one element. -Steve
Jul 20 2010