How to implement IntoIterator for Tree?

Question

I try to implement IntoIterator for Tree, then I can use " for in Tree ", otherwise I have to write for in TreeIter{...}, but the lifetime error:

use std::iter::IntoIterator;

#[derive(Debug)]
struct Tree<T> {
    data: T,
}

struct TreeIter<'a, T> {
    tree: &'a Tree<T>,
    count: i32,
}

impl<'a, T> IntoIterator for Tree<T> {
    type Item = &'a Tree<T>;
    type IntoIter = TreeIter<'a, T>;

    fn into_iter(&'a self) -> Self::IntoIter {
        TreeIter { tree: &self, count: 0 }
    }
}

impl<'a, T> Iterator for TreeIter<'a, T>
{
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.count += 1;
        if self.count > 5 {
            return None;
        } else {
            return Some(&self.tree.data);
        }
    }
}

fn main() {
    let tree = Tree { data: "abc" };

    for v in tree {
        println!("{:?}", v);
    }

    /*
    let treeiter = TreeIter{tree: &tree, count: 0};
    for (i, &v) in treeiter.enumerate() {
        println!("{}: {}", i, v);
    }
    */
}

got error: error[E0207]: the lifetime parameter 'a is not constrained by the impl trait

error[E0207]: the lifetime parameter `'a` is not constrained by the impl trait, self type, or predicates
  --> test-iter/src/main.rs:13:6
   |
13 | impl<'a, T> IntoIterator for Tree<T> {
   |      ^^ unconstrained lifetime parameter

score 4 · Accepted Answer · answered Jan 08 '21 at 07:18

Given your TreeIter structure and everything else, you don't want to consume the Tree on iteration, you just want it to reference the elements. So you want

impl<'a, T> IntoIterator for &'a Tree<T> {
                          // ^^^^^^^^^^^ implement for references to Trees
    type Item = &'a T;
             // ^^^^^ this needs to match Iterator::Item for TreeIter
    type IntoIter = TreeIter<'a, T>;

    fn into_iter(self) -> Self::IntoIter {
              // ^^^^ self is a &'a Tree<T>
        TreeIter { tree: self, count: 0 }
    }
}

Then you can use it in a for loop like so:

let tree = Tree { data: "abc" };
for v in &tree {
      // ^ only iterate via reference
    println!("{:?}", v);
}

See it on the playground. See this Q&A for the difference between for _ in x vs for _ in &x.

Another answer to this post suggests a consuming iterator. A fully featured collection will typically have *both*; see [IntoIterator implementations for Vec](https://doc.rust-lang.org/std/vec/struct.Vec.html#impl-IntoIterator), there's one for `Vec`, one for `&Vec`, as well as one for `&mut Vec`. — kmdreko, Jan 08 '21 at 07:59

HTNW · Answer 2 · 2021-01-08T09:32:38.533

into_iter() is meant to wholesale take ownership of the collection. The collection is moved into the iterator and is consumed by iteration, not borrowed by reference and simply looked at. That behavior is provided by iter() and iter_mut(). Your code is thus conceptually flawed, and the compiler error reflects that: into_iter doesn't take a borrow a collection with whatever lifetime it already has; it takes a collection and ends its lifetime right then and there. There's no 'a for you to impl<'a> over. Implement it with the right idea in mind and it works

struct IntoIter<T> { // e.g. same convention as std::vec::IntoIter
    tree: Tree<T>,
    pos: i32,
}
// due to your dummy implementation, we need T: Copy, but a real implementation shouldn't need it
impl<T: Copy> IntoIterator for Tree<T> {
    type Item = T; // why would iterating over a tree give you trees?
    type IntoIter = IntoIter<T>;
    fn into_iter(self) -> Self::IntoIter {
        IntoIter { tree: self, pos: 0 }
    }
}
impl<T: Copy> Iterator for IntoIter<T> {
    type Item = T; // iterating over an IntoIter should give values moved out of the container (in this case we're copying the same value a few times and pretending they were moved)
    fn next(&mut self) -> Option<Self::Item> {
        if self.pos < 5 {
            self.pos += 1;
            Some(self.tree.data)
        } else {
            None
        }
    }
}

fn main() {
    for i in (Tree { data: 1 }) { println!("{}", i) }
}

Note that it is conventional to provide IntoIterator for borrows of the collection as well. Again, into_iter() should be seen as consuming it's argument... but "consuming" a borrow doesn't actually consume what it's referring to. This would use your iterator type, but note that this trait implementation is not what we're using in the above main.

struct Iter<'a, T> {
    tree: &'a Tree<T>,
    pos: i32
}
impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> { todo!() }
}
impl<'a, T> IntoIterator for &'a Tree<T> {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;
    fn into_iter(self) -> Iter<'a, T> { todo!() }
}

struct IterMut<'a, T> {
    tree: &'a mut Tree<T>,
    pos: i32
}
impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> { todo!() }
}
impl<'a, T> IntoIterator for &'a mut Tree<T> {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;
    fn into_iter(self) -> IterMut<'a, T> { todo!() }
}

These would be called if you did

fn main() {
    let mut tree = Tree { data: 1 };
    for i in &tree { println!("{}", i) } // IntoIter for borrow
    for i in &mut tree { println!("{}", i) } // IntoIter for mutable borrow
}

How to implement IntoIterator for Tree?

2 Answers2