Returning a parametrized iterator over HashMap entries in stable Rust

Question

I'm trying to extend a Rust container (HashMap) with a method that returns a non-owning iterator, similarly to iter(). This method would iterate over the same entries as HashMap::iter() but will filter out some entries. I want to parametrize the filtering with a &str parameter (so depending on the parameter, some, none, or all the map's (&k, &v) entries are stepped over).

I decided to use an extension trait for the implementation, and in the new method, just summon iter().filter_map().

use std::collections::{hash_map, HashMap};

pub struct Section {}

pub trait HashMapExt<'a> {
    type FilterMap: Iterator<Item = &'a Section>;

    fn iter_sections(&'a self, path: &'static str) -> Self::FilterMap;
}

A dummy implementation that is not capturing the parameter in a closure works fine:

impl<'a> HashMapExt<'a> for HashMap<String, Section> {
    type FilterMap = core::iter::FilterMap<hash_map::Iter<'a, String, Section>,
                                           fn((&String, &'a Section))->Option<&'a Section>>;

    fn iter_sections(&'a self, path: &str) -> Self::FilterMap {
        self.iter().filter_map(|(k,v)| {
            println!("do stuff"); // Simulate filtering
            Some(v)
        })
    }
}

Problems arise when I'm trying to capture "path":

fn iter_sections(&'a self, path: &str) -> Self::FilterMap {
    self.iter().filter_map(|(k,v)| {
        path;  // simulate "path" based filtering
        Some(v)
    }) 
}

Which results in an error at the filter_map() line:

error[E0308]: mismatched types
expected fn pointer, found closure
note: expected fn pointer `for<'r> fn((&'r String, &Section)) -> Option<&Section>`
      found closure `[closure@src/main.rs:31:32: 31:57]`

I don't have any problem returning a FilterMap type parametrized by closure type, but the problem is that this [closure@src/main.rs...] thing doesn't have a type name in Rust.

And that is my question: How do I specify the return type of a trait method that is accepting a parametrized filter so I get a working iter_sections() method?

My attempts to work around this issue so far:

I thought that maybe using a non-parametric function pointer would resolve the issue:

fn make_filter<'a>(path: &'static str) -> impl Fn((&String,
                                                   &'a Section))->Option<&'a Section> {
    move|(p, c)| {
        path;  // simulate "path" based filtering
        Some(c)
    }
}

used as:

    fn iter_sections(&'a self, path: &'static str) -> Self::FilterMap {
        let filter = make_filter(path);
        self.iter().filter_map(filter)
    }

Which doesn't help:

error[E0308]: mismatched types
expected fn pointer, found opaque type
note: expected fn pointer `for<'r> fn((&'r String, &Section)) -> Option<&Section>`
      found opaque type `impl for<'r> Fn<((&'r String, &Section),)>`

I attempted to return an "impl" type in the trait implementation:

type FilterMap = core::iter::FilterMap<hash_map::Iter<'a, String, Section>,
                                       impl Fn((&String, &'a Section))->Option<&'a Section>>;

Which apparently isn't possible in stable Rust:

error[E0658]: `impl Trait` in type aliases is unstable

note: see issue #63063 <https://github.com/rust-lang/rust/issues/63063> for more information

I have Rust v1.48 so this is not an option for me. I know about "Box" based solutions (make the trait deal in Box<dyn Trait> return values) but I'd like to avoid heap allocations whenever possible, and express the iterator type thru type manipulation.

Angelicos Phosphoros · Accepted Answer · 2023-03-07 13:39:44Z

2

You can implement filtering manually.

use std::collections::hash_map::Iter as HmIter;
use std::collections::HashMap;

trait HashMapExt<K, V>{
    fn iter_sections<'a>(&'a self, path: &'a str)->IterSections<'a, K, V>;
}

struct IterSections<'a, K: 'a, V: 'a>{
    path: &'a str,
    map_iter: HmIter<'a, K, V>,
}

impl<'a, K: 'a, V: 'a> Iterator for IterSections<'a, K, V> {
    type Item = <HmIter::<'a, K, V> as Iterator>::Item;
    fn next(&mut self)->Option<Self::Item> {
        while let Some(res) = self.map_iter.next(){
            // Simulate filtering
            if self.path == "Hello" {
                return Some(res);
            }
        }
        None
    }
}

impl<K,V> HashMapExt<K,V> for HashMap<K,V>{
    fn iter_sections<'a>(&'a self, path: &'a str)->IterSections<'a, K, V>{
        IterSections{
            path,
            map_iter: self.iter(),
        }
    }
}

Probably, you should also implement fold/try_fold functions too.

answered Mar 7, 2023 at 13:39

Angelicos Phosphoros

3,2211 gold badge13 silver badges32 bronze badges

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

1 Comment

cheater Over a year ago

Thanks! This is not the approach I was planning initially but it works just fine.

Collectives™ on Stack Overflow

Returning a parametrized iterator over HashMap entries in stable Rust

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related