digitalmars.D - Are iterators and ranges going to co-exist?
- Peter Alexander (17/17) Jul 19 2010 I've been following the D programming language for quite some time now,
- Andrei Alexandrescu (9/26) Jul 19 2010 The plan is to use ranges everywhere. Sorry to disappoint. If you can
- Peter Alexander (25/28) Jul 19 2010 Well, you mentioned a few yourself in your article.
- Andrei Alexandrescu (15/44) Jul 19 2010 Phobos' bringToFront does not assume the ranges are adjacent.
- Peter Alexander (15/29) Jul 19 2010 My point still stands: if you want to rotate then you need pass in
- Joaquin M Lopez Munoz (6/18) Jul 21 2010 I'd like to state that Boost.MultiIndex internal implementation is *not*
- Andrei Alexandrescu (4/22) Jul 21 2010 Welcome, Joaquín! Good to see you here. Could you please provide a bit
- Joaquin M Lopez Munoz (41/50) Jul 21 2010 The implementation is based on nodes interlinked with pointers,
- Andrei Alexandrescu (12/31) Jul 21 2010 [snip]
- Jay Norwood (6/20) Mar 21 2012 I didn't find a follow-up discussion to this thread. Was any
- Jonathan M Davis (18/53) Jul 19 2010 The only time that I'm aware of where it makes any sense to have an iter...
- bearophile (12/20) Mar 21 2012 The "Don't pay for what you don't use" is a C++ rule, it's not a
- Steven Schveighoffer (16/25) Jul 19 2010 You may want to check out cursors from dcollections. I apologize, the
- Peter Alexander (4/18) Jul 19 2010 Thanks Steve. That looks good to me :)
- Mafi (5/5) Jul 19 2010 I have to say that I'm not a specialist in STL or C++ in general but as
- Steven Schveighoffer (13/18) Jul 20 2010 No, an iterator is a pointer to an *element* in the container. The look...
- Andrei Alexandrescu (10/33) Jul 19 2010 This has been discussed in the past, you may want to refer to the
- PercentEwe (18/23) Jul 19 2010 As far as anyone not coming from C++ is concerned, ranges == iterators.
- Andrei Alexandrescu (18/25) Jul 19 2010 Agreed, with one amendment: Java et al. offer iterators for traversal
- Peter Alexander (11/21) Jul 20 2010 What else do you propose I use?
- Peter Alexander (45/45) Jul 20 2010 Some more arguments for iterators/cursors:
- Andrei Alexandrescu (20/65) Jul 20 2010 I think there's a confusion somewhere. You may want to check out the
- Steven Schveighoffer (9/20) Jul 20 2010 That is an example of a single exception to the rule :) AFAIK, no other...
- Andrei Alexandrescu (4/27) Jul 20 2010 To express such ranges in SList I used Take.
- Steven Schveighoffer (18/45) Jul 20 2010 As long as the sentinel is null or some invalid value. I have
- Jim Balter (7/28) Jul 24 2010 zstrings, pipes, and various other streams. Various calculated numeric
- Steven Schveighoffer (18/49) Jul 26 2010 Streams are in a completely different category. They are not containers...
- Andrei Alexandrescu (5/9) Jul 26 2010 SList is intentionally defined as a run-of-the-mill list with no
- Steven Schveighoffer (7/15) Jul 26 2010 - O(1) removal (of 1 or multiple elements), insertion, and splicing.
- Peter Alexander (27/48) Jul 20 2010 That wastefulness in C++ does not need to be replicated in D.
- Walter Bright (7/10) Jul 21 2010 The strongest reason against iterators is that they are fundamentally un...
- Peter Alexander (24/30) Jul 21 2010 all know) is based
- Andrei Alexandrescu (6/12) Jul 21 2010 I don't understand this. If all you need is access to one individual
- Peter Alexander (15/20) Jul 21 2010 containers?
- Andrei Alexandrescu (25/47) Jul 21 2010 Ah, yes. Good point. But then I don't see why removing a range is less
- Walter Bright (8/16) Jul 21 2010 If some algorithms used ranges and others used iterators, the poor progr...
- Peter Alexander (26/35) Jul 21 2010 each container.
- Andrei Alexandrescu (19/44) Jul 21 2010 This contradicts the assertion that there's no competition between
- Peter Alexander (18/61) Jul 21 2010 Well, yes, you could say they share some turf, but that's common when
- Jonathan M Davis (16/20) Jul 21 2010 Well, considering that any function that you'd be dealing with at this p...
- Andrei Alexandrescu (12/80) Jul 21 2010 I refute this analogy. Matrices and vectors are different beasts -
- Jim Balter (4/67) Jul 24 2010 Er, um, perhaps you have never written a container class and don't know...
- Peter Alexander (3/16) Jul 24 2010 I have written plenty.
- Jim Balter (5/23) Jul 25 2010 Sure: you wrote as if Walter were referring to the user of the container...
- Michel Fortin (23/27) Jul 21 2010 From what I understand, you'd like something like this to work:
- Steven Schveighoffer (10/20) Jul 22 2010 From dcollections:
- Walter Bright (8/36) Jul 21 2010 The algorithm is the one doing the requiring, not the container. So, if
- KennyTM~ (2/38) Jul 22 2010
- Steven Schveighoffer (24/57) Jul 22 2010 With std.container, nobody is obliged to implement anything. If you loo...
- Walter Bright (2/9) Jul 22 2010 I meant iterators, not interfaces. Sorry for the confusion.
- Steven Schveighoffer (22/30) Jul 22 2010 OK, sorry for my confusion :) The unquoted message that you responded t...
- BLS (21/23) Jul 23 2010 ATM I find it pretty hard to implement an other underlying
- Steven Schveighoffer (9/30) Jul 26 2010 I hope we can talk about how to fix it, send me an email. AFAIK, nobody...
- Steven Schveighoffer (13/18) Jul 27 2010 Sorry to do this on the D forum, but I don't know how else to contact yo...
- Rainer Deyke (23/28) Jul 20 2010 I agree with this. Ranges are great for iterating, but iterators are
- Bruno Medeiros (19/20) Jul 27 2010 Actually, thanks for pointing that out. It took me a while to figure
- Andrei Alexandrescu (7/19) Jul 27 2010 Good point. Two highly related (and interrelated) pieces of work:
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
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
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
On 07/19/2010 04:24 PM, Peter Alexander wrote:On 19/07/10 9:47 PM, Andrei Alexandrescu wrote:Agreed.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.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
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.Ok, I agree that's not a very good argument.- 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.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
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleOn 07/19/2010 04:24 PM, Peter Alexander 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 DesarrolloOn 19/07/10 9:47 PM, Andrei Alexandrescu wrote:Agreed.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.
Jul 21 2010
Joaquin M Lopez Munoz wrote:== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleWelcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks! AndreiOn 07/19/2010 04:24 PM, Peter Alexander 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 DesarrolloOn 19/07/10 9:47 PM, Andrei Alexandrescu wrote:Agreed.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.
Jul 21 2010
== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s articleJoaquin M Lopez Munoz wrote: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 { color c0; pointer parent0,left0,right0; 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. JI'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 DesarrolloWelcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks!
Jul 21 2010
On 07/21/2010 01:18 PM, Joaquin M Lopez Munoz wrote:== Quote from Andrei Alexandrescu (SeeWebsiteForEmail erdani.org)'s article[snip] 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.Joaquin M Lopez Munoz wrote:The implementation is based on nodes interlinked with pointers, just as say your favorite std::set implementation.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 DesarrolloWelcome, Joaquín! Good to see you here. Could you please provide a bit more detail? Does Boost.MultiIndex use pointers? Thanks!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
On Wednesday, 21 July 2010 at 19:25:26 UTC, Andrei Alexandrescu wrote:I didn't find a follow-up discussion to this thread. Was any further discussion done on the use of the RBTree for MultiIndex in D? jayPS: 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
Mar 21 2012
On Monday, July 19, 2010 14:24:24 Peter Alexander wrote:On 19/07/10 9:47 PM, Andrei Alexandrescu wrote: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 DavisThe 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
Peter Alexander: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.The "Don't pay for what you don't use" is a C++ rule, it's not a D Zen rule. In D you sometimes pay a little if it gives back enough safety or convenience elsewhere. In D there are usually ways to not pay, but you have to ask for it explicitly.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.There is also a price to pay if you want both abstractions in Phobos. A single abstraction makes things simpler, more compatible with each other, etc. Example: D has opApply, but at the moment nearly nothing in Phobos supports opApply (array() and foreachType, I'd like a third Phobos thing to support it). Bye, bearophile
Mar 21 2012
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
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. -SteveThanks 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
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
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
On 07/19/2010 04:26 PM, Peter Alexander wrote:On 19/07/10 10:06 PM, Steven Schveighoffer wrote: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. AndreiYou 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. -SteveThanks Steve. That looks good to me :) Andrei, can we convince you to add these into Phobos?
Jul 19 2010
== Quote from Peter Alexander (peter.alexander.au gmail.com)'s articleWhat 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 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
On 07/19/2010 10:27 PM, PercentEwe wrote:== Quote from Peter Alexander (peter.alexander.au gmail.com)'s articleAgreed, 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. AndreiWhat 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.
Jul 19 2010
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.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.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 20 2010
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
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
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: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. -SteveSome 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().
Jul 20 2010
Steven Schveighoffer wrote:On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:C-style strings and generally all sentinel-terminated sequences.On 07/20/2010 03:01 AM, Peter Alexander wrote:That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.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().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
On Tue, 20 Jul 2010 13:53:37 -0400, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Steven Schveighoffer wrote: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.On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:C-style strings and generally all sentinel-terminated sequences.On 07/20/2010 03:01 AM, Peter Alexander wrote:That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.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 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. -SteveIt 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.
Jul 20 2010
"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: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.On 07/20/2010 03:01 AM, Peter Alexander wrote:That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.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().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
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...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.On Tue, 20 Jul 2010 09:52:00 -0400, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:zstrings, pipes, and various other streams.On 07/20/2010 03:01 AM, Peter Alexander wrote:That is an example of a single exception to the rule :) AFAIK, no other container types have ranges with no end pointer or length.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().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
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
On Mon, 26 Jul 2010 14:27:11 -0400, Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> wrote:Steven Schveighoffer wrote:- 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. -SteveNo, 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?
Jul 26 2010
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.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.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?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
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
== Quote from Walter Bright (newshound2 digitalmars.com)'s articleThe strongest reason against iterators is that they arefundamentally unsafe, asAndrei explains in his paper about ranges. An iterator (as weall know) is basedon a pointer, and is often a thin veneer over a pointer. Itcannot be checkedmechanically to determine if it is safe to increment ordereference.The problem with supporting a dual range/iterator design inPhobos is thelibrary 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
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
== Quote from Andrei AlexandrescuI don't understand this. If all you need is access to oneindividualelement, why are pointers inadequate for non-arraylikecontainers?Knowledge of the container's topology is needed only if movingtheiterator around is needed. AndreiThere'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
Peter Alexander wrote:== Quote from Andrei AlexandrescuAh, yes. Good point. But then I don't see why removing a range is less adequate than removing a pointer.I don't understand this. If all you need is access to oneindividualelement, why are pointers inadequate for non-arraylikecontainers?Knowledge of the container's topology is needed only if movingtheiterator around is needed. AndreiThere'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.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
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
== Quote from Walter Bright (newshound2 digitalmars.com)'s articleIf some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.That only works on arrays, therefore it is not generic.All I would like to see is some way to generically point to a single element in a range.range[0] ?There is the massive unsafeness of using iterators. We'd likethe whole of thealgorithms to be guaranteed memory safe, and that cannot happenwith iterators.Being able to statically guarantee memory safety is a huge deal,and the largera program is and the larger the team working on it, the morethis matters. 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
Peter Alexander wrote:== Quote from Walter Bright (newshound2 digitalmars.com)'s articleThis 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. AndreiIf some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.
Jul 21 2010
On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:Peter Alexander wrote: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.== Quote from Walter Bright (newshound2 digitalmars.com)'s articleThis 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.If some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.
Jul 21 2010
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
Peter Alexander wrote:On 21/07/10 6:33 PM, Andrei Alexandrescu wrote: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.Peter Alexander wrote: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));== Quote from Walter Bright (newshound2 digitalmars.com)'s articleThis 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.If some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.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
"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:Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?Peter Alexander wrote:== Quote from Walter Bright (newshound2 digitalmars.com)'s articleIf some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. This makes no sense.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.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.
Jul 24 2010
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...I have written plenty. Care to elaborate?On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?Peter Alexander wrote:== Quote from Walter Bright (newshound2 digitalmars.com)'s articleIf some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. This makes no sense.
Jul 24 2010
"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: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."Peter Alexander" <peter.alexander.au gmail.com> wrote in message news:i27p32$dtt$1 digitalmars.com...I have written plenty. Care to elaborate?On 21/07/10 6:33 PM, Andrei Alexandrescu wrote:Er, um, perhaps you have never written a container class and don't know what "implement an interface" means?Peter Alexander wrote:== Quote from Walter Bright (newshound2 digitalmars.com)'s articleIf some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. This makes no sense.
Jul 25 2010
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
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: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). -SteveAn 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);
Jul 22 2010
Peter Alexander wrote:== Quote from Walter Bright (newshound2 digitalmars.com)'s articleRight, so the container programmer is obliged to implement both.If some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.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.Any range can provide a [0] interface.That only works on arrays, therefore it is not generic.All I would like to see is some way to generically point to a single element in a range.range[0] ?Perhaps calling them iterators, then, is a source of confusion!There is the massive unsafeness of using iterators. We'd likethe whole of thealgorithms to be guaranteed memory safe, and that cannot happenwith iterators.Being able to statically guarantee memory safety is a huge deal,and the largera program is and the larger the team working on it, the morethis matters. The iterators would not need to be used for iterations.
Jul 21 2010
On Jul 22, 10 11:56, Walter Bright wrote:Peter Alexander wrote:I think it's actually ".front".== Quote from Walter Bright (newshound2 digitalmars.com)'s articleRight, so the container programmer is obliged to implement both.If some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.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.Any range can provide a [0] interface.That only works on arrays, therefore it is not generic.All I would like to see is some way to generically point to a single element in a range.range[0] ?Perhaps calling them iterators, then, is a source of confusion!There is the massive unsafeness of using iterators. We'd likethe whole of thealgorithms to be guaranteed memory safe, and that cannot happenwith iterators.Being able to statically guarantee memory safety is a huge deal,and the largera program is and the larger the team working on it, the morethis matters. The iterators would not need to be used for iterations.
Jul 22 2010
On Wed, 21 Jul 2010 23:56:20 -0400, Walter Bright <newshound1 digitalmars.com> wrote:Peter Alexander wrote: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.== Quote from Walter Bright (newshound2 digitalmars.com)'s articleRight, so the container programmer is obliged to implement both.If some algorithms used ranges and others used iterators, thepoor programmerwould find himself then obliged to implement both interfaces foreach container. 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.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.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.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.Any range can provide a [0] interface.That only works on arrays, therefore it is not generic.All I would like to see is some way to generically point to a single element in a range.range[0] ?Yeah, dcollections changed iterators to cursor early on to avoid the confusion with C++ iterators, which they are not. -StevePerhaps calling them iterators, then, is a source of confusion!There is the massive unsafeness of using iterators. We'd likethe whole of thealgorithms to be guaranteed memory safe, and that cannot happenwith iterators.Being able to statically guarantee memory safety is a huge deal,and the largera program is and the larger the team working on it, the morethis matters. The iterators would not need to be used for iterations.
Jul 22 2010
Steven Schveighoffer wrote:I meant iterators, not interfaces. Sorry for the confusion.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.
Jul 22 2010
On Thu, 22 Jul 2010 16:13:21 -0400, Walter Bright <newshound1 digitalmars.com> wrote:Steven Schveighoffer wrote: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. -SteveI meant iterators, not interfaces. Sorry for the confusion.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.
Jul 22 2010
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
On Fri, 23 Jul 2010 20:05:21 -0400, BLS <windevguy hotmail.de> wrote:On 22/07/2010 23:00, Steven Schveighoffer wrote: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.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.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
On Fri, 23 Jul 2010 20:05:21 -0400, BLS <windevguy hotmail.de> wrote:On 22/07/2010 23:00, Steven Schveighoffer wrote: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. -Stevecollections 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.
Jul 27 2010
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
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
Bruno Medeiros wrote:On 20/07/2010 04:27, PercentEwe wrote: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. AndreiAs 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.
Jul 27 2010