Iterators Must Go (Ahead)
Hello, I wrote an article about D's ranges, contrasting them to other iteration idioms. Those who'd be interested in reviewing the article, please send me email. (I may not be able to reply to all requests.) The article has very few prerequisites, so I encourage people who aren't very versed in the subject. Thanks, Andrei
Re: Iterators Must Go video online
Tim Matthews wrote: On Mon, 03 Aug 2009 12:47:40 -0500 Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei I may have been mistaken but I thought I heard you say you re wrote the iterators as ranges twice. Once for D's std.range and once for C++ STL but I heard you then saying someone should re write STL. Do you have a re write of STL on the net anywhere? I wrote D's algorithms twice: once with iterators, once with ranges. Andrei
Re: Iterators Must Go video online
On Mon, 03 Aug 2009 12:47:40 -0500 Andrei Alexandrescu wrote: > A while ago I mentioned the video of my BoostCon keynote "Iterators > Must Go" will be soon available online. Here it is: > > http://boostcon.blip.tv/ > > > Andrei I may have been mistaken but I thought I heard you say you re wrote the iterators as ranges twice. Once for D's std.range and once for C++ STL but I heard you then saying someone should re write STL. Do you have a re write of STL on the net anywhere?
Re: Iterators Must Go video online
Sergey Gromov wrote: Mon, 03 Aug 2009 12:47:40 -0500, Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei Nice talk! The "Try THAT with iterators, @"($#* !" part was especially entertaining. XD What I didn't get was why range.front is so much superior to *i. At the end of the day they're both just functions returning whatever they please. range.front could insert a cheap check for validity, i.e. assert(!empty). *i has no chance; it puts the burden of precondition on its user. Andrei
Re: Iterators Must Go video online
grauzone wrote: > Daniel Keep wrote: >> >> grauzone wrote: >>> torhu wrote: >>>> On 03.08.2009 19:47, Andrei Alexandrescu wrote: >>>>> A while ago I mentioned the video of my BoostCon keynote "Iterators >>>>> Must >>>>> Go" will be soon available online. Here it is: >>>>> >>>>> http://boostcon.blip.tv/ >>>>> >>>>> >>>>> Andrei >>>> Cool. I'm having some trouble skipping to the parts I'm interested in, >>>> can anyone point me to a downloadable video? >>> This works for me: >>> wget >>> 'http://blip.tv/file/get/Boostcon-BoostCon2009Keynote487.flv?referrer=boostcon.blip.tv&ext=.flv' >>> >>> >>> >>> I didn't find a download link, but had to go through the sourcecode and >>> had to deal with their JavaScript/AJAX/XML crap. Why? >> >> Because you don't have the LiveHTTPHeaders extension for Firefox >> installed so you can sniff the URLs as it grabs stuff. Bwahahaha. >> >> (Actually, I usually just use an extension that lets me search the >> cache.) > > And if I don't use Firefox? kdesu wireshark! Works for me.
Re: Iterators Must Go video online
Mon, 03 Aug 2009 12:47:40 -0500, Andrei Alexandrescu wrote: > A while ago I mentioned the video of my BoostCon keynote "Iterators Must > Go" will be soon available online. Here it is: > > http://boostcon.blip.tv/ > > Andrei Nice talk! The "Try THAT with iterators, @"($#* !" part was especially entertaining. XD What I didn't get was why range.front is so much superior to *i. At the end of the day they're both just functions returning whatever they please.
Re: Iterators Must Go video online
Daniel Keep wrote: grauzone wrote: torhu wrote: On 03.08.2009 19:47, Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei Cool. I'm having some trouble skipping to the parts I'm interested in, can anyone point me to a downloadable video? This works for me: wget 'http://blip.tv/file/get/Boostcon-BoostCon2009Keynote487.flv?referrer=boostcon.blip.tv&ext=.flv' I didn't find a download link, but had to go through the sourcecode and had to deal with their JavaScript/AJAX/XML crap. Why? Because you don't have the LiveHTTPHeaders extension for Firefox installed so you can sniff the URLs as it grabs stuff. Bwahahaha. (Actually, I usually just use an extension that lets me search the cache.) And if I don't use Firefox? Anyway, the intention of blip.tv seems to be not to allow users downloading content, at least in no obvious way. They're probably just too lazy to implement more strict DRM. Same with Youtube.
Re: Iterators Must Go video online
grauzone wrote: > torhu wrote: >> On 03.08.2009 19:47, Andrei Alexandrescu wrote: >>> A while ago I mentioned the video of my BoostCon keynote "Iterators Must >>> Go" will be soon available online. Here it is: >>> >>> http://boostcon.blip.tv/ >>> >>> >>> Andrei >> >> Cool. I'm having some trouble skipping to the parts I'm interested in, >> can anyone point me to a downloadable video? > > This works for me: > wget > 'http://blip.tv/file/get/Boostcon-BoostCon2009Keynote487.flv?referrer=boostcon.blip.tv&ext=.flv' > > > I didn't find a download link, but had to go through the sourcecode and > had to deal with their JavaScript/AJAX/XML crap. Why? Because you don't have the LiveHTTPHeaders extension for Firefox installed so you can sniff the URLs as it grabs stuff. Bwahahaha. (Actually, I usually just use an extension that lets me search the cache.)
Re: Iterators Must Go video online
torhu wrote: On 03.08.2009 19:47, Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei Cool. I'm having some trouble skipping to the parts I'm interested in, can anyone point me to a downloadable video? This works for me: wget 'http://blip.tv/file/get/Boostcon-BoostCon2009Keynote487.flv?referrer=boostcon.blip.tv&ext=.flv' I didn't find a download link, but had to go through the sourcecode and had to deal with their JavaScript/AJAX/XML crap. Why?
Re: Iterators Must Go video online
On 03.08.2009 19:47, Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei Cool. I'm having some trouble skipping to the parts I'm interested in, can anyone point me to a downloadable video?
Re: Iterators Must Go video online
On Mon, 3 Aug 2009, Andrei Alexandrescu wrote: > A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" > will be soon available online. Here it is: > > http://boostcon.blip.tv/ > > > Andrei Good talk.. I remember reviewing the slides from when you gave the talk originally at the accu conference. :) The very last question has a very simple answer that you forgot about and sort of danced around. To repeat the question: q) Why not have both iterators and ranges? The answer was given earlier in the talk.. a) Iterators are fundamentally unsafe. btw.. the birds chirping throughout made me really want to go to boostcon. That it's set in such a wonderful location (Aspen) is a major selling point. Later, Brad
Re: Iterators Must Go video online
Andrei Alexandrescu wrote: A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ On reddit, too! http://www.reddit.com/r/programming/comments/976aj/iterators_must_go_presentation_by_andrei/
Iterators Must Go video online
A while ago I mentioned the video of my BoostCon keynote "Iterators Must Go" will be soon available online. Here it is: http://boostcon.blip.tv/ Andrei
Re: Iterators Must Go video to come online soon
Andrei Alexandrescu wrote: BCS wrote: Is there going to be a midnight release party? Rats, I almost forgot. I arranged with an old friend to hold a little party in conjunction to his. http://tinyurl.com/qgdolk Aww, geezz, the man must really be out of cash! P.S. In fact I'm only half kidding. According to the fellas on fatwallet.com that's a good deal. Sure, if you make a habit of partying below your standing.
Re: Iterators Must Go video to come online soon
BCS wrote: Is there going to be a midnight release party? Rats, I almost forgot. I arranged with an old friend to hold a little party in conjunction to his. http://tinyurl.com/qgdolk Andrei P.S. In fact I'm only half kidding. According to the fellas on fatwallet.com that's a good deal.
Re: Iterators Must Go video to come online soon
Reply to Tim, On Fri, 22 May 2009 06:16:28 +1200, Andrei Alexandrescu wrote: Denis Koroskin wrote: On Thu, 21 May 2009 21:43:07 +0400, Tim Matthews wrote: On Fri, 22 May 2009 05:28:30 +1200, Walter Bright wrote: Jeremie Pelletier wrote: Walter Bright Wrote: Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! And the Alternate Ending! Do you have a list of the cast? Is there a trailer? Will it be suitable for younger audience or what is the rating? I've heard it is nominated for Oscars for best picture, scenario, actor performance and directing. Now I regret having posted the info, once because of the over-expectation, and then because the folks seem to take their time putting the thing online. I thought I'll see it when I woke up this morning. Andrei Even if the movie isn't that good I will still be able to get my hands on the merchandise including the offical McD and BK toys won't I? Is there going to be a midnight release party?
Re: Iterators Must Go video to come online soon
On Fri, 22 May 2009 06:16:28 +1200, Andrei Alexandrescu wrote: Denis Koroskin wrote: On Thu, 21 May 2009 21:43:07 +0400, Tim Matthews wrote: On Fri, 22 May 2009 05:28:30 +1200, Walter Bright wrote: Jeremie Pelletier wrote: Walter Bright Wrote: Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! And the Alternate Ending! Do you have a list of the cast? Is there a trailer? Will it be suitable for younger audience or what is the rating? I've heard it is nominated for Oscars for best picture, scenario, actor performance and directing. Now I regret having posted the info, once because of the over-expectation, and then because the folks seem to take their time putting the thing online. I thought I'll see it when I woke up this morning. Andrei Even if the movie isn't that good I will still be able to get my hands on the merchandise including the offical McD and BK toys won't I?
Re: Iterators Must Go video to come online soon
Denis Koroskin wrote: On Thu, 21 May 2009 21:43:07 +0400, Tim Matthews wrote: On Fri, 22 May 2009 05:28:30 +1200, Walter Bright wrote: Jeremie Pelletier wrote: Walter Bright Wrote: Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! And the Alternate Ending! Do you have a list of the cast? Is there a trailer? Will it be suitable for younger audience or what is the rating? I've heard it is nominated for Oscars for best picture, scenario, actor performance and directing. Now I regret having posted the info, once because of the over-expectation, and then because the folks seem to take their time putting the thing online. I thought I'll see it when I woke up this morning. Andrei
Re: Iterators Must Go video to come online soon
On Thu, 21 May 2009 21:43:07 +0400, Tim Matthews wrote: > On Fri, 22 May 2009 05:28:30 +1200, Walter Bright > wrote: > >> Jeremie Pelletier wrote: >>> Walter Bright Wrote: >>> Andrei Alexandrescu wrote: > Daniel Keep wrote: >> Andrei Alexandrescu wrote: >>> Apparently the entire talk has been filmed, and the conference >>> organizers have edited the footage a bit and will make it available >>> soon. Stay tuned. >>> >>> Andrei >> Why do you taunt us so? >> >> "Coming soon: something awesome you want to see but can't yet. Just >> reminding you that you can't see it yet. Ha-ha, suckers." >> >> :( >> >> -- Daniel > I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! >>> I hope there's also a making-of! >> >> And the Alternate Ending! > > > Do you have a list of the cast? Is there a trailer? Will it be suitable > for younger audience or what is the rating? I've heard it is nominated for Oscars for best picture, scenario, actor performance and directing.
Re: Iterators Must Go video to come online soon
On Fri, 22 May 2009 05:28:30 +1200, Walter Bright wrote: Jeremie Pelletier wrote: Walter Bright Wrote: Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! And the Alternate Ending! Do you have a list of the cast? Is there a trailer? Will it be suitable for younger audience or what is the rating?
Re: Iterators Must Go video to come online soon
Jeremie Pelletier wrote: Walter Bright Wrote: Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! And the Alternate Ending!
Re: Iterators Must Go video to come online soon
Walter Bright Wrote: > Andrei Alexandrescu wrote: > > Daniel Keep wrote: > >> > >> Andrei Alexandrescu wrote: > >>> Apparently the entire talk has been filmed, and the conference > >>> organizers have edited the footage a bit and will make it available > >>> soon. Stay tuned. > >>> > >>> Andrei > >> > >> Why do you taunt us so? > >> > >> "Coming soon: something awesome you want to see but can't yet. Just > >> reminding you that you can't see it yet. Ha-ha, suckers." > >> > >> :( > >> > >> -- Daniel > > > > I just got word myself; I wasn't even being aware the talk was taped. > > I'm waiting for the "deleted scenes" extra feature! I hope there's also a making-of! Is there any overview of what was discussed available? I've never been a big fan of iterators. so something saying they must go got my interest ;)
Re: Iterators Must Go video to come online soon
Andrei Alexandrescu wrote: Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. I'm waiting for the "deleted scenes" extra feature!
Re: Iterators Must Go video to come online soon
Daniel Keep wrote: Andrei Alexandrescu wrote: Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel I just got word myself; I wasn't even being aware the talk was taped. Andrei
Re: Iterators Must Go video to come online soon
Andrei Alexandrescu wrote: > Apparently the entire talk has been filmed, and the conference > organizers have edited the footage a bit and will make it available > soon. Stay tuned. > > Andrei Why do you taunt us so? "Coming soon: something awesome you want to see but can't yet. Just reminding you that you can't see it yet. Ha-ha, suckers." :( -- Daniel
Iterators Must Go video to come online soon
Apparently the entire talk has been filmed, and the conference organizers have edited the footage a bit and will make it available soon. Stay tuned. Andrei
Re: Iterators Must Go
On Sat, 09 May 2009 22:10:22 -0400, Rainer Deyke wrote: dsimcha wrote: == Quote from Rainer Deyke ([email protected])'s article Although I like ranges, it looks to me like there are a couple of operations that would difficult to implement without iterators or some other way to specify a specific position in a range. Finding and erasing an element: list.erase(find(list.begin(), list.end(), e)); What's wrong with this? Since list owns its range representation, it can know the implementation details. For a linked list, this will probably be just a pair of pointers under the hood anyhow. In other words, it's internally still an iterator, just prettier looking. The following is semantically incorrect: r = find(list, e) list.erase(r) 'find' advances only the front of the range to the found element. Therefore 'r' is the range of all elements starting with the found element, but also including all elements after that. I would expect 'list.erase(range)' to erase all elements in the range. However, in this case I only want to erase a single element. This could still be expressed with ranges, but it would require a different function. For example: find(list, e).eraseFront() Or: list.eraseFrontOf(find(list, e)) Or: list.eraseOne(find(list, e)) Or: list.findAndErase(e) Or: list.erase(take(1, find(list, e))) I think Andrei's plans are for this last one. You can srhink a range, so use the range primitives to srhink it to a 1-element range, then call erase. Splitting a container on a position: iter = find(list.begin(), list.end(), e); do_something_with(list.begin(), iter); do_something_else_with(iter, list.end()); From what I remember from the earlier discussions, Andrei's plan is for you to be able to subrange a range. So for example, you have 2 ranges that overlap, return a range that is the intersection or complement. I don't have huge issues with that solution, but I would point out that you now are depending on the developer to ensure the ranges do in fact overlap. Of course, I could be wrong with my assumption (about Andrei's intent), maybe he has a better solution. -Steve
Re: Iterators Must Go
On Sat, 09 May 2009 12:40:34 -0400, Michel Fortin wrote: On 2009-05-09 10:45:05 -0400, "Steven Schveighoffer" said: STL iterators can be used for more than just iteration. They also serve as cursors, or pointers to specific elements. If you add the ability for them to check their own bounds, then they become as safe as ranges, and can be used as general purpose pointers for things like insertion, deletion, bi-directional traversal, things that ranges can do but are clumsy at. You still have the interchangable-with-pointer concept burned into your brain :) Think more like this: for(cursor i = begin; !i.end; i++) So basically your cursor is a range (so it knows its bounds) with an added position pointer. Basically, yes. -Steve
Re: Iterators Must Go
== Quote from Rainer Deyke ([email protected])'s article > dsimcha wrote: > > == Quote from Rainer Deyke ([email protected])'s article > >> Although I like ranges, it looks to me like there are a couple of > >> operations that would difficult to implement without iterators or some > >> other way to specify a specific position in a range. > >> Finding and erasing an element: > >> list.erase(find(list.begin(), list.end(), e)); > > > > What's wrong with this? Since list owns its range representation, it can > > know the > > implementation details. For a linked list, this will probably be just a > > pair of > > pointers under the hood anyhow. In other words, it's internally still an > > iterator, just prettier looking. > The following is semantically incorrect: > r = find(list, e) > list.erase(r) > 'find' advances only the front of the range to the found element. > Therefore 'r' is the range of all elements starting with the found > element, but also including all elements after that. > I would expect 'list.erase(range)' to erase all elements in the range. > However, in this case I only want to erase a single element. This could > still be expressed with ranges, but it would require a different > function. For example: > find(list, e).eraseFront() > Or: > list.eraseFrontOf(find(list, e)) > Or: > list.eraseOne(find(list, e)) > Or: > list.findAndErase(e) > Or: > list.erase(take(1, find(list, e))) > >> Splitting a container on a position: > >> iter = find(list.begin(), list.end(), e); > >> do_something_with(list.begin(), iter); > >> do_something_else_with(iter, list.end()); > > > > This one is legit, as far as I can tell. On the other hand, although it's > > awkward, you could do something like: > > > > Range myRange1; > > auto myRange2 = find(myRange1, e); > > struct PairOfRanges { > > Range myRange1, myRange2; > > > > auto front() { > > return myRange1.front; > > } > > > > bool empty() { > > return myRange1 == myRange2; > > } > > > > void popFront() { > > myRange1.popFront; > > } > > } > Unfortunately this falls apart if my 'do_something_with' in the above > example is 'list.erase', unless 'list.erase' can look inside a > 'PairOfRanges'. > >> Inserting into a container at a position: > >> iter = find(list.begin(), list.end(), e); > >> list.insert(iter, array.begin(), array.end()); > > > > Same as erasing. > > > >> Constructing a range from two independent position: > >> iter1 = find(list.begin(), list.end(), e1); > >> iter2 = rfind(list.begin(), list.end(), e2); > >> do_something_with(iter1, iter2); > > > > Assuming find() works by popping elements off the front of the range until > > it > > finds what it's looking for, and then returning that, and rfind() does the > > same > > thing but from the back, just do something like: > > > > Range myRange = find(list, e1); > > myRange = rfind(myRange, e2); > > do_something_with(myRange); > That works in this case, but what if the iterators (sorry, ranges) come > from different sources? You do make some good points here, but as counter points: Your examples rely on the fact that there are two iterators, a begin iterator and an end iterator. In C++, this means that testing for the end of a range/iterator/whatever must be reduced to some kind of comparison, thus exposing an implementation detail in the design. Thinking about some of the ranges I've written, I cannot picture how I would reduce testing for empty to a comparison operation without resorting to some pretty significant kludges.
Re: Iterators Must Go
dsimcha wrote: > == Quote from Rainer Deyke ([email protected])'s article >> Although I like ranges, it looks to me like there are a couple of >> operations that would difficult to implement without iterators or some >> other way to specify a specific position in a range. >> Finding and erasing an element: >> list.erase(find(list.begin(), list.end(), e)); > > What's wrong with this? Since list owns its range representation, it can > know the > implementation details. For a linked list, this will probably be just a pair > of > pointers under the hood anyhow. In other words, it's internally still an > iterator, just prettier looking. The following is semantically incorrect: r = find(list, e) list.erase(r) 'find' advances only the front of the range to the found element. Therefore 'r' is the range of all elements starting with the found element, but also including all elements after that. I would expect 'list.erase(range)' to erase all elements in the range. However, in this case I only want to erase a single element. This could still be expressed with ranges, but it would require a different function. For example: find(list, e).eraseFront() Or: list.eraseFrontOf(find(list, e)) Or: list.eraseOne(find(list, e)) Or: list.findAndErase(e) Or: list.erase(take(1, find(list, e))) >> Splitting a container on a position: >> iter = find(list.begin(), list.end(), e); >> do_something_with(list.begin(), iter); >> do_something_else_with(iter, list.end()); > > This one is legit, as far as I can tell. On the other hand, although it's > awkward, you could do something like: > > Range myRange1; > auto myRange2 = find(myRange1, e); > struct PairOfRanges { > Range myRange1, myRange2; > > auto front() { > return myRange1.front; > } > > bool empty() { > return myRange1 == myRange2; > } > > void popFront() { > myRange1.popFront; > } > } Unfortunately this falls apart if my 'do_something_with' in the above example is 'list.erase', unless 'list.erase' can look inside a 'PairOfRanges'. >> Inserting into a container at a position: >> iter = find(list.begin(), list.end(), e); >> list.insert(iter, array.begin(), array.end()); > > Same as erasing. > >> Constructing a range from two independent position: >> iter1 = find(list.begin(), list.end(), e1); >> iter2 = rfind(list.begin(), list.end(), e2); >> do_something_with(iter1, iter2); > > Assuming find() works by popping elements off the front of the range until it > finds what it's looking for, and then returning that, and rfind() does the > same > thing but from the back, just do something like: > > Range myRange = find(list, e1); > myRange = rfind(myRange, e2); > do_something_with(myRange); That works in this case, but what if the iterators (sorry, ranges) come from different sources? -- Rainer Deyke - [email protected]
Re: Iterators Must Go
== Quote from Rainer Deyke ([email protected])'s article > Although I like ranges, it looks to me like there are a couple of > operations that would difficult to implement without iterators or some > other way to specify a specific position in a range. > Finding and erasing an element: > list.erase(find(list.begin(), list.end(), e)); What's wrong with this? Since list owns its range representation, it can know the implementation details. For a linked list, this will probably be just a pair of pointers under the hood anyhow. In other words, it's internally still an iterator, just prettier looking. > Splitting a container on a position: > iter = find(list.begin(), list.end(), e); > do_something_with(list.begin(), iter); > do_something_else_with(iter, list.end()); This one is legit, as far as I can tell. On the other hand, although it's awkward, you could do something like: Range myRange1; auto myRange2 = find(myRange1, e); struct PairOfRanges { Range myRange1, myRange2; auto front() { return myRange1.front; } bool empty() { return myRange1 == myRange2; } void popFront() { myRange1.popFront; } } > Inserting into a container at a position: > iter = find(list.begin(), list.end(), e); > list.insert(iter, array.begin(), array.end()); Same as erasing. > Constructing a range from two independent position: > iter1 = find(list.begin(), list.end(), e1); > iter2 = rfind(list.begin(), list.end(), e2); > do_something_with(iter1, iter2); Assuming find() works by popping elements off the front of the range until it finds what it's looking for, and then returning that, and rfind() does the same thing but from the back, just do something like: Range myRange = find(list, e1); myRange = rfind(myRange, e2); do_something_with(myRange);
Re: Iterators Must Go
Although I like ranges, it looks to me like there are a couple of operations that would difficult to implement without iterators or some other way to specify a specific position in a range. Finding and erasing an element: list.erase(find(list.begin(), list.end(), e)); Splitting a container on a position: iter = find(list.begin(), list.end(), e); do_something_with(list.begin(), iter); do_something_else_with(iter, list.end()); Inserting into a container at a position: iter = find(list.begin(), list.end(), e); list.insert(iter, array.begin(), array.end()); Constructing a range from two independent position: iter1 = find(list.begin(), list.end(), e1); iter2 = rfind(list.begin(), list.end(), e2); do_something_with(iter1, iter2); -- Rainer Deyke - [email protected]
Re: Iterators Must Go
On 2009-05-09 18:06:48 +0200, Sean Kelly said: Walter Bright wrote: If you had an iterator that knew its beginning and end, then the whole paradigm of: for (iterator i = begin; i != end; i++) doesn't make much sense because of the redundancy. Yup. And most of the "interesting" iterators fall into this category--the one returned from begin or rbegin is the real iterator and the one returned from end or rend is just used to tell the real cursor to check whether it's at the end or not. This is why I commented on Andrei's statement that it's impossible to make an iterator for a delimited range. It's possible, the design is just unnatural. Indeed I have always argued that the unbundling of the iterator end done by C++ was a bad idea. All other languages that have iterators or generators did not make this mistake, and luckily it seems that D2 did not either. I had to argue but finally ranges have ForwardRange and the possibility to check the head with another Range I would call that (which is in my opinion the most general and useful) simply Iterator because that is what it is, and iterator which knows its end (as generators in python, iterators in Aldor, and almost all languages that want to be reasonably safe). Anyway as long as it works and for_each works on them I don't care much about the name used... Fawzi
Re: Iterators Must Go
On 2009-05-09 10:45:05 -0400, "Steven Schveighoffer" said: STL iterators can be used for more than just iteration. They also serve as cursors, or pointers to specific elements. If you add the ability for them to check their own bounds, then they become as safe as ranges, and can be used as general purpose pointers for things like insertion, deletion, bi-directional traversal, things that ranges can do but are clumsy at. You still have the interchangable-with-pointer concept burned into your brain :) Think more like this: for(cursor i = begin; !i.end; i++) So basically your cursor is a range (so it knows its bounds) with an added position pointer. -- Michel Fortin [email protected] http://michelf.com/
Re: Iterators Must Go
Walter Bright wrote: If you had an iterator that knew its beginning and end, then the whole paradigm of: for (iterator i = begin; i != end; i++) doesn't make much sense because of the redundancy. Yup. And most of the "interesting" iterators fall into this category--the one returned from begin or rbegin is the real iterator and the one returned from end or rend is just used to tell the real cursor to check whether it's at the end or not. This is why I commented on Andrei's statement that it's impossible to make an iterator for a delimited range. It's possible, the design is just unnatural.
Re: Iterators Must Go
On Sat, 09 May 2009 00:15:19 -0400, Walter Bright wrote: Steven Schveighoffer wrote: You're assuming an iterator does not know its bounds. That's right. That's the usual design, which is based on the pointer model. Pointers do not know their limits. Yes, that model is not as safe. That's not the model I'm referring to. Maybe I should call it something other than iterator. How about cursor? Or range? Nope, a range cannot go backwards or forwards at will. It can only do one or the other, shrinking one end. There are definite reasons to use containers in ways that don't involve std.algorithm, where something that has the easy ability to move back and forth N times without weird subrange operations. I'm thinking of a structure with either a pointer to the container for bounds checking, or a range and pointer combined (where the invariant is that the pointer is always within the range). I'm not saying ranges are not great, i think they are a HUGE step forward, but the statement "Iterators must be eliminated" may be too harsh. Perhaps the unchecked iterator, yes (but you may want to allow it in certain performance-critical code). If you had an iterator that knew its beginning and end, then the whole paradigm of: for (iterator i = begin; i != end; i++) doesn't make much sense because of the redundancy. STL iterators can be used for more than just iteration. They also serve as cursors, or pointers to specific elements. If you add the ability for them to check their own bounds, then they become as safe as ranges, and can be used as general purpose pointers for things like insertion, deletion, bi-directional traversal, things that ranges can do but are clumsy at. You still have the interchangable-with-pointer concept burned into your brain :) Think more like this: for(cursor i = begin; !i.end; i++) -Steve
Re: Iterators Must Go
在 Fri, 08 May 2009 11:01:20 +0800，Andrei Alexandrescu 写道: The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges. Andrei Yeah, range is the correct design. Iterators should be deprecated. -- 使用 Opera 革命性的电子邮件客户程序: http://www.opera.com/mail/
Re: Iterators Must Go
Congratulations, glad to hear it was so well received. These are very inspiring slides, helped me to understand the benefits of ranges much better. You are a very good writer, looking forward to read more of your publications on D.
Re: Iterators Must Go
Steven Schveighoffer wrote: You're assuming an iterator does not know its bounds. That's right. That's the usual design, which is based on the pointer model. Pointers do not know their limits. Maybe I should call it something other than iterator. How about cursor? Or range? There are definite reasons to use containers in ways that don't involve std.algorithm, where something that has the easy ability to move back and forth N times without weird subrange operations. I'm thinking of a structure with either a pointer to the container for bounds checking, or a range and pointer combined (where the invariant is that the pointer is always within the range). I'm not saying ranges are not great, i think they are a HUGE step forward, but the statement "Iterators must be eliminated" may be too harsh. Perhaps the unchecked iterator, yes (but you may want to allow it in certain performance-critical code). If you had an iterator that knew its beginning and end, then the whole paradigm of: for (iterator i = begin; i != end; i++) doesn't make much sense because of the redundancy.
Re: Iterators Must Go
On Fri, 08 May 2009 11:57:41 -0400, Walter Bright wrote: Steven Schveighoffer wrote: You still have not addressed the usage of iterators as general data structure pointers. As far as I can tell, ranges do not implement this. i.e. find surrounding elements of an element. With iterators: auto iter = container.find(elem); auto elembefore = iter - 1; auto elemafter = iter + 1; Assuming incrementing and decrementing an iterator is checked for out-of-bounds. The problem is that last statement - "Assuming". If the iterator is the first or the last, or if there's only 1 or 2 elements in the container, it's crash city. Iterators are *inherently* uncheckable. For finding the elemafter, it's trivial as find() returns a range from the found element to the end (and it's also trivially checkable!). For elembefore, there's a bit more work involved, probably defining a find() that returns a range backed up by one one. You're assuming an iterator does not know its bounds. Maybe I should call it something other than iterator. How about cursor? There are definite reasons to use containers in ways that don't involve std.algorithm, where something that has the easy ability to move back and forth N times without weird subrange operations. I'm thinking of a structure with either a pointer to the container for bounds checking, or a range and pointer combined (where the invariant is that the pointer is always within the range). I'm not saying ranges are not great, i think they are a HUGE step forward, but the statement "Iterators must be eliminated" may be too harsh. Perhaps the unchecked iterator, yes (but you may want to allow it in certain performance-critical code). -Steve
Re: Iterators Must Go
Steven Schveighoffer wrote: You still have not addressed the usage of iterators as general data structure pointers. As far as I can tell, ranges do not implement this. i.e. find surrounding elements of an element. With iterators: auto iter = container.find(elem); auto elembefore = iter - 1; auto elemafter = iter + 1; Assuming incrementing and decrementing an iterator is checked for out-of-bounds. The problem is that last statement - "Assuming". If the iterator is the first or the last, or if there's only 1 or 2 elements in the container, it's crash city. Iterators are *inherently* uncheckable. For finding the elemafter, it's trivial as find() returns a range from the found element to the end (and it's also trivially checkable!). For elembefore, there's a bit more work involved, probably defining a find() that returns a range backed up by one one.
Re: Iterators Must Go
Sean Kelly wrote: Great paper! The only quibble I have so far is that I think iterators can support sentinel-terminated containers, it just isn't terribly natural to do so. The things I particularly like: find_end() -- Reverse iterators are a pain in the ass. The simplicity of this is just fantastic. Chain, Zip, Stride, Radial -- 100% pure awesome. partial_sort() -- The definition of this is just ingenious. It derives naturally from the range design and yet I'd never have thought of it otherwise. Regarding iostream ranges, I'd have liked if there was a bit more about the difference in interface: put vs. push/pop. One "benefit" of stream iterators is that they use the same syntax as other iterators, so it would be good to hear why the change in syntax for ranges isn't actually a design flaw. Overall, the presentation makes a very compelling case for ranges. While it's /possible/ to do quite a lot with iterators, the truly interesting stuff is so difficult/messy that it isn't worth doing. Ranges are elegant and safe for even fancy things. Nice work.
Re: Iterators Must Go
On Thu, 07 May 2009 23:01:20 -0400, Andrei Alexandrescu wrote: The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges. A good paper. You still have not addressed the usage of iterators as general data structure pointers. As far as I can tell, ranges do not implement this. i.e. find surrounding elements of an element. With iterators: auto iter = container.find(elem); auto elembefore = iter - 1; auto elemafter = iter + 1; Assuming incrementing and decrementing an iterator is checked for out-of-bounds. -Steve
Re: Iterators Must Go
Great paper! The only quibble I have so far is that I think iterators can support sentinel-terminated containers, it just isn't terribly natural to do so.
Re: Iterators Must Go
Walter Bright wrote: http://www.reddit.com/r/programming/comments/8isiw/author_of_modern_c_design_stl_iterators_must_die/ The link reads like Andrei wants to mureder Stepanov. Good thing I read the slides. :-)
Re: Iterators Must Go
http://www.reddit.com/r/programming/comments/8isiw/author_of_modern_c_design_stl_iterators_must_die/
Re: Iterators Must Go
Andrei Alexandrescu wrote: The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges. Have you considered an article in the paper version of DrDobb's? And maybe some other publications, too. D could use this PR. (Maybe even CUJ.)
Iterators Must Go
The slides from my keynote at BoostCon 2009 (www.boostcon.com) are now available from: http://www.boostcon.com/site-media/var/sphene/sphwiki/attachment/2009/05/08/iterators-must-go.pdf The talk went so well, the urge to brag is too mighty to resist. I mean it's not everyday that several people come and tell they've literally lost sleep and focus on other talks because of thinking about ranges. Also, there was a definite feel of "before" and "after". In short, the talk has generated a great deal of interest in both D proper and in the Boost community rewriting the STL entirely in terms of ranges. Andrei
