Group iterator into HashMap<K, Vec<V>>

Hi, I need the following function:

fn group<K, V, I>(iter: I) -> HashMap<K, Vec<V>>
 where 
  K: Eq + std::hash::Hash,
  I: Iterator<Item = (K, V)>{...}

I maps each k to a list of all its partners. Example in pseudocode:

group(vec![(1,2), (1,3), (3,4)].iter()) 
  == map!(1 => vec![1,3], 3 => vec![4])

Does there exist such a function in std?

I don't think there is a function doing exactly that but you can use entry to do it:

fn group<K, V, I>(iter: I) -> HashMap<K, Vec<V>>
where
    K: Eq + std::hash::Hash,
    I: Iterator<Item = (K, V)>,
{
    let mut hash_map = match iter.size_hint() {
        (_, Some(len)) => HashMap::with_capacity(len),
        (len, None) => HashMap::with_capacity(len)
    };

    for (key, value) in iter {
        hash_map.entry(key).or_insert_with(|| Vec::with_capacity(1)).push(value)
    }

    hash_map
}

I used with_capacity but you don't have to.
Also you'll have to use into_iter.

1 Like

I am quite surprised that this does not exist yet.

In the first iteration, I implemented this with a fold

fn group<K: Eq + std::hash::Hash, V, I: Iterator<Item = (K, V)>>(iter: I) -> HashMap<K, Vec<V>> {
    iter.fold(HashMap::new(), |mut map, (k, v)| {
        map.entry(k).or_insert_with(|| Vec::new()).push(v);
        map
    })
}

It probably won't ever exist. Rust's std tries to stay:

a set of minimal and battle-tested shared abstractions

Since you can create this functionality with a few functions and no unsafe there is no necessity to have it in the standard library.
If you really don't want to do it yourself I found this crate while googling.
There is also itertools that extends std::iter::Iterator so maybe there is something you can do with it.

1 Like

In particular, there is Itertools::into_group_map.

3 Likes