Implementing Iterator in a Trait

1

I have two map-like types that implement a trait. The trait lets one search for the closest value in those objects without worrying what the actual underlying type is.

I would like to extend the trait to be able to iterate over the items in those map-like objects.

One of the two types is BTreeMap with which I could do btreemap.iter(), but this returns btree_map::Iter and I can't have this BTree-specific struct as return value of my generic trait. I would like to have something like Iterator<Item=(f64, Position)>, but I can't get it to work.

What would be the right approach here for constructing a generic iterator?

type PositionMapA = BTreeMap<u64, Position>;
pub struct PositionMapB { ... }

pub trait FindPosition: Sync + Send {
    fn find(&self, f64) -> Option<Position>;
    fn iter(&self) -> Iterator<Item=(f64, Position)>; // ?
}

impl FindPosition for PositionMapA {
    fn find(...) {...}
}

impl FindPosition for PositionMapB {
    fn find(...) {...}
}
2 
pub struct MyFunkyIterator(SomeBTreIterator);

Not seen from outside because field isn't marked as pub
Then, an Iterator delegating impl for it.

3

Just in case, here's a template for implementing your Iterator:

impl Iterator for MyFunkyIterator {
    type Item = (f64, Position);

    fn next(&mut self) -> Option<(f64, Position)> {
        // @target_san's example has the inner iterator at self.0
        // so maybe call self.0.next(), tweak the result, and return it.
    }
}
4

Oh, since your different FindPosition impls may want different iterators, you probably want an associated type of your own. Something like this (untested)

type PositionMapA = BTreeMap<u64, Position>;
pub struct PositionMapB { ... }

pub trait FindPosition: Sync + Send {
    type Iter: Iterator<Item=(f64, Position)>;
    fn iter(&self) -> Iter;
}

impl FindPosition for PositionMapA {
    type Iter = IteratorA;
    fn iter(&self) -> IteratorA { /* ... */ }
}

impl FindPosition for PositionMapB {
    type Iter = IteratorB;
    fn iter(&self) -> IteratorB { /* ... */ }
}
1 Like
5

For a trait method that returns an iterator — use the same construction as the IntoIterator trait. It's not ideal, but it lets the traits provide an iterator that borrows from &self properly.

See the impl IntoIterator for &'a Vec<T> for an example.

6

If I do this:

pub trait FindPosition {
    type Iter: Iterator<Item=(f64, Position)>;
    fn iter(&self) -> Iter;
}

I get error: use of undeclared type name `Iter` .

By the way, is defining Iter beforehand any different from simply fn iter(&self) -> Iterator<Item=(f64, Position)>?

7

I also have another issue when trying to implement iter for PositionMapA. That is, I just want it to return whatever BTreeMap returns when its .iter() is called. Here's what I'm trying to do:

use std::collections::btree_map;

impl FindPosition for PositionMapA {
    fn iter(&self) -> btree_map::Iter<f64, Position> {
        return self.iter()
    }
}

However, this gives an error: method `iter` has an incompatible type for trait: expected trait core::iter::Iterator, found struct `collections::btree::map::Iter` [E0053]. But from what I see in btree_map docs, this Iter does implement Iterator.

To paraphrase this question - how do I create a function that returns BTreeMap's Iter as a generic trait (as `Iterator<Item=(f64, Position)> or anything else for that matter)?

8 
fn iter(&self) -> Self::Iter;
9

I did say it was untested. :smile: It should be -> Self::Iter.

Yes, it's different. Note we're not actually defining or assigning the associated type Iter yet. We're just saying it has to implement Iterator... the same way your Sync + Send bound put a requirement on FindPosition implementers. Associated types are a lot like generic type parameters, and in fact they used to be written as explicit type parameters before associated types came around.

Whereas writing -> Iterator is trying to directly return a trait, which is not supported. It must be a concrete type or boxed as a trait object. There was RFC 105 to support this kind of thing, but I don't know if there's any current work on this.

You can do this, but not with f64 as the key, since BTreeMap requires full Ord. So either you need a middleman iterator type to translate the key to f64, or we can make FindPosition even more generic.

Here's a more complete example which compiles on the playground: Rust Playground

use std::collections::btree_map::{self, BTreeMap};

pub struct Position;

pub trait FindPosition<'a> {
    type Key;
    type Iter: Iterator<Item=(Self::Key, &'a Position)>;
    fn iter(&'a self) -> Self::Iter;
}

type PositionMapA = BTreeMap<u64, Position>;

impl<'a> FindPosition<'a> for PositionMapA {
    type Key = &'a u64;
    type Iter = btree_map::Iter<'a, u64, Position>;
    
    fn iter(&'a self) -> Self::Iter {
        BTreeMap::iter(self)
    }
}