How to reverse map of objects to vector of tuples by using an iterator?

Question

What is the easiest way to convert HashMap<String, String> to Vec<(String, Vec<String>)> by using an iterator ? I want to reverse the map.

I've tried to use iter() methods but have no idea how to do a correct map closure implementation for collecting values after:

fn get_aliases(&self) -> Vec<(String, Vec<String>)> {
    let mut aliases: HashMap<String, String> = HashMap::new();
    aliases.insert("a".to_owned(), "test".to_owned());
    aliases.insert("b".to_owned(), "test".to_owned());
    aliases.insert("c".to_owned(), "test2".to_owned());

    aliases.iter().map(|(ref a, ref c)| {
        // what to do here?
    }).collect()

    // the expected return value is:
    // [("test", ["a", "b"]), ("test2", ["c"])]
}

This function will return a vector which says what String keys belong to some object.

I could write a lot of code with for and finds but it seems to me this would be less efficient and I think there is a way to do that by using iterators only.

Answer 1

I could write a lot of code with for and finds but it seems to me this would be less efficient and I think there is a way to do that by using iterators only.

I wouldn't call it a lot of code, and remember that for loops operate on iterators. I've not done any benchmarking, but this is far simpler and I'd expect it to be more performant:

use std::collections::HashMap;

fn get_aliases(aliases: HashMap<String, String>) -> Vec<(String, Vec<String>)> {
    let mut x = HashMap::new();

    for (k, v) in aliases {
        x.entry(v).or_insert_with(Vec::new).push(k)
    }

    x.into_iter().collect()
}

fn main() {
    let mut aliases = HashMap::new();
    aliases.insert("a".to_owned(), "test".to_owned());
    aliases.insert("b".to_owned(), "test".to_owned());
    aliases.insert("c".to_owned(), "test2".to_owned());

    println!("{:?}", get_aliases(aliases));
}

Answer 2

It's not trivial, certainly not as trivial as it would be with some other stream libraries that provide the necessary functions.

You can use the itertools crate's group_by to group elements by some key. However, it only groups adjacent elements, so you have to sort them first. Here's my result:

impl A {
    pub fn get_aliases(&self) -> Vec<(String, Vec<String>)> {
        // Get a Vec of string references for sorting. Reverse element
        // order for clarity.
        let mut v = self.aliases.iter()
            .map(|(a, c)| (&c[..], &a[..])).collect::<Vec<_>>();
        v.sort_by_key(|t| t.0); // Make identical keys adjacent.
        let g = v.into_iter().group_by(|t| t.0); // Create grouping.
        g.into_iter()
            .map(|(key, group)| // key is the str with the key
                                // group is a subiterator that just visits
                                // elements with that key, Item=&(&str,&str)
                (key.to_string(), // result is a tuple of the key as String
                 group.map(|t| t.1.to_string()).collect())
                   // and the subiterator turned into a Vec<String>
                )
            .collect() // finally, turn Iterator<Item=(String, Vec<String>) into Vec
    }
}

Going back to your original problem, you have the additional issue that Arc<Object> is only PartialEq (needed by group_by) if Object is; same for Ord (needed by sort_by_key). If your Object type cannot be compared that way and you want to use the pointer identity, your intermediate vector will need to store some newtype wrapper around Arc that uses pointer values for comparison.