mozilla/rust — pull request #10214 by alexcrichton (2013-11-01 01:53:40+00:00)
Title: Implement an O(1) stack treemap move iterator

Because the move iterator contains ownership of the tree, we can destructure it
as we go (and modify the internal structure). This also allows us to make the
move iterator for a treemap invertable and exactly sized (for an enumerable
variant). Sadly, I know of no way to extend this to a normal iterator, so iter()
will still require a stack allocation for now.

Additionally, this implements the clear() method in terms of move_iter() to
force O(1) stack usage when clearing a tree. I tried to implement this in a Drop
implementation for `TreeMap` as well, but I ran into ICE problems about some
missing vtables, so I'll leave that implementation for a later date. The idea
would be that dropping a `TreeMap` requires O(1) stack space instead of O(depth)
stack space.