auto merge of #8430 : erickt/rust/cleanup-iterators, r=erickt

This PR does a bunch of cleaning up of various APIs. The major one is that it merges `Iterator` and `IteratorUtil`, and renames functions like `transform` into `map`. I also merged `DoubleEndedIterator` and `DoubleEndedIteratorUtil`, as well as I renamed various .consume* functions to .move_iter(). This helps to implement part of #7887.

22 files changed, 363 insertions, 460 deletions

diff --git a/src/libstd/at_vec.rs b/src/libstd/at_vec.rs
index 786548c0642..c948074990a 100644
--- a/src/libstd/at_vec.rs
+++ b/src/libstd/at_vec.rs
@@ -141,11 +141,11 @@ pub fn from_elem<T:Clone>(n_elts: uint, t: T) -> @[T] {
  * Creates and initializes an immutable managed vector by moving all the
  * elements from an owned vector.
  */
-pub fn to_managed_consume<T>(v: ~[T]) -> @[T] {
+pub fn to_managed_move<T>(v: ~[T]) -> @[T] {
     let mut av = @[];
     unsafe {
         raw::reserve(&mut av, v.len());
-        for x in v.consume_iter() {
+        for x in v.move_iter() {
             raw::push(&mut av, x);
         }
         av
@@ -331,12 +331,12 @@ mod test {
     }
 
     #[test]
-    fn test_to_managed_consume() {
-        assert_eq!(to_managed_consume::<int>(~[]), @[]);
-        assert_eq!(to_managed_consume(~[true]), @[true]);
-        assert_eq!(to_managed_consume(~[1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
-        assert_eq!(to_managed_consume(~[~"abc", ~"123"]), @[~"abc", ~"123"]);
-        assert_eq!(to_managed_consume(~[~[42]]), @[~[42]]);
+    fn test_to_managed_move() {
+        assert_eq!(to_managed_move::<int>(~[]), @[]);
+        assert_eq!(to_managed_move(~[true]), @[true]);
+        assert_eq!(to_managed_move(~[1, 2, 3, 4, 5]), @[1, 2, 3, 4, 5]);
+        assert_eq!(to_managed_move(~[~"abc", ~"123"]), @[~"abc", ~"123"]);
+        assert_eq!(to_managed_move(~[~[42]]), @[~[42]]);
     }
 
     #[test]
diff --git a/src/libstd/either.rs b/src/libstd/either.rs
index bb74d9b3ec4..132ebc72960 100644
--- a/src/libstd/either.rs
+++ b/src/libstd/either.rs
@@ -150,7 +150,7 @@ pub fn rights<L, R: Clone>(eithers: &[Either<L, R>]) -> ~[R] {
 pub fn partition<L, R>(eithers: ~[Either<L, R>]) -> (~[L], ~[R]) {
     let mut lefts: ~[L] = ~[];
     let mut rights: ~[R] = ~[];
-    for elt in eithers.consume_iter() {
+    for elt in eithers.move_iter() {
         match elt {
             Left(l) => lefts.push(l),
             Right(r) => rights.push(r)
diff --git a/src/libstd/hashmap.rs b/src/libstd/hashmap.rs
index 84cba254dcf..7a224776859 100644
--- a/src/libstd/hashmap.rs
+++ b/src/libstd/hashmap.rs
@@ -19,7 +19,7 @@ use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 use clone::Clone;
 use cmp::{Eq, Equiv};
 use hash::Hash;
-use iterator::{Iterator, IteratorUtil, FromIterator, Extendable};
+use iterator::{Iterator, FromIterator, Extendable};
 use iterator::{FilterMap, Chain, Repeat, Zip};
 use num;
 use option::{None, Option, Some};
@@ -159,8 +159,8 @@ impl<K:Hash + Eq,V> HashMap<K, V> {
                                   vec::from_fn(new_capacity, |_| None));
 
         self.size = 0;
-        // consume_rev_iter is more efficient
-        for bucket in old_buckets.consume_rev_iter() {
+        // move_rev_iter is more efficient
+        for bucket in old_buckets.move_rev_iter() {
             self.insert_opt_bucket(bucket);
         }
     }
@@ -470,9 +470,9 @@ impl<K: Hash + Eq, V> HashMap<K, V> {
     /// Creates a consuming iterator, that is, one that moves each key-value
     /// pair out of the map in arbitrary order. The map cannot be used after
     /// calling this.
-    pub fn consume(self) -> HashMapConsumeIterator<K, V> {
-        // `consume_rev_iter` is more efficient than `consume_iter` for vectors
-        HashMapConsumeIterator {iter: self.buckets.consume_rev_iter()}
+    pub fn move_iter(self) -> HashMapMoveIterator<K, V> {
+        // `move_rev_iter` is more efficient than `move_iter` for vectors
+        HashMapMoveIterator {iter: self.buckets.move_rev_iter()}
     }
 }
 
@@ -524,9 +524,9 @@ pub struct HashMapMutIterator<'self, K, V> {
     priv iter: vec::VecMutIterator<'self, Option<Bucket<K, V>>>,
 }
 
-/// HashMap consume iterator
-pub struct HashMapConsumeIterator<K, V> {
-    priv iter: vec::ConsumeRevIterator<Option<Bucket<K, V>>>,
+/// HashMap move iterator
+pub struct HashMapMoveIterator<K, V> {
+    priv iter: vec::MoveRevIterator<Option<Bucket<K, V>>>,
 }
 
 /// HashSet iterator
@@ -535,9 +535,9 @@ pub struct HashSetIterator<'self, K> {
     priv iter: vec::VecIterator<'self, Option<Bucket<K, ()>>>,
 }
 
-/// HashSet consume iterator
-pub struct HashSetConsumeIterator<K> {
-    priv iter: vec::ConsumeRevIterator<Option<Bucket<K, ()>>>,
+/// HashSet move iterator
+pub struct HashSetMoveIterator<K> {
+    priv iter: vec::MoveRevIterator<Option<Bucket<K, ()>>>,
 }
 
 impl<'self, K, V> Iterator<(&'self K, &'self V)> for HashMapIterator<'self, K, V> {
@@ -566,7 +566,7 @@ impl<'self, K, V> Iterator<(&'self K, &'self mut V)> for HashMapMutIterator<'sel
     }
 }
 
-impl<K, V> Iterator<(K, V)> for HashMapConsumeIterator<K, V> {
+impl<K, V> Iterator<(K, V)> for HashMapMoveIterator<K, V> {
     #[inline]
     fn next(&mut self) -> Option<(K, V)> {
         for elt in self.iter {
@@ -592,7 +592,7 @@ impl<'self, K> Iterator<&'self K> for HashSetIterator<'self, K> {
     }
 }
 
-impl<K> Iterator<K> for HashSetConsumeIterator<K> {
+impl<K> Iterator<K> for HashSetMoveIterator<K> {
     #[inline]
     fn next(&mut self) -> Option<K> {
         for elt in self.iter {
@@ -707,9 +707,9 @@ impl<T:Hash + Eq> HashSet<T> {
     /// Creates a consuming iterator, that is, one that moves each value out
     /// of the set in arbitrary order. The set cannot be used after calling
     /// this.
-    pub fn consume(self) -> HashSetConsumeIterator<T> {
-        // `consume_rev_iter` is more efficient than `consume_iter` for vectors
-        HashSetConsumeIterator {iter: self.map.buckets.consume_rev_iter()}
+    pub fn move_iter(self) -> HashSetMoveIterator<T> {
+        // `move_rev_iter` is more efficient than `move_iter` for vectors
+        HashSetMoveIterator {iter: self.map.buckets.move_rev_iter()}
     }
 
     /// Visit the values representing the difference
@@ -724,7 +724,7 @@ impl<T:Hash + Eq> HashSet<T> {
     /// Visit the values representing the symmetric difference
     pub fn symmetric_difference_iter<'a>(&'a self, other: &'a HashSet<T>)
         -> Chain<SetAlgebraIter<'a, T>, SetAlgebraIter<'a, T>> {
-        self.difference_iter(other).chain_(other.difference_iter(self))
+        self.difference_iter(other).chain(other.difference_iter(self))
     }
 
     /// Visit the values representing the intersection
@@ -740,7 +740,7 @@ impl<T:Hash + Eq> HashSet<T> {
     /// Visit the values representing the union
     pub fn union_iter<'a>(&'a self, other: &'a HashSet<T>)
         -> Chain<HashSetIterator<'a, T>, SetAlgebraIter<'a, T>> {
-        self.iter().chain_(other.difference_iter(self))
+        self.iter().chain(other.difference_iter(self))
     }
 
 }
@@ -881,7 +881,7 @@ mod test_map {
     }
 
     #[test]
-    fn test_consume() {
+    fn test_move_iter() {
         let hm = {
             let mut hm = HashMap::new();
 
@@ -891,7 +891,7 @@ mod test_map {
             hm
         };
 
-        let v = hm.consume().collect::<~[(char, int)]>();
+        let v = hm.move_iter().collect::<~[(char, int)]>();
         assert!([('a', 1), ('b', 2)] == v || [('b', 2), ('a', 1)] == v);
     }
 
@@ -977,7 +977,7 @@ mod test_map {
     fn test_from_iter() {
         let xs = ~[(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 
-        let map: HashMap<int, int> = xs.iter().transform(|&x| x).collect();
+        let map: HashMap<int, int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
             assert_eq!(map.find(&k), Some(&v));
@@ -1169,7 +1169,7 @@ mod test_set {
     fn test_from_iter() {
         let xs = ~[1, 2, 3, 4, 5, 6, 7, 8, 9];
 
-        let set: HashSet<int> = xs.iter().transform(|&x| x).collect();
+        let set: HashSet<int> = xs.iter().map(|&x| x).collect();
 
         for x in xs.iter() {
             assert!(set.contains(x));
@@ -1177,7 +1177,7 @@ mod test_set {
     }
 
     #[test]
-    fn test_consume() {
+    fn test_move_iter() {
         let hs = {
             let mut hs = HashSet::new();
 
@@ -1187,7 +1187,7 @@ mod test_set {
             hs
         };
 
-        let v = hs.consume().collect::<~[char]>();
+        let v = hs.move_iter().collect::<~[char]>();
         assert!(['a', 'b'] == v || ['b', 'a'] == v);
     }
 }
diff --git a/src/libstd/iterator.rs b/src/libstd/iterator.rs
index d10a5541e41..a7a1c0bede8 100644
--- a/src/libstd/iterator.rs
+++ b/src/libstd/iterator.rs
@@ -49,89 +49,7 @@ pub trait Iterator<A> {
     /// The common use case for the estimate is pre-allocating space to store the results.
     #[inline]
     fn size_hint(&self) -> (uint, Option<uint>) { (0, None) }
-}
-
-/// A range iterator able to yield elements from both ends
-pub trait DoubleEndedIterator<A>: Iterator<A> {
-    /// Yield an element from the end of the range, returning `None` if the range is empty.
-    fn next_back(&mut self) -> Option<A>;
-}
-
-/// An object implementing random access indexing by `uint`
-///
-/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
-pub trait RandomAccessIterator<A>: Iterator<A> {
-    /// Return the number of indexable elements. At most `std::uint::max_value`
-    /// elements are indexable, even if the iterator represents a longer range.
-    fn indexable(&self) -> uint;
-
-    /// Return an element at an index
-    fn idx(&self, index: uint) -> Option<A>;
-}
-
-/// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
-///
-/// In the future these will be default methods instead of a utility trait.
-pub trait DoubleEndedIteratorUtil {
-    /// Flip the direction of the iterator
-    fn invert(self) -> Invert<Self>;
-}
-
-/// Iterator adaptors provided for every `DoubleEndedIterator` implementation.
-///
-/// In the future these will be default methods instead of a utility trait.
-impl<A, T: DoubleEndedIterator<A>> DoubleEndedIteratorUtil for T {
-    /// Flip the direction of the iterator
-    ///
-    /// The inverted iterator flips the ends on an iterator that can already
-    /// be iterated from the front and from the back.
-    ///
-    ///
-    /// If the iterator also implements RandomAccessIterator, the inverted
-    /// iterator is also random access, with the indices starting at the back
-    /// of the original iterator.
-    ///
-    /// Note: Random access with inverted indices still only applies to the first
-    /// `uint::max_value` elements of the original iterator.
-    #[inline]
-    fn invert(self) -> Invert<T> {
-        Invert{iter: self}
-    }
-}
-
-/// An double-ended iterator with the direction inverted
-#[deriving(Clone)]
-pub struct Invert<T> {
-    priv iter: T
-}
 
-impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
-    #[inline]
-    fn next(&mut self) -> Option<A> { self.iter.next_back() }
-    #[inline]
-    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
-}
-
-impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
-    #[inline]
-    fn next_back(&mut self) -> Option<A> { self.iter.next() }
-}
-
-impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
-    for Invert<T> {
-    #[inline]
-    fn indexable(&self) -> uint { self.iter.indexable() }
-    #[inline]
-    fn idx(&self, index: uint) -> Option<A> {
-        self.iter.idx(self.indexable() - index - 1)
-    }
-}
-
-/// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
-/// implementations of the `Iterator` trait.
-///
-/// In the future these will be default methods instead of a utility trait.
-pub trait IteratorUtil<A> {
     /// Chain this iterator with another, returning a new iterator which will
     /// finish iterating over the current iterator, and then it will iterate
     /// over the other specified iterator.
@@ -141,12 +59,15 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     /// let a = [0];
     /// let b = [1];
-    /// let mut it = a.iter().chain_(b.iter());
+    /// let mut it = a.iter().chain(b.iter());
     /// assert_eq!(it.next().get(), &0);
     /// assert_eq!(it.next().get(), &1);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn chain_<U: Iterator<A>>(self, other: U) -> Chain<Self, U>;
+    #[inline]
+    fn chain<U: Iterator<A>>(self, other: U) -> Chain<Self, U> {
+        Chain{a: self, b: other, flag: false}
+    }
 
     /// Creates an iterator which iterates over both this and the specified
     /// iterators simultaneously, yielding the two elements as pairs. When
@@ -162,9 +83,11 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), (&0, &1));
     /// assert!(it.next().is_none());
     /// ~~~
-    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U>;
+    #[inline]
+    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<Self, U> {
+        Zip{a: self, b: other}
+    }
 
-    // FIXME: #5898: should be called map
     /// Creates a new iterator which will apply the specified function to each
     /// element returned by the first, yielding the mapped element instead.
     ///
@@ -172,12 +95,15 @@ pub trait IteratorUtil<A> {
     ///
     /// ~~~ {.rust}
     /// let a = [1, 2];
-    /// let mut it = a.iter().transform(|&x| 2 * x);
+    /// let mut it = a.iter().map(|&x| 2 * x);
     /// assert_eq!(it.next().get(), 2);
     /// assert_eq!(it.next().get(), 4);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self>;
+    #[inline]
+    fn map<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, Self> {
+        Map{iter: self, f: f}
+    }
 
     /// Creates an iterator which applies the predicate to each element returned
     /// by this iterator. Only elements which have the predicate evaluate to
@@ -191,7 +117,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &2);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self>;
+    #[inline]
+    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, Self> {
+        Filter{iter: self, predicate: predicate}
+    }
 
     /// Creates an iterator which both filters and maps elements.
     /// If the specified function returns None, the element is skipped.
@@ -205,7 +134,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), 4);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn filter_map<'r,  B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, Self>;
+    #[inline]
+    fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, Self> {
+        FilterMap { iter: self, f: f }
+    }
 
     /// Creates an iterator which yields a pair of the value returned by this
     /// iterator plus the current index of iteration.
@@ -219,7 +151,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), (1, &200));
     /// assert!(it.next().is_none());
     /// ~~~
-    fn enumerate(self) -> Enumerate<Self>;
+    #[inline]
+    fn enumerate(self) -> Enumerate<Self> {
+        Enumerate{iter: self, count: 0}
+    }
 
     /// Creates an iterator which invokes the predicate on elements until it
     /// returns false. Once the predicate returns false, all further elements are
@@ -235,7 +170,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &1);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self>;
+    #[inline]
+    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, Self> {
+        SkipWhile{iter: self, flag: false, predicate: predicate}
+    }
 
     /// Creates an iterator which yields elements so long as the predicate
     /// returns true. After the predicate returns false for the first time, no
@@ -250,7 +188,10 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &2);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self>;
+    #[inline]
+    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, Self> {
+        TakeWhile{iter: self, flag: false, predicate: predicate}
+    }
 
     /// Creates an iterator which skips the first `n` elements of this iterator,
     /// and then it yields all further items.
@@ -264,9 +205,11 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), &5);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn skip(self, n: uint) -> Skip<Self>;
+    #[inline]
+    fn skip(self, n: uint) -> Skip<Self> {
+        Skip{iter: self, n: n}
+    }
 
-    // FIXME: #5898: should be called take
     /// Creates an iterator which yields the first `n` elements of this
     /// iterator, and then it will always return None.
     ///
@@ -274,13 +217,16 @@ pub trait IteratorUtil<A> {
     ///
     /// ~~~ {.rust}
     /// let a = [1, 2, 3, 4, 5];
-    /// let mut it = a.iter().take_(3);
+    /// let mut it = a.iter().take(3);
     /// assert_eq!(it.next().get(), &1);
     /// assert_eq!(it.next().get(), &2);
     /// assert_eq!(it.next().get(), &3);
     /// assert!(it.next().is_none());
     /// ~~~
-    fn take_(self, n: uint) -> Take<Self>;
+    #[inline]
+    fn take(self, n: uint) -> Take<Self> {
+        Take{iter: self, n: n}
+    }
 
     /// Creates a new iterator which behaves in a similar fashion to foldl.
     /// There is a state which is passed between each iteration and can be
@@ -302,8 +248,11 @@ pub trait IteratorUtil<A> {
     /// assert_eq!(it.next().get(), 120);
     /// assert!(it.next().is_none());
     /// ~~~
+    #[inline]
     fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
-        -> Scan<'r, A, B, Self, St>;
+        -> Scan<'r, A, B, Self, St> {
+        Scan{iter: self, f: f, state: initial_state}
+    }
 
     /// Creates an iterator that maps each element to an iterator,
     /// and yields the elements of the produced iterators
@@ -313,7 +262,7 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     /// let xs = [2u, 3];
     /// let ys = [0u, 1, 0, 1, 2];
-    /// let mut it = xs.iter().flat_map_(|&x| count(0u, 1).take_(x));
+    /// let mut it = xs.iter().flat_map(|&x| count(0u, 1).take(x));
     /// // Check that `it` has the same elements as `ys`
     /// let mut i = 0;
     /// for x: uint in it {
@@ -321,9 +270,11 @@ pub trait IteratorUtil<A> {
     ///     i += 1;
     /// }
     /// ~~~
-    // FIXME: #5898: should be called `flat_map`
-    fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
-        -> FlatMap<'r, A, Self, U>;
+    #[inline]
+    fn flat_map<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
+        -> FlatMap<'r, A, Self, U> {
+        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
+    }
 
     /// Creates an iterator that calls a function with a reference to each
     /// element before yielding it. This is often useful for debugging an
@@ -334,15 +285,17 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     ///let xs = [1u, 4, 2, 3, 8, 9, 6];
     ///let sum = xs.iter()
-    ///            .transform(|&x| x)
-    ///            .peek_(|&x| debug!("filtering %u", x))
+    ///            .map(|&x| x)
+    ///            .peek(|&x| debug!("filtering %u", x))
     ///            .filter(|&x| x % 2 == 0)
-    ///            .peek_(|&x| debug!("%u made it through", x))
+    ///            .peek(|&x| debug!("%u made it through", x))
     ///            .sum();
     ///println(sum.to_str());
     /// ~~~
-    // FIXME: #5898: should be called `peek`
-    fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, Self>;
+    #[inline]
+    fn peek<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, Self> {
+        Peek{iter: self, f: f}
+    }
 
     /// An adaptation of an external iterator to the for-loop protocol of rust.
     ///
@@ -355,7 +308,17 @@ pub trait IteratorUtil<A> {
     ///     printfln!("%d", i);
     /// }
     /// ~~~
-    fn advance(&mut self, f: &fn(A) -> bool) -> bool;
+    #[inline]
+    fn advance(&mut self, f: &fn(A) -> bool) -> bool {
+        loop {
+            match self.next() {
+                Some(x) => {
+                    if !f(x) { return false; }
+                }
+                None => { return true; }
+            }
+        }
+    }
 
     /// Loops through the entire iterator, collecting all of the elements into
     /// a container implementing `FromIterator`.
@@ -364,10 +327,13 @@ pub trait IteratorUtil<A> {
     ///
     /// ~~~ {.rust}
     /// let a = [1, 2, 3, 4, 5];
-    /// let b: ~[int] = a.iter().transform(|&x| x).collect();
+    /// let b: ~[int] = a.iter().map(|&x| x).collect();
     /// assert!(a == b);
     /// ~~~
-    fn collect<B: FromIterator<A, Self>>(&mut self) -> B;
+    #[inline]
+    fn collect<B: FromIterator<A, Self>>(&mut self) -> B {
+        FromIterator::from_iterator(self)
+    }
 
     /// Loops through the entire iterator, collecting all of the elements into
     /// a unique vector. This is simply collect() specialized for vectors.
@@ -376,10 +342,13 @@ pub trait IteratorUtil<A> {
     ///
     /// ~~~ {.rust}
     /// let a = [1, 2, 3, 4, 5];
-    /// let b: ~[int] = a.iter().transform(|&x| x).to_owned_vec();
+    /// let b: ~[int] = a.iter().map(|&x| x).to_owned_vec();
     /// assert!(a == b);
     /// ~~~
-    fn to_owned_vec(&mut self) -> ~[A];
+    #[inline]
+    fn to_owned_vec(&mut self) -> ~[A] {
+        self.collect()
+    }
 
     /// Loops through `n` iterations, returning the `n`th element of the
     /// iterator.
@@ -392,7 +361,16 @@ pub trait IteratorUtil<A> {
     /// assert!(it.nth(2).get() == &3);
     /// assert!(it.nth(2) == None);
     /// ~~~
-    fn nth(&mut self, n: uint) -> Option<A>;
+    #[inline]
+    fn nth(&mut self, mut n: uint) -> Option<A> {
+        loop {
+            match self.next() {
+                Some(x) => if n == 0 { return Some(x) },
+                None => return None
+            }
+            n -= 1;
+        }
+    }
 
     /// Loops through the entire iterator, returning the last element of the
     /// iterator.
@@ -403,8 +381,12 @@ pub trait IteratorUtil<A> {
     /// let a = [1, 2, 3, 4, 5];
     /// assert!(a.iter().last().get() == &5);
     /// ~~~
-    // FIXME: #5898: should be called `last`
-    fn last_(&mut self) -> Option<A>;
+    #[inline]
+    fn last(&mut self) -> Option<A> {
+        let mut last = None;
+        for x in *self { last = Some(x); }
+        last
+    }
 
     /// Performs a fold operation over the entire iterator, returning the
     /// eventual state at the end of the iteration.
@@ -415,9 +397,18 @@ pub trait IteratorUtil<A> {
     /// let a = [1, 2, 3, 4, 5];
     /// assert!(a.iter().fold(0, |a, &b| a + b) == 15);
     /// ~~~
-    fn fold<B>(&mut self, start: B, f: &fn(B, A) -> B) -> B;
+    #[inline]
+    fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
+        let mut accum = init;
+        loop {
+            match self.next() {
+                Some(x) => { accum = f(accum, x); }
+                None    => { break; }
+            }
+        }
+        accum
+    }
 
-    // FIXME: #5898: should be called len
     /// Counts the number of elements in this iterator.
     ///
     /// # Example
@@ -425,10 +416,13 @@ pub trait IteratorUtil<A> {
     /// ~~~ {.rust}
     /// let a = [1, 2, 3, 4, 5];
     /// let mut it = a.iter();
-    /// assert!(it.len_() == 5);
-    /// assert!(it.len_() == 0);
+    /// assert!(it.len() == 5);
+    /// assert!(it.len() == 0);
     /// ~~~
-    fn len_(&mut self) -> uint;
+    #[inline]
+    fn len(&mut self) -> uint {
+        self.fold(0, |cnt, _x| cnt + 1)
+    }
 
     /// Tests whether the predicate holds true for all elements in the iterator.
     ///
@@ -439,7 +433,11 @@ pub trait IteratorUtil<A> {
     /// assert!(a.iter().all(|&x| *x > 0));
     /// assert!(!a.iter().all(|&x| *x > 2));
     /// ~~~
-    fn all(&mut self, f: &fn(A) -> bool) -> bool;
+    #[inline]
+    fn all(&mut self, f: &fn(A) -> bool) -> bool {
+        for x in *self { if !f(x) { return false; } }
+        true
+    }
 
     /// Tests whether any element of an iterator satisfies the specified
     /// predicate.
@@ -452,179 +450,6 @@ pub trait IteratorUtil<A> {
     /// assert!(it.any(|&x| *x == 3));
     /// assert!(!it.any(|&x| *x == 3));
     /// ~~~
-    fn any(&mut self, f: &fn(A) -> bool) -> bool;
-
-    /// Return the first element satisfying the specified predicate
-    fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A>;
-
-    /// Return the index of the first element satisfying the specified predicate
-    fn position(&mut self, predicate: &fn(A) -> bool) -> Option<uint>;
-
-    /// Count the number of elements satisfying the specified predicate
-    fn count(&mut self, predicate: &fn(A) -> bool) -> uint;
-
-    /// Return the element that gives the maximum value from the specfied function
-    ///
-    /// # Example
-    ///
-    /// ~~~ {.rust}
-    /// let xs = [-3, 0, 1, 5, -10];
-    /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
-    /// ~~~
-    fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
-
-    /// Return the element that gives the minimum value from the specfied function
-    ///
-    /// # Example
-    ///
-    /// ~~~ {.rust}
-    /// let xs = [-3, 0, 1, 5, -10];
-    /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
-    /// ~~~
-    fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A>;
-}
-
-/// Iterator adaptors provided for every `Iterator` implementation. The adaptor objects are also
-/// implementations of the `Iterator` trait.
-///
-/// In the future these will be default methods instead of a utility trait.
-impl<A, T: Iterator<A>> IteratorUtil<A> for T {
-    #[inline]
-    fn chain_<U: Iterator<A>>(self, other: U) -> Chain<T, U> {
-        Chain{a: self, b: other, flag: false}
-    }
-
-    #[inline]
-    fn zip<B, U: Iterator<B>>(self, other: U) -> Zip<T, U> {
-        Zip{a: self, b: other}
-    }
-
-    // FIXME: #5898: should be called map
-    #[inline]
-    fn transform<'r, B>(self, f: &'r fn(A) -> B) -> Map<'r, A, B, T> {
-        Map{iter: self, f: f}
-    }
-
-    #[inline]
-    fn filter<'r>(self, predicate: &'r fn(&A) -> bool) -> Filter<'r, A, T> {
-        Filter{iter: self, predicate: predicate}
-    }
-
-    #[inline]
-    fn filter_map<'r, B>(self, f: &'r fn(A) -> Option<B>) -> FilterMap<'r, A, B, T> {
-        FilterMap { iter: self, f: f }
-    }
-
-    #[inline]
-    fn enumerate(self) -> Enumerate<T> {
-        Enumerate{iter: self, count: 0}
-    }
-
-    #[inline]
-    fn skip_while<'r>(self, predicate: &'r fn(&A) -> bool) -> SkipWhile<'r, A, T> {
-        SkipWhile{iter: self, flag: false, predicate: predicate}
-    }
-
-    #[inline]
-    fn take_while<'r>(self, predicate: &'r fn(&A) -> bool) -> TakeWhile<'r, A, T> {
-        TakeWhile{iter: self, flag: false, predicate: predicate}
-    }
-
-    #[inline]
-    fn skip(self, n: uint) -> Skip<T> {
-        Skip{iter: self, n: n}
-    }
-
-    // FIXME: #5898: should be called take
-    #[inline]
-    fn take_(self, n: uint) -> Take<T> {
-        Take{iter: self, n: n}
-    }
-
-    #[inline]
-    fn scan<'r, St, B>(self, initial_state: St, f: &'r fn(&mut St, A) -> Option<B>)
-        -> Scan<'r, A, B, T, St> {
-        Scan{iter: self, f: f, state: initial_state}
-    }
-
-    #[inline]
-    fn flat_map_<'r, B, U: Iterator<B>>(self, f: &'r fn(A) -> U)
-        -> FlatMap<'r, A, T, U> {
-        FlatMap{iter: self, f: f, frontiter: None, backiter: None }
-    }
-
-    // FIXME: #5898: should be called `peek`
-    #[inline]
-    fn peek_<'r>(self, f: &'r fn(&A)) -> Peek<'r, A, T> {
-        Peek{iter: self, f: f}
-    }
-
-    /// A shim implementing the `for` loop iteration protocol for iterator objects
-    #[inline]
-    fn advance(&mut self, f: &fn(A) -> bool) -> bool {
-        loop {
-            match self.next() {
-                Some(x) => {
-                    if !f(x) { return false; }
-                }
-                None => { return true; }
-            }
-        }
-    }
-
-    #[inline]
-    fn collect<B: FromIterator<A, T>>(&mut self) -> B {
-        FromIterator::from_iterator(self)
-    }
-
-    #[inline]
-    fn to_owned_vec(&mut self) -> ~[A] {
-        self.collect()
-    }
-
-    /// Return the `n`th item yielded by an iterator.
-    #[inline]
-    fn nth(&mut self, mut n: uint) -> Option<A> {
-        loop {
-            match self.next() {
-                Some(x) => if n == 0 { return Some(x) },
-                None => return None
-            }
-            n -= 1;
-        }
-    }
-
-    /// Return the last item yielded by an iterator.
-    #[inline]
-    fn last_(&mut self) -> Option<A> {
-        let mut last = None;
-        for x in *self { last = Some(x); }
-        last
-    }
-
-    /// Reduce an iterator to an accumulated value
-    #[inline]
-    fn fold<B>(&mut self, init: B, f: &fn(B, A) -> B) -> B {
-        let mut accum = init;
-        loop {
-            match self.next() {
-                Some(x) => { accum = f(accum, x); }
-                None    => { break; }
-            }
-        }
-        accum
-    }
-
-    /// Count the number of items yielded by an iterator
-    #[inline]
-    fn len_(&mut self) -> uint { self.fold(0, |cnt, _x| cnt + 1) }
-
-    #[inline]
-    fn all(&mut self, f: &fn(A) -> bool) -> bool {
-        for x in *self { if !f(x) { return false; } }
-        true
-    }
-
     #[inline]
     fn any(&mut self, f: &fn(A) -> bool) -> bool {
         for x in *self { if f(x) { return true; } }
@@ -633,7 +458,7 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
 
     /// Return the first element satisfying the specified predicate
     #[inline]
-    fn find_(&mut self, predicate: &fn(&A) -> bool) -> Option<A> {
+    fn find(&mut self, predicate: &fn(&A) -> bool) -> Option<A> {
         for x in *self {
             if predicate(&x) { return Some(x) }
         }
@@ -653,6 +478,7 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         None
     }
 
+    /// Count the number of elements satisfying the specified predicate
     #[inline]
     fn count(&mut self, predicate: &fn(A) -> bool) -> uint {
         let mut i = 0;
@@ -662,6 +488,14 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         i
     }
 
+    /// Return the element that gives the maximum value from the specfied function
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let xs = [-3, 0, 1, 5, -10];
+    /// assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
+    /// ~~~
     #[inline]
     fn max_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
         self.fold(None, |max: Option<(A, B)>, x| {
@@ -677,6 +511,14 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
         }).map_move(|(x, _)| x)
     }
 
+    /// Return the element that gives the minimum value from the specfied function
+    ///
+    /// # Example
+    ///
+    /// ~~~ {.rust}
+    /// let xs = [-3, 0, 1, 5, -10];
+    /// assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
+    /// ~~~
     #[inline]
     fn min_by<B: Ord>(&mut self, f: &fn(&A) -> B) -> Option<A> {
         self.fold(None, |min: Option<(A, B)>, x| {
@@ -693,6 +535,69 @@ impl<A, T: Iterator<A>> IteratorUtil<A> for T {
     }
 }
 
+/// A range iterator able to yield elements from both ends
+pub trait DoubleEndedIterator<A>: Iterator<A> {
+    /// Yield an element from the end of the range, returning `None` if the range is empty.
+    fn next_back(&mut self) -> Option<A>;
+
+    /// Flip the direction of the iterator
+    ///
+    /// The inverted iterator flips the ends on an iterator that can already
+    /// be iterated from the front and from the back.
+    ///
+    ///
+    /// If the iterator also implements RandomAccessIterator, the inverted
+    /// iterator is also random access, with the indices starting at the back
+    /// of the original iterator.
+    ///
+    /// Note: Random access with inverted indices still only applies to the first
+    /// `uint::max_value` elements of the original iterator.
+    #[inline]
+    fn invert(self) -> Invert<Self> {
+        Invert{iter: self}
+    }
+}
+
+/// An object implementing random access indexing by `uint`
+///
+/// A `RandomAccessIterator` should be either infinite or a `DoubleEndedIterator`.
+pub trait RandomAccessIterator<A>: Iterator<A> {
+    /// Return the number of indexable elements. At most `std::uint::max_value`
+    /// elements are indexable, even if the iterator represents a longer range.
+    fn indexable(&self) -> uint;
+
+    /// Return an element at an index
+    fn idx(&self, index: uint) -> Option<A>;
+}
+
+/// An double-ended iterator with the direction inverted
+#[deriving(Clone)]
+pub struct Invert<T> {
+    priv iter: T
+}
+
+impl<A, T: DoubleEndedIterator<A>> Iterator<A> for Invert<T> {
+    #[inline]
+    fn next(&mut self) -> Option<A> { self.iter.next_back() }
+    #[inline]
+    fn size_hint(&self) -> (uint, Option<uint>) { self.iter.size_hint() }
+}
+
+impl<A, T: DoubleEndedIterator<A>> DoubleEndedIterator<A> for Invert<T> {
+    #[inline]
+    fn next_back(&mut self) -> Option<A> { self.iter.next() }
+}
+
+impl<A, T: DoubleEndedIterator<A> + RandomAccessIterator<A>> RandomAccessIterator<A>
+    for Invert<T> {
+    #[inline]
+    fn indexable(&self) -> uint { self.iter.indexable() }
+    #[inline]
+    fn idx(&self, index: uint) -> Option<A> {
+        self.iter.idx(self.indexable() - index - 1)
+    }
+}
+
 /// A trait for iterators over elements which can be added together
 pub trait AdditiveIterator<A> {
     /// Iterates over the entire iterator, summing up all the elements
@@ -701,7 +606,7 @@ pub trait AdditiveIterator<A> {
     ///
     /// ~~~ {.rust}
     /// let a = [1, 2, 3, 4, 5];
-    /// let mut it = a.iter().transform(|&x| x);
+    /// let mut it = a.iter().map(|&x| x);
     /// assert!(it.sum() == 15);
     /// ~~~
     fn sum(&mut self) -> A;
@@ -790,7 +695,7 @@ pub trait ClonableIterator {
     /// # Example
     ///
     /// ~~~ {.rust}
-    /// let a = count(1,1).take_(1);
+    /// let a = count(1,1).take(1);
     /// let mut cy = a.cycle();
     /// assert_eq!(cy.next(), Some(1));
     /// assert_eq!(cy.next(), Some(1));
@@ -1617,7 +1522,7 @@ mod tests {
 
     #[test]
     fn test_counter_from_iter() {
-        let mut it = count(0, 5).take_(10);
+        let mut it = count(0, 5).take(10);
         let xs: ~[int] = FromIterator::from_iterator(&mut it);
         assert_eq!(xs, ~[0, 5, 10, 15, 20, 25, 30, 35, 40, 45]);
     }
@@ -1627,7 +1532,7 @@ mod tests {
         let xs = [0u, 1, 2, 3, 4, 5];
         let ys = [30u, 40, 50, 60];
         let expected = [0, 1, 2, 3, 4, 5, 30, 40, 50, 60];
-        let mut it = xs.iter().chain_(ys.iter());
+        let mut it = xs.iter().chain(ys.iter());
         let mut i = 0;
         for &x in it {
             assert_eq!(x, expected[i]);
@@ -1635,8 +1540,8 @@ mod tests {
         }
         assert_eq!(i, expected.len());
 
-        let ys = count(30u, 10).take_(4);
-        let mut it = xs.iter().transform(|&x| x).chain_(ys);
+        let ys = count(30u, 10).take(4);
+        let mut it = xs.iter().map(|&x| x).chain(ys);
         let mut i = 0;
         for x in it {
             assert_eq!(x, expected[i]);
@@ -1647,7 +1552,7 @@ mod tests {
 
     #[test]
     fn test_filter_map() {
-        let mut it = count(0u, 1u).take_(10)
+        let mut it = count(0u, 1u).take(10)
             .filter_map(|x| if x.is_even() { Some(x*x) } else { None });
         assert_eq!(it.collect::<~[uint]>(), ~[0*0, 2*2, 4*4, 6*6, 8*8]);
     }
@@ -1704,7 +1609,7 @@ mod tests {
     fn test_iterator_take() {
         let xs = [0u, 1, 2, 3, 5, 13, 15, 16, 17, 19];
         let ys = [0u, 1, 2, 3, 5];
-        let mut it = xs.iter().take_(5);
+        let mut it = xs.iter().take(5);
         let mut i = 0;
         for &x in it {
             assert_eq!(x, ys[i]);
@@ -1736,7 +1641,7 @@ mod tests {
     fn test_iterator_flat_map() {
         let xs = [0u, 3, 6];
         let ys = [0u, 1, 2, 3, 4, 5, 6, 7, 8];
-        let mut it = xs.iter().flat_map_(|&x| count(x, 1).take_(3));
+        let mut it = xs.iter().flat_map(|&x| count(x, 1).take(3));
         let mut i = 0;
         for x in it {
             assert_eq!(x, ys[i]);
@@ -1751,8 +1656,8 @@ mod tests {
         let mut n = 0;
 
         let ys = xs.iter()
-                   .transform(|&x| x)
-                   .peek_(|_| n += 1)
+                   .map(|&x| x)
+                   .peek(|_| n += 1)
                    .collect::<~[uint]>();
 
         assert_eq!(n, xs.len());
@@ -1783,13 +1688,13 @@ mod tests {
     #[test]
     fn test_cycle() {
         let cycle_len = 3;
-        let it = count(0u, 1).take_(cycle_len).cycle();
+        let it = count(0u, 1).take(cycle_len).cycle();
         assert_eq!(it.size_hint(), (uint::max_value, None));
-        for (i, x) in it.take_(100).enumerate() {
+        for (i, x) in it.take(100).enumerate() {
             assert_eq!(i % cycle_len, x);
         }
 
-        let mut it = count(0u, 1).take_(0).cycle();
+        let mut it = count(0u, 1).take(0).cycle();
         assert_eq!(it.size_hint(), (0, Some(0)));
         assert_eq!(it.next(), None);
     }
@@ -1805,48 +1710,48 @@ mod tests {
     #[test]
     fn test_iterator_last() {
         let v = &[0, 1, 2, 3, 4];
-        assert_eq!(v.iter().last_().unwrap(), &4);
-        assert_eq!(v.slice(0, 1).iter().last_().unwrap(), &0);
+        assert_eq!(v.iter().last().unwrap(), &4);
+        assert_eq!(v.slice(0, 1).iter().last().unwrap(), &0);
     }
 
     #[test]
     fn test_iterator_len() {
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-        assert_eq!(v.slice(0, 4).iter().len_(), 4);
-        assert_eq!(v.slice(0, 10).iter().len_(), 10);
-        assert_eq!(v.slice(0, 0).iter().len_(), 0);
+        assert_eq!(v.slice(0, 4).iter().len(), 4);
+        assert_eq!(v.slice(0, 10).iter().len(), 10);
+        assert_eq!(v.slice(0, 0).iter().len(), 0);
     }
 
     #[test]
     fn test_iterator_sum() {
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-        assert_eq!(v.slice(0, 4).iter().transform(|&x| x).sum(), 6);
-        assert_eq!(v.iter().transform(|&x| x).sum(), 55);
-        assert_eq!(v.slice(0, 0).iter().transform(|&x| x).sum(), 0);
+        assert_eq!(v.slice(0, 4).iter().map(|&x| x).sum(), 6);
+        assert_eq!(v.iter().map(|&x| x).sum(), 55);
+        assert_eq!(v.slice(0, 0).iter().map(|&x| x).sum(), 0);
     }
 
     #[test]
     fn test_iterator_product() {
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-        assert_eq!(v.slice(0, 4).iter().transform(|&x| x).product(), 0);
-        assert_eq!(v.slice(1, 5).iter().transform(|&x| x).product(), 24);
-        assert_eq!(v.slice(0, 0).iter().transform(|&x| x).product(), 1);
+        assert_eq!(v.slice(0, 4).iter().map(|&x| x).product(), 0);
+        assert_eq!(v.slice(1, 5).iter().map(|&x| x).product(), 24);
+        assert_eq!(v.slice(0, 0).iter().map(|&x| x).product(), 1);
     }
 
     #[test]
     fn test_iterator_max() {
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-        assert_eq!(v.slice(0, 4).iter().transform(|&x| x).max(), Some(3));
-        assert_eq!(v.iter().transform(|&x| x).max(), Some(10));
-        assert_eq!(v.slice(0, 0).iter().transform(|&x| x).max(), None);
+        assert_eq!(v.slice(0, 4).iter().map(|&x| x).max(), Some(3));
+        assert_eq!(v.iter().map(|&x| x).max(), Some(10));
+        assert_eq!(v.slice(0, 0).iter().map(|&x| x).max(), None);
     }
 
     #[test]
     fn test_iterator_min() {
         let v = &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
-        assert_eq!(v.slice(0, 4).iter().transform(|&x| x).min(), Some(0));
-        assert_eq!(v.iter().transform(|&x| x).min(), Some(0));
-        assert_eq!(v.slice(0, 0).iter().transform(|&x| x).min(), None);
+        assert_eq!(v.slice(0, 4).iter().map(|&x| x).min(), Some(0));
+        assert_eq!(v.iter().map(|&x| x).min(), Some(0));
+        assert_eq!(v.slice(0, 0).iter().map(|&x| x).min(), None);
     }
 
     #[test]
@@ -1859,43 +1764,43 @@ mod tests {
         assert_eq!(c.size_hint(), (uint::max_value, None));
         assert_eq!(vi.size_hint(), (10, Some(10)));
 
-        assert_eq!(c.take_(5).size_hint(), (5, Some(5)));
+        assert_eq!(c.take(5).size_hint(), (5, Some(5)));
         assert_eq!(c.skip(5).size_hint().second(), None);
         assert_eq!(c.take_while(|_| false).size_hint(), (0, None));
         assert_eq!(c.skip_while(|_| false).size_hint(), (0, None));
         assert_eq!(c.enumerate().size_hint(), (uint::max_value, None));
-        assert_eq!(c.chain_(vi.transform(|&i| i)).size_hint(), (uint::max_value, None));
+        assert_eq!(c.chain(vi.map(|&i| i)).size_hint(), (uint::max_value, None));
         assert_eq!(c.zip(vi).size_hint(), (10, Some(10)));
         assert_eq!(c.scan(0, |_,_| Some(0)).size_hint(), (0, None));
         assert_eq!(c.filter(|_| false).size_hint(), (0, None));
-        assert_eq!(c.transform(|_| 0).size_hint(), (uint::max_value, None));
+        assert_eq!(c.map(|_| 0).size_hint(), (uint::max_value, None));
         assert_eq!(c.filter_map(|_| Some(0)).size_hint(), (0, None));
 
-        assert_eq!(vi.take_(5).size_hint(), (5, Some(5)));
-        assert_eq!(vi.take_(12).size_hint(), (10, Some(10)));
+        assert_eq!(vi.take(5).size_hint(), (5, Some(5)));
+        assert_eq!(vi.take(12).size_hint(), (10, Some(10)));
         assert_eq!(vi.skip(3).size_hint(), (7, Some(7)));
         assert_eq!(vi.skip(12).size_hint(), (0, Some(0)));
         assert_eq!(vi.take_while(|_| false).size_hint(), (0, Some(10)));
         assert_eq!(vi.skip_while(|_| false).size_hint(), (0, Some(10)));
         assert_eq!(vi.enumerate().size_hint(), (10, Some(10)));
-        assert_eq!(vi.chain_(v2.iter()).size_hint(), (13, Some(13)));
+        assert_eq!(vi.chain(v2.iter()).size_hint(), (13, Some(13)));
         assert_eq!(vi.zip(v2.iter()).size_hint(), (3, Some(3)));
         assert_eq!(vi.scan(0, |_,_| Some(0)).size_hint(), (0, Some(10)));
         assert_eq!(vi.filter(|_| false).size_hint(), (0, Some(10)));
-        assert_eq!(vi.transform(|i| i+1).size_hint(), (10, Some(10)));
+        assert_eq!(vi.map(|i| i+1).size_hint(), (10, Some(10)));
         assert_eq!(vi.filter_map(|_| Some(0)).size_hint(), (0, Some(10)));
     }
 
     #[test]
     fn test_collect() {
         let a = ~[1, 2, 3, 4, 5];
-        let b: ~[int] = a.iter().transform(|&x| x).collect();
+        let b: ~[int] = a.iter().map(|&x| x).collect();
         assert_eq!(a, b);
     }
 
     #[test]
     fn test_all() {
-        let v = ~&[1, 2, 3, 4, 5];
+        let v: ~&[int] = ~&[1, 2, 3, 4, 5];
         assert!(v.iter().all(|&x| x < 10));
         assert!(!v.iter().all(|&x| x.is_even()));
         assert!(!v.iter().all(|&x| x > 100));
@@ -1904,7 +1809,7 @@ mod tests {
 
     #[test]
     fn test_any() {
-        let v = ~&[1, 2, 3, 4, 5];
+        let v: ~&[int] = ~&[1, 2, 3, 4, 5];
         assert!(v.iter().any(|&x| x < 10));
         assert!(v.iter().any(|&x| x.is_even()));
         assert!(!v.iter().any(|&x| x > 100));
@@ -1913,10 +1818,10 @@ mod tests {
 
     #[test]
     fn test_find() {
-        let v = &[1, 3, 9, 27, 103, 14, 11];
-        assert_eq!(*v.iter().find_(|x| *x & 1 == 0).unwrap(), 14);
-        assert_eq!(*v.iter().find_(|x| *x % 3 == 0).unwrap(), 3);
-        assert!(v.iter().find_(|x| *x % 12 == 0).is_none());
+        let v: &[int] = &[1, 3, 9, 27, 103, 14, 11];
+        assert_eq!(*v.iter().find(|x| *x & 1 == 0).unwrap(), 14);
+        assert_eq!(*v.iter().find(|x| *x % 3 == 0).unwrap(), 3);
+        assert!(v.iter().find(|x| *x % 12 == 0).is_none());
     }
 
     #[test]
@@ -1937,13 +1842,13 @@ mod tests {
 
     #[test]
     fn test_max_by() {
-        let xs = [-3, 0, 1, 5, -10];
+        let xs: &[int] = &[-3, 0, 1, 5, -10];
         assert_eq!(*xs.iter().max_by(|x| x.abs()).unwrap(), -10);
     }
 
     #[test]
     fn test_min_by() {
-        let xs = [-3, 0, 1, 5, -10];
+        let xs: &[int] = &[-3, 0, 1, 5, -10];
         assert_eq!(*xs.iter().min_by(|x| x.abs()).unwrap(), 0);
     }
 
@@ -1953,13 +1858,13 @@ mod tests {
         let mut it = xs.iter();
         it.next();
         it.next();
-        assert_eq!(it.invert().transform(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
+        assert_eq!(it.invert().map(|&x| x).collect::<~[int]>(), ~[16, 14, 12, 10, 8, 6]);
     }
 
     #[test]
     fn test_double_ended_map() {
         let xs = [1, 2, 3, 4, 5, 6];
-        let mut it = xs.iter().transform(|&x| x * -1);
+        let mut it = xs.iter().map(|&x| x * -1);
         assert_eq!(it.next(), Some(-1));
         assert_eq!(it.next(), Some(-2));
         assert_eq!(it.next_back(), Some(-6));
@@ -1993,7 +1898,7 @@ mod tests {
     fn test_double_ended_chain() {
         let xs = [1, 2, 3, 4, 5];
         let ys = ~[7, 9, 11];
-        let mut it = xs.iter().chain_(ys.iter()).invert();
+        let mut it = xs.iter().chain(ys.iter()).invert();
         assert_eq!(it.next().unwrap(), &11)
         assert_eq!(it.next().unwrap(), &9)
         assert_eq!(it.next_back().unwrap(), &1)
@@ -2029,7 +1934,7 @@ mod tests {
     fn test_double_ended_flat_map() {
         let u = [0u,1];
         let v = [5,6,7,8];
-        let mut it = u.iter().flat_map_(|x| v.slice(*x, v.len()).iter());
+        let mut it = u.iter().flat_map(|x| v.slice(*x, v.len()).iter());
         assert_eq!(it.next_back().unwrap(), &8);
         assert_eq!(it.next().unwrap(),      &5);
         assert_eq!(it.next_back().unwrap(), &7);
@@ -2046,7 +1951,7 @@ mod tests {
     fn test_random_access_chain() {
         let xs = [1, 2, 3, 4, 5];
         let ys = ~[7, 9, 11];
-        let mut it = xs.iter().chain_(ys.iter());
+        let mut it = xs.iter().chain(ys.iter());
         assert_eq!(it.idx(0).unwrap(), &1);
         assert_eq!(it.idx(5).unwrap(), &7);
         assert_eq!(it.idx(7).unwrap(), &11);
@@ -2091,10 +1996,10 @@ mod tests {
     fn test_random_access_take() {
         let xs = [1, 2, 3, 4, 5];
         let empty: &[int] = [];
-        check_randacc_iter(xs.iter().take_(3), 3);
-        check_randacc_iter(xs.iter().take_(20), xs.len());
-        check_randacc_iter(xs.iter().take_(0), 0);
-        check_randacc_iter(empty.iter().take_(2), 0);
+        check_randacc_iter(xs.iter().take(3), 3);
+        check_randacc_iter(xs.iter().take(20), xs.len());
+        check_randacc_iter(xs.iter().take(0), 0);
+        check_randacc_iter(empty.iter().take(2), 0);
     }
 
     #[test]
@@ -2109,8 +2014,8 @@ mod tests {
     fn test_random_access_peek() {
         let xs = [1, 2, 3, 4, 5];
 
-        // test .transform and .peek_ that don't implement Clone
-        let it = xs.iter().peek_(|_| {});
+        // test .map and .peek that don't implement Clone
+        let it = xs.iter().peek(|_| {});
         assert_eq!(xs.len(), it.indexable());
         for (i, elt) in xs.iter().enumerate() {
             assert_eq!(Some(elt), it.idx(i));
@@ -2119,11 +2024,11 @@ mod tests {
     }
 
     #[test]
-    fn test_random_access_transform() {
+    fn test_random_access_map() {
         let xs = [1, 2, 3, 4, 5];
 
-        // test .transform and .peek_ that don't implement Clone
-        let it = xs.iter().transform(|x| *x);
+        // test .map and .peek that don't implement Clone
+        let it = xs.iter().map(|x| *x);
         assert_eq!(xs.len(), it.indexable());
         for (i, elt) in xs.iter().enumerate() {
             assert_eq!(Some(*elt), it.idx(i));
@@ -2134,7 +2039,7 @@ mod tests {
     fn test_random_access_cycle() {
         let xs = [1, 2, 3, 4, 5];
         let empty: &[int] = [];
-        check_randacc_iter(xs.iter().cycle().take_(27), 27);
+        check_randacc_iter(xs.iter().cycle().take(27), 27);
         check_randacc_iter(empty.iter().cycle(), 0);
     }
 
diff --git a/src/libstd/option.rs b/src/libstd/option.rs
index 66b30d8dd03..c1999ae47d6 100644
--- a/src/libstd/option.rs
+++ b/src/libstd/option.rs
@@ -134,7 +134,7 @@ impl<T> Option<T> {
 
     /// Return a consuming iterator over the possibly contained value
     #[inline]
-    pub fn consume(self) -> OptionIterator<T> {
+    pub fn move_iter(self) -> OptionIterator<T> {
         OptionIterator{opt: self}
     }
 
diff --git a/src/libstd/os.rs b/src/libstd/os.rs
index 008d59d5376..c916be79c53 100644
--- a/src/libstd/os.rs
+++ b/src/libstd/os.rs
@@ -32,7 +32,7 @@ use c_str::ToCStr;
 use clone::Clone;
 use container::Container;
 use io;
-use iterator::{IteratorUtil, range};
+use iterator::range;
 use libc;
 use libc::{c_char, c_void, c_int, size_t};
 use libc::FILE;
@@ -765,7 +765,7 @@ pub fn list_dir(p: &Path) -> ~[~str] {
                 strings
             }
         }
-        do get_list(p).consume_iter().filter |filename| {
+        do get_list(p).move_iter().filter |filename| {
             "." != *filename && ".." != *filename
         }.collect()
     }
diff --git a/src/libstd/path.rs b/src/libstd/path.rs
index 14844e24006..177f0efb6da 100644
--- a/src/libstd/path.rs
+++ b/src/libstd/path.rs
@@ -21,7 +21,7 @@ use c_str;
 use clone::Clone;
 use cmp::Eq;
 use container::Container;
-use iterator::{Iterator, IteratorUtil, range};
+use iterator::{Iterator, range};
 use libc;
 use num;
 use option::{None, Option, Some};
@@ -961,7 +961,7 @@ impl GenericPath for WindowsPath {
         match self.filestem() {
             Some(stem) => {
                 // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
-                // to_ascii_consume and to_str_consume to not do a unnecessary copy.
+                // to_ascii_move and to_str_move to not do a unnecessary copy.
                 match stem.to_ascii().to_lower().to_str_ascii() {
                     ~"con" | ~"aux" | ~"com1" | ~"com2" | ~"com3" | ~"com4" |
                     ~"lpt1" | ~"lpt2" | ~"lpt3" | ~"prn" | ~"nul" => true,
@@ -1020,7 +1020,7 @@ impl GenericPath for WindowsPath {
                 None => None,
 
                 // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
-                // to_ascii_consume and to_str_consume to not do a unnecessary copy.
+                // to_ascii_move and to_str_move to not do a unnecessary copy.
                 Some(ref device) => Some(device.to_ascii().to_upper().to_str_ascii())
             },
             is_absolute: self.is_absolute,
diff --git a/src/libstd/prelude.rs b/src/libstd/prelude.rs
index f035e61fa1e..9a8737f4dee 100644
--- a/src/libstd/prelude.rs
+++ b/src/libstd/prelude.rs
@@ -51,7 +51,7 @@ pub use container::{Container, Mutable, Map, MutableMap, Set, MutableSet};
 pub use hash::Hash;
 pub use iter::Times;
 pub use iterator::Extendable;
-pub use iterator::{Iterator, IteratorUtil, DoubleEndedIterator, DoubleEndedIteratorUtil};
+pub use iterator::{Iterator, DoubleEndedIterator};
 pub use iterator::{ClonableIterator, OrdIterator};
 pub use num::{Num, NumCast};
 pub use num::{Orderable, Signed, Unsigned, Round};
diff --git a/src/libstd/result.rs b/src/libstd/result.rs
index 3e429c6116d..9de5e69148a 100644
--- a/src/libstd/result.rs
+++ b/src/libstd/result.rs
@@ -94,7 +94,7 @@ impl<T, E: ToStr> Result<T, E> {
         match *self {
             Ok(ref t) => Some(t),
             Err(*) => None,
-        }.consume()
+        }.move_iter()
     }
 
     /// Call a method based on a previous result
@@ -108,7 +108,7 @@ impl<T, E: ToStr> Result<T, E> {
         match *self {
             Ok(*) => None,
             Err(ref t) => Some(t),
-        }.consume()
+        }.move_iter()
     }
 
     /// Unwraps a result, yielding the content of an `Ok`.
diff --git a/src/libstd/rt/kill.rs b/src/libstd/rt/kill.rs
index e07cb1425bf..07b4ea10b6a 100644
--- a/src/libstd/rt/kill.rs
+++ b/src/libstd/rt/kill.rs
@@ -239,7 +239,7 @@ impl BlockedTask {
         };
         // Even if the task was unkillable before, we use 'Killable' because
         // multiple pipes will have handles. It does not really mean killable.
-        handles.consume_iter().transform(|x| Killable(x)).collect()
+        handles.move_iter().map(|x| Killable(x)).collect()
     }
 
     // This assertion has two flavours because the wake involves an atomic op.
diff --git a/src/libstd/rt/mod.rs b/src/libstd/rt/mod.rs
index 348345f61fc..1b9f28b95fb 100644
--- a/src/libstd/rt/mod.rs
+++ b/src/libstd/rt/mod.rs
@@ -63,7 +63,7 @@ Several modules in `core` are clients of `rt`:
 use cell::Cell;
 use clone::Clone;
 use container::Container;
-use iterator::{Iterator, IteratorUtil, range};
+use iterator::{Iterator, range};
 use option::{Some, None};
 use ptr::RawPtr;
 use rt::local::Local;
@@ -391,7 +391,7 @@ fn run_(main: ~fn(), use_main_sched: bool) -> int {
     rtdebug!("waiting for threads");
 
     // Wait for schedulers
-    for thread in threads.consume_iter() {
+    for thread in threads.move_iter() {
         thread.join();
     }
 
diff --git a/src/libstd/rt/select.rs b/src/libstd/rt/select.rs
index 0e8d26e9482..bde703af315 100644
--- a/src/libstd/rt/select.rs
+++ b/src/libstd/rt/select.rs
@@ -54,7 +54,7 @@ pub fn select<A: Select>(ports: &mut [A]) -> uint {
         let task_handles = task.make_selectable(ports.len());
 
         for (index, (port, task_handle)) in
-                ports.mut_iter().zip(task_handles.consume_iter()).enumerate() {
+                ports.mut_iter().zip(task_handles.move_iter()).enumerate() {
             // If one of the ports has data by now, it will wake the handle.
             if port.block_on(sched, task_handle) {
                 ready_index = index;
@@ -128,7 +128,7 @@ mod test {
         let (ports, chans) = unzip(from_fn(num_ports, |_| oneshot::<()>()));
         let mut dead_chans = ~[];
         let mut ports = ports;
-        for (i, chan) in chans.consume_iter().enumerate() {
+        for (i, chan) in chans.move_iter().enumerate() {
             if send_on_chans.contains(&i) {
                 chan.send(());
             } else {
@@ -145,7 +145,7 @@ mod test {
         let (ports, chans) = unzip(from_fn(num_ports, |_| stream::<()>()));
         let mut dead_chans = ~[];
         let mut ports = ports;
-        for (i, chan) in chans.consume_iter().enumerate() {
+        for (i, chan) in chans.move_iter().enumerate() {
             if send_on_chans.contains(&i) {
                 chan.send(());
             } else {
diff --git a/src/libstd/rt/test.rs b/src/libstd/rt/test.rs
index 92366d5187f..ca94468e1ad 100644
--- a/src/libstd/rt/test.rs
+++ b/src/libstd/rt/test.rs
@@ -232,7 +232,7 @@ pub fn run_in_mt_newsched_task(f: ~fn()) {
         }
 
         // Wait for schedulers
-        for thread in threads.consume_iter() {
+        for thread in threads.move_iter() {
             thread.join();
         }
     }
diff --git a/src/libstd/rt/util.rs b/src/libstd/rt/util.rs
index 40e5c8d4bf1..6280b64ecf5 100644
--- a/src/libstd/rt/util.rs
+++ b/src/libstd/rt/util.rs
@@ -10,7 +10,6 @@
 
 use container::Container;
 use from_str::FromStr;
-use iterator::IteratorUtil;
 use libc;
 use option::{Some, None};
 use os;
diff --git a/src/libstd/str.rs b/src/libstd/str.rs
index b72e5a87c6d..26a00cca4c8 100644
--- a/src/libstd/str.rs
+++ b/src/libstd/str.rs
@@ -23,9 +23,9 @@ use char::Char;
 use clone::Clone;
 use container::{Container, Mutable};
 use iter::Times;
-use iterator::{Iterator, FromIterator, Extendable, IteratorUtil};
+use iterator::{Iterator, FromIterator, Extendable};
 use iterator::{Filter, AdditiveIterator, Map};
-use iterator::{Invert, DoubleEndedIterator, DoubleEndedIteratorUtil};
+use iterator::{Invert, DoubleEndedIterator};
 use libc;
 use num::Zero;
 use option::{None, Option, Some};
@@ -59,7 +59,7 @@ pub fn from_bytes(vv: &[u8]) -> ~str {
     use str::not_utf8::cond;
 
     if !is_utf8(vv) {
-        let first_bad_byte = *vv.iter().find_(|&b| !is_utf8([*b])).unwrap();
+        let first_bad_byte = *vv.iter().find(|&b| !is_utf8([*b])).unwrap();
         cond.raise(fmt!("from_bytes: input is not UTF-8; first bad byte is %u",
                         first_bad_byte as uint))
     } else {
@@ -76,7 +76,7 @@ pub fn from_bytes_owned(vv: ~[u8]) -> ~str {
     use str::not_utf8::cond;
 
     if !is_utf8(vv) {
-        let first_bad_byte = *vv.iter().find_(|&b| !is_utf8([*b])).unwrap();
+        let first_bad_byte = *vv.iter().find(|&b| !is_utf8([*b])).unwrap();
         cond.raise(fmt!("from_bytes: input is not UTF-8; first bad byte is %u",
                         first_bad_byte as uint))
     } else {
@@ -185,7 +185,7 @@ impl<'self, S: Str> StrVector for &'self [S] {
     pub fn concat(&self) -> ~str {
         if self.is_empty() { return ~""; }
 
-        let len = self.iter().transform(|s| s.as_slice().len()).sum();
+        let len = self.iter().map(|s| s.as_slice().len()).sum();
 
         let mut s = with_capacity(len);
 
@@ -210,7 +210,7 @@ impl<'self, S: Str> StrVector for &'self [S] {
     pub fn concat(&self) -> ~str {
         if self.is_empty() { return ~""; }
 
-        let len = self.iter().transform(|s| s.as_slice().len()).sum();
+        let len = self.iter().map(|s| s.as_slice().len()).sum();
 
         let mut s = with_capacity(len);
 
@@ -239,7 +239,7 @@ impl<'self, S: Str> StrVector for &'self [S] {
 
         // this is wrong without the guarantee that `self` is non-empty
         let len = sep.len() * (self.len() - 1)
-            + self.iter().transform(|s| s.as_slice().len()).sum();
+            + self.iter().map(|s| s.as_slice().len()).sum();
         let mut s = ~"";
         let mut first = true;
 
@@ -280,7 +280,7 @@ impl<'self, S: Str> StrVector for &'self [S] {
 
         // this is wrong without the guarantee that `self` is non-empty
         let len = sep.len() * (self.len() - 1)
-            + self.iter().transform(|s| s.as_slice().len()).sum();
+            + self.iter().map(|s| s.as_slice().len()).sum();
         let mut s = ~"";
         let mut first = true;
 
@@ -1051,7 +1051,7 @@ pub mod raw {
     /// If end is greater than the length of the string.
     #[cfg(not(stage0))]
     #[inline]
-    pub unsafe fn slice_bytes(s: &str, begin: uint, end: uint) -> &str {
+    pub unsafe fn slice_bytes<'a>(s: &'a str, begin: uint, end: uint) -> &'a str {
         do s.as_imm_buf |sbuf, n| {
              assert!((begin <= end));
              assert!((end <= n));
@@ -1445,7 +1445,7 @@ impl<'self> StrSlice<'self> for &'self str {
     /// ~~~
     #[inline]
     fn iter(&self) -> CharIterator<'self> {
-        self.char_offset_iter().transform(|(_, c)| c)
+        self.char_offset_iter().map(|(_, c)| c)
     }
 
     /// An iterator over the characters of `self`, in reverse order.
@@ -1457,7 +1457,7 @@ impl<'self> StrSlice<'self> for &'self str {
     /// An iterator over the bytes of `self`
     #[inline]
     fn byte_iter(&self) -> ByteIterator<'self> {
-        self.as_bytes().iter().transform(|&b| b)
+        self.as_bytes().iter().map(|&b| b)
     }
 
     /// An iterator over the bytes of `self`, in reverse order
@@ -1565,7 +1565,7 @@ impl<'self> StrSlice<'self> for &'self str {
     /// An iterator over the lines of a string, separated by either
     /// `\n` or (`\r\n`).
     fn any_line_iter(&self) -> AnyLineIterator<'self> {
-        do self.line_iter().transform |line| {
+        do self.line_iter().map |line| {
             let l = line.len();
             if l > 0 && line[l - 1] == '\r' as u8 { line.slice(0, l - 1) }
             else { line }
@@ -1593,7 +1593,7 @@ impl<'self> StrSlice<'self> for &'self str {
 
     /// Returns the number of characters that a string holds
     #[inline]
-    fn char_len(&self) -> uint { self.iter().len_() }
+    fn char_len(&self) -> uint { self.iter().len() }
 
     /// Returns a slice of the given string from the byte range
     /// [`begin`..`end`)
@@ -2546,7 +2546,6 @@ impl Zero for @str {
 
 #[cfg(test)]
 mod tests {
-    use iterator::IteratorUtil;
     use container::Container;
     use option::Some;
     use libc::c_char;
@@ -3687,7 +3686,7 @@ mod tests {
     #[test]
     fn test_str_container() {
         fn sum_len<S: Container>(v: &[S]) -> uint {
-            v.iter().transform(|x| x.len()).sum()
+            v.iter().map(|x| x.len()).sum()
         }
 
         let s = ~"01234";
diff --git a/src/libstd/str/ascii.rs b/src/libstd/str/ascii.rs
index 02a6247428c..c6ae535c19a 100644
--- a/src/libstd/str/ascii.rs
+++ b/src/libstd/str/ascii.rs
@@ -17,7 +17,7 @@ use str::OwnedStr;
 use container::Container;
 use cast;
 use ptr;
-use iterator::{Iterator, IteratorUtil};
+use iterator::Iterator;
 use vec::{CopyableVector, ImmutableVector};
 #[cfg(stage0)]
 use vec::OwnedVector;
diff --git a/src/libstd/task/spawn.rs b/src/libstd/task/spawn.rs
index 1a38dfc3d88..10bac9325ab 100644
--- a/src/libstd/task/spawn.rs
+++ b/src/libstd/task/spawn.rs
@@ -79,7 +79,7 @@ use cast;
 use cell::Cell;
 use container::MutableMap;
 use comm::{Chan, GenericChan, oneshot};
-use hashmap::{HashSet, HashSetConsumeIterator};
+use hashmap::{HashSet, HashSetMoveIterator};
 use local_data;
 use task::{Failure, SingleThreaded};
 use task::{Success, TaskOpts, TaskResult};
@@ -141,8 +141,8 @@ impl TaskSet {
         assert!(was_present);
     }
     #[inline]
-    fn consume(self) -> HashSetConsumeIterator<TaskHandle> {
-        (*self).consume()
+    fn move_iter(self) -> HashSetMoveIterator<TaskHandle> {
+        (*self).move_iter()
     }
 }
 
@@ -460,13 +460,13 @@ fn kill_taskgroup(state: TaskGroupInner, me: &TaskHandle, is_main: bool) {
         if newstate.is_some() {
             let TaskGroupData { members: members, descendants: descendants } =
                 newstate.unwrap();
-            for sibling in members.consume() {
+            for sibling in members.move_iter() {
                 // Skip self - killing ourself won't do much good.
                 if &sibling != me {
                     RuntimeGlue::kill_task(sibling);
                 }
             }
-            for child in descendants.consume() {
+            for child in descendants.move_iter() {
                 assert!(&child != me);
                 RuntimeGlue::kill_task(child);
             }
diff --git a/src/libstd/to_bytes.rs b/src/libstd/to_bytes.rs
index 5ad7969c8d2..f871f4ef6d6 100644
--- a/src/libstd/to_bytes.rs
+++ b/src/libstd/to_bytes.rs
@@ -17,7 +17,7 @@ The `ToBytes` and `IterBytes` traits
 use cast;
 use io;
 use io::Writer;
-use iterator::IteratorUtil;
+use iterator::Iterator;
 use option::{None, Option, Some};
 use str::StrSlice;
 use vec::ImmutableVector;
diff --git a/src/libstd/trie.rs b/src/libstd/trie.rs
index 5ef5526e516..0bfee145a3c 100644
--- a/src/libstd/trie.rs
+++ b/src/libstd/trie.rs
@@ -11,7 +11,7 @@
 //! An ordered map and set for integer keys implemented as a radix trie
 
 use prelude::*;
-use iterator::{IteratorUtil, FromIterator, Extendable};
+use iterator::{FromIterator, Extendable};
 use uint;
 use util::{swap, replace};
 use vec;
@@ -617,7 +617,7 @@ mod test_map {
     fn test_from_iter() {
         let xs = ~[(1u, 1i), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6)];
 
-        let map: TrieMap<int> = xs.iter().transform(|&x| x).collect();
+        let map: TrieMap<int> = xs.iter().map(|&x| x).collect();
 
         for &(k, v) in xs.iter() {
             assert_eq!(map.find(&k), Some(&v));
@@ -680,7 +680,7 @@ mod test_set {
     fn test_from_iter() {
         let xs = ~[9u, 8, 7, 6, 5, 4, 3, 2, 1];
 
-        let set: TrieSet = xs.iter().transform(|&x| x).collect();
+        let set: TrieSet = xs.iter().map(|&x| x).collect();
 
         for x in xs.iter() {
             assert!(set.contains(x));
diff --git a/src/libstd/tuple.rs b/src/libstd/tuple.rs
index 41af29022a6..80d1626c084 100644
--- a/src/libstd/tuple.rs
+++ b/src/libstd/tuple.rs
@@ -15,7 +15,7 @@
 use clone::Clone;
 use vec;
 use vec::ImmutableVector;
-use iterator::IteratorUtil;
+use iterator::Iterator;
 
 pub use self::inner::*;
 
@@ -102,7 +102,7 @@ impl<'self,
     fn map<C>(&self, f: &fn(a: &A, b: &B) -> C) -> ~[C] {
         match *self {
             (ref a, ref b) => {
-                a.iter().zip(b.iter()).transform(|(aa, bb)| f(aa, bb)).collect()
+                a.iter().zip(b.iter()).map(|(aa, bb)| f(aa, bb)).collect()
             }
         }
     }
@@ -122,7 +122,7 @@ impl<A:Clone, B:Clone> ExtendedTupleOps<A,B> for (~[A], ~[B]) {
     fn map<C>(&self, f: &fn(a: &A, b: &B) -> C) -> ~[C] {
         match *self {
             (ref a, ref b) => {
-                a.iter().zip(b.iter()).transform(|(aa, bb)| f(aa, bb)).collect()
+                a.iter().zip(b.iter()).map(|(aa, bb)| f(aa, bb)).collect()
             }
         }
     }
diff --git a/src/libstd/unstable/extfmt.rs b/src/libstd/unstable/extfmt.rs
index d63f914bc73..7b1f0e8ced8 100644
--- a/src/libstd/unstable/extfmt.rs
+++ b/src/libstd/unstable/extfmt.rs
@@ -526,7 +526,7 @@ pub mod rt {
               TyHexLower => uint_to_str_prec(u, 16, prec),
 
               // FIXME: #4318 Instead of to_ascii and to_str_ascii, could use
-              // to_ascii_consume and to_str_consume to not do a unnecessary copy.
+              // to_ascii_move and to_str_move to not do a unnecessary copy.
               TyHexUpper => {
                 let s = uint_to_str_prec(u, 16, prec);
                 s.to_ascii().to_upper().to_str_ascii()
diff --git a/src/libstd/vec.rs b/src/libstd/vec.rs
index 0f6d94bb771..c831dd70918 100644
--- a/src/libstd/vec.rs
+++ b/src/libstd/vec.rs
@@ -382,7 +382,7 @@ pub fn unzip_slice<T:Clone,U:Clone>(v: &[(T, U)]) -> (~[T], ~[U]) {
 pub fn unzip<T,U>(v: ~[(T, U)]) -> (~[T], ~[U]) {
     let mut ts = ~[];
     let mut us = ~[];
-    for p in v.consume_iter() {
+    for p in v.move_iter() {
         let (t, u) = p;
         ts.push(t);
         us.push(u);
@@ -1068,10 +1068,10 @@ impl<'self,T> ImmutableVector<'self, T> for &'self [T] {
     }
 
     /// Deprecated, use iterators where possible
-    /// (`self.iter().transform(f)`). Apply a function to each element
+    /// (`self.iter().map(f)`). Apply a function to each element
     /// of a vector and return the results.
     fn map<U>(&self, f: &fn(t: &T) -> U) -> ~[U] {
-        self.iter().transform(f).collect()
+        self.iter().map(f).collect()
     }
 
     /**
@@ -1174,8 +1174,8 @@ impl<'self,T:Clone> ImmutableCopyableVector<T> for &'self [T] {
 
 #[allow(missing_doc)]
 pub trait OwnedVector<T> {
-    fn consume_iter(self) -> ConsumeIterator<T>;
-    fn consume_rev_iter(self) -> ConsumeRevIterator<T>;
+    fn move_iter(self) -> MoveIterator<T>;
+    fn move_rev_iter(self) -> MoveRevIterator<T>;
 
     fn reserve(&mut self, n: uint);
     fn reserve_at_least(&mut self, n: uint);
@@ -1204,26 +1204,26 @@ impl<T> OwnedVector<T> for ~[T] {
     /// value out of the vector (from start to end). The vector cannot
     /// be used after calling this.
     ///
-    /// Note that this performs O(n) swaps, and so `consume_rev_iter`
+    /// Note that this performs O(n) swaps, and so `move_rev_iter`
     /// (which just calls `pop` repeatedly) is more efficient.
     ///
     /// # Examples
     ///
     /// ~~~ {.rust}
     /// let v = ~[~"a", ~"b"];
-    /// for s in v.consume_iter() {
+    /// for s in v.move_iter() {
     ///   // s has type ~str, not &~str
     ///   println(s);
     /// }
     /// ~~~
-    fn consume_iter(self) -> ConsumeIterator<T> {
-        ConsumeIterator { v: self, idx: 0 }
+    fn move_iter(self) -> MoveIterator<T> {
+        MoveIterator { v: self, idx: 0 }
     }
     /// Creates a consuming iterator that moves out of the vector in
-    /// reverse order. Also see `consume_iter`, however note that this
+    /// reverse order. Also see `move_iter`, however note that this
     /// is more efficient.
-    fn consume_rev_iter(self) -> ConsumeRevIterator<T> {
-        ConsumeRevIterator { v: self }
+    fn move_rev_iter(self) -> MoveRevIterator<T> {
+        MoveRevIterator { v: self }
     }
 
     /**
@@ -1540,7 +1540,7 @@ impl<T> OwnedVector<T> for ~[T] {
         let mut lefts  = ~[];
         let mut rights = ~[];
 
-        for elt in self.consume_iter() {
+        for elt in self.move_iter() {
             if f(&elt) {
                 lefts.push(elt);
             } else {
@@ -2148,7 +2148,7 @@ pub mod bytes {
 impl<A:Clone> Clone for ~[A] {
     #[inline]
     fn clone(&self) -> ~[A] {
-        self.iter().transform(|item| item.clone()).collect()
+        self.iter().map(|item| item.clone()).collect()
     }
 }
 
@@ -2281,12 +2281,12 @@ pub type MutRevIterator<'self, T> = Invert<VecMutIterator<'self, T>>;
 
 /// An iterator that moves out of a vector.
 #[deriving(Clone)]
-pub struct ConsumeIterator<T> {
+pub struct MoveIterator<T> {
     priv v: ~[T],
     priv idx: uint,
 }
 
-impl<T> Iterator<T> for ConsumeIterator<T> {
+impl<T> Iterator<T> for MoveIterator<T> {
     fn next(&mut self) -> Option<T> {
         // this is peculiar, but is required for safety with respect
         // to dtors. It traverses the first half of the vec, and
@@ -2308,11 +2308,11 @@ impl<T> Iterator<T> for ConsumeIterator<T> {
 
 /// An iterator that moves out of a vector in reverse order.
 #[deriving(Clone)]
-pub struct ConsumeRevIterator<T> {
+pub struct MoveRevIterator<T> {
     priv v: ~[T]
 }
 
-impl<T> Iterator<T> for ConsumeRevIterator<T> {
+impl<T> Iterator<T> for MoveRevIterator<T> {
     fn next(&mut self) -> Option<T> {
         self.v.pop_opt()
     }
@@ -3323,17 +3323,17 @@ mod tests {
     }
 
     #[test]
-    fn test_consume_iterator() {
+    fn test_move_iterator() {
         use iterator::*;
         let xs = ~[1u,2,3,4,5];
-        assert_eq!(xs.consume_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
+        assert_eq!(xs.move_iter().fold(0, |a: uint, b: uint| 10*a + b), 12345);
     }
 
     #[test]
-    fn test_consume_rev_iterator() {
+    fn test_move_rev_iterator() {
         use iterator::*;
         let xs = ~[1u,2,3,4,5];
-        assert_eq!(xs.consume_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
+        assert_eq!(xs.move_rev_iter().fold(0, |a: uint, b: uint| 10*a + b), 54321);
     }
 
     #[test]
@@ -3608,7 +3608,7 @@ mod tests {
         }
         assert_eq!(cnt, 8);
 
-        for f in v.consume_iter() {
+        for f in v.move_iter() {
             assert!(f == Foo);
             cnt += 1;
         }