On Sat, Jun 8, 2013 at 5:45 PM, Niko Matsakis <n...@alum.mit.edu> wrote: > On Thu, Jun 06, 2013 at 12:09:29AM -0400, Daniel Micay wrote: >> A quick terminology refresher, for those who aren't familiar with it: >> Another issue is mutability, as you can write iterators that are able to >> mutate >> containers. With internal iterators, this is easy to do with safe code. With >> external ones, it will `unsafe` and won't be easy to get right. > > Something about this assertion didn't sit right with me. It took me a > little bit, but I realized it's actually faily easy to do a mutable > external iterator. Here is an example for a binary tree, visiting in > pre-order. > > https://gist.github.com/nikomatsakis/5736715
Huh, I'm surprised by how simple it is. When I tried to do it before, it was with the old borrow checker so I guess I could have just been fighting with the old bugs/limitations. > Perhaps there are other cases that are harder? I'd be curious to know > how the efficiency of this compares with the internal iterator case; > clearly, it requires allocation where an internal iterator does not. Efficiency-wise, I don't think it should be a big deal because for up to 2^32 elements it will only need a stack depth of ~32. It could be reserving the memory in advance based on the size of the tree. The recursive version will have stack overflow checks for each level of recursion so that's not much different than the vector capacity checks. _______________________________________________ Rust-dev mailing list Rust-dev@mozilla.org https://mail.mozilla.org/listinfo/rust-dev