How to implement Iterator and IntoIterator for a simple struct?

Question

How would someone implement the Iterator and IntoIterator traits for the following struct?

struct Pixel {
    r: i8,
    g: i8,
    b: i8,
}

I've tried various forms of the following with no success.

impl IntoIterator for Pixel {
    type Item = i8;
    type IntoIter = Iterator<Item=Self::Item>;

    fn into_iter(self) -> Self::IntoIter {
        [&self.r, &self.b, &self.g].into_iter()
    }
}

This code gives me a compile error

error[E0277]: the trait bound `std::iter::Iterator<Item=i8> + 'static: std::marker::Sized` is not satisfied
 --> src/main.rs:7:6
  |
7 | impl IntoIterator for Pixel {
  |      ^^^^^^^^^^^^ the trait `std::marker::Sized` is not implemented for `std::iter::Iterator<Item=i8> + 'static`
  |
  = note: `std::iter::Iterator<Item=i8> + 'static` does not have a constant size known at compile-time
  = note: required by `std::iter::IntoIterator`

Shepmaster · Accepted Answer · 2021-03-29 14:35:01Z

182

Your iterator type is Iterator<Item = Self::Item>, but Iterator is a trait. Traits are implemented by structs, they don't exist on their own. You could also have a reference trait object (&Iterator), a boxed trait object (Box<Iterator>) or an anonymous trait implementation (impl Iterator), all of which have a known sizes.

Instead, we create a PixelIntoIterator that has a known size and implements Iterator itself:

struct Pixel {
    r: i8,
    g: i8,
    b: i8,
}

impl IntoIterator for Pixel {
    type Item = i8;
    type IntoIter = PixelIntoIterator;

    fn into_iter(self) -> Self::IntoIter {
        PixelIntoIterator {
            pixel: self,
            index: 0,
        }
    }
}

pub struct PixelIntoIterator {
    pixel: Pixel,
    index: usize,
}

impl Iterator for PixelIntoIterator {
    type Item = i8;
    fn next(&mut self) -> Option<i8> {
        let result = match self.index {
            0 => self.pixel.r,
            1 => self.pixel.g,
            2 => self.pixel.b,
            _ => return None,
        };
        self.index += 1;
        Some(result)
    }
}

fn main() {
    let p = Pixel {
        r: 54,
        g: 23,
        b: 74,
    };
    for component in p {
        println!("{}", component);
    }
}

This has the nice benefit of returning actual i8s, not references. Since these are so small, you might as well pass them directly.

This consumes the Pixel. If you had a reference to a Pixel, you'd need to also implement an iterator that doesn't consume it:

impl<'a> IntoIterator for &'a Pixel {
    type Item = i8;
    type IntoIter = PixelIterator<'a>;

    fn into_iter(self) -> Self::IntoIter {
        PixelIterator {
            pixel: self,
            index: 0,
        }
    }
}

pub struct PixelIterator<'a> {
    pixel: &'a Pixel,
    index: usize,
}

impl<'a> Iterator for PixelIterator<'a> {
    type Item = i8;
    fn next(&mut self) -> Option<i8> {
        let result = match self.index {
            0 => self.pixel.r,
            1 => self.pixel.g,
            2 => self.pixel.b,
            _ => return None,
        };
        self.index += 1;
        Some(result)
    }
}

If you wanted to support creating both a consuming iterator and a non-consuming iterator, you can implement both versions. You can always take a reference to a Pixel you own, so you only need the non-consuming variant. However, it's often nice to have a consuming version so that you can return the iterator without worrying about lifetimes.

it'd be much more convenient to write this by reusing iterators that already exists, e.g., with [T; 3]

As of Rust 1.51, you can leverage array::IntoIter:

impl IntoIterator for Pixel {
    type Item = i8;
    type IntoIter = std::array::IntoIter<i8, 3>;

    fn into_iter(self) -> Self::IntoIter {
        std::array::IntoIter::new([self.r, self.b, self.g])
    }
}

In previous versions, it might be a bit silly, but you could avoid creating your own iterator type by gluing some existing types together and using impl Iterator:

use std::iter;

impl Pixel {
    fn values(&self) -> impl Iterator<Item = i8> {
        let r = iter::once(self.r);
        let b = iter::once(self.b);
        let g = iter::once(self.g);
        r.chain(b).chain(g)
    }
}

edited Mar 29, 2021 at 14:35

answered May 13, 2015 at 16:47

Shepmaster

439k116 gold badges1.3k silver badges1.5k bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

BurntSushi5 Over a year ago

The OP was on to something though: it'd be much more convenient to write this by reusing iterators that already exists, e.g., with [T; 3]. But AFAIK, you can't move out of arrays. Instead, you can do this, but it costs an allocation: is.gd/IMVLoG

Shepmaster Over a year ago

Right, and you can't convert an array into an iterator to store it standalone, either. Allocating a Vec is certainly an option, but seemed overkill for this struct.

ArtemGr Over a year ago

Now that we have a good answer I'll post mine. It has a bit of guesswork about arrays.

bluss Over a year ago

You can implement a by move iterator for fixed size arrays (see literator on github). The basic trick available right now is to store Option<[T; N]> in the iterator and write over it with None to inhibit drop of the inner value. The drop_in_place intrinsic just merged will make this easier in future rust.

Shepmaster Over a year ago

@AaronMerriam I added a bit more about the differences - does that help any?

|

ArtemGr · Accepted Answer · 2015-05-13 18:12:43Z

9

First, IntoIter must point to a real struct and not to a trait in order for Rust to be able to pass the value around (that's what Sized means). In case of arrays into_iter returns the std::slice::Iter struct.

Second, a typical array, [1, 2, 3], isn't allocated on heap. In fact, the compiler is allowed to optimize away the allocation entirely, pointing to a pre-compiled array instead. Being able to iterate the arrays without copying them anywhere is I think the reason why the IntoIterator implementation for arrays doesn't move the array anywhere as other IntoIterator implementations do. Instead it seems to reference the existing array. You can see from its signature

impl<'a, T> IntoIterator for &'a [T; 3]
    type Item = &'a T
    type IntoIter = Iter<'a, T>
    fn into_iter(self) -> Iter<'a, T>

that it takes a reference to an array (&'a [T; 3]).

As such, you can't use it in the way you're trying to. The referenced array must outlive the returned iterator. Here's a version where Rust compiler tells so.

Vector has an IntoIterator implementation that truly moves the data into the iterator and so you can use it.

P.S. To make it both fast and simple, return an array instead of an iterator (playpen):

impl Pixel {
    fn into_array(self) -> [i8; 3] {[self.r, self.g, self.b]}
}

That way the array is first moved into the outer scope and then it can be referenced from the outer scope's iterator:

for color in &(Pixel {r: 1, g: 2, b: 3}).into_array() {
    println! ("{}", color);
}

edited May 13, 2015 at 18:12

answered May 13, 2015 at 16:59

ArtemGr

12.8k3 gold badges57 silver badges90 bronze badges

2 Comments

Piper Merriam Over a year ago

I don't know enough about the language to understand any of the additional implications that might come with this, but it looks clean. Thank you.

ArtemGr Over a year ago

Using vec! adds a heap allocation, it's slower than Shepmaster's version. On my machine Shepmaster's version (is.gd/BJUSbZ) performs at 1 ns/iter. vec! version (is.gd/CMNqzR) performs at 23 ns/iter. A version returning an array (is.gd/pr6Zaf) is both fast and simple to implement, it performs at 1 ns/iter on my hardware.

Collectives™ on Stack Overflow

How to implement Iterator and IntoIterator for a simple struct?

2 Answers 2

7 Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related