How does Iterator::next(&mut self) move out values?

[jacg]

Iterators such as std::vec::IntoIter<T> consume the iterand, yielding the contained items by value. If the item type is non-Copy, the iterator's .next() method would seem to me moving (surely not cloning‽) items that it gets from &mut self.

For example

let v: Vec<String> = vec!["a".to_string()];
let mut iterator: std::vec::IntoIter<String> = v.into_iter();
let first: String = iterator.next().unwrap();

Was the String in first moved out of next's &mut self? If so, how?

Put another way, how can one get around the compilation error

error[E0507]: cannot move out of `self.data` which is behind a mutable reference
  --> src/lib.rs:19:18
   |
19 |             Some(self.data.0)
   |                  ^^^^^^^^^^^ move occurs because `self.data.0` has type `String`, which does not implement the `Copy` trait

in this toy example?

struct One(String);

impl IntoIterator for One {
    type Item = String;
    type IntoIter = IntoIter;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter { data: self, finished: false }
    }
}

struct IntoIter { data: One, finished: bool }

impl Iterator for IntoIter {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        if self.finished { None }
        else { 
            self.finished = true;
            Some(self.data.0)
        }
    }
}

playground

[steffahn]

For the most general tool for moving out data behind a mutable reference, look at replace in std::mem - Rust an its friend take in std::mem - Rust.

For the iterator at hand, you should use a Option<One> field (and then you don't need the finished either); for convenience, the Option type even has the equivalent of mem::take as an inherent method, .take().

It is possible without using Option, too, but then you would need to leave an empty string in place, because you cannot completely move out of an owned value, unless you provide immediate replacement.

[tczajka]

Or use an Option<String> in the iterator:

struct One(String);

impl IntoIterator for One {
    type Item = String;
    type IntoIter = IntoIter;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter(Some(self.0))
    }
}

struct IntoIter(Option<String>);

impl Iterator for IntoIter {
    type Item = String;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take()
    }
}

[quinedot]

If you're wondering how vec::IntoIter<T> in particular does it, it keeps track of which elements have been returned or not (from either end), and also drops any non-iterated items when the iterator drops (in addition to freeing the allocated memory of the Vec itself).

The implementation is too generic to be able to use std::mem::take ^[1], and doesn't want to do a bunch of extra work moving everything into a new Vec<Option<T>> or such, so it uses low-level pointer operations (requiring unsafe) to keep track of what has been moved or not.

Usually there's a safe way to do it for your own iterators, though (either because your iterator is not completely generic, or because your completely generic collection is built upon other collections like Vec).

---

1. or Clone ↩︎