Merge two HashMaps in Rust

Question

So I'm a bit stuck, trying to merge two HashMaps.

It's easy to do it inline:

fn inline() {
    let mut first_context = HashMap::new();
    first_context.insert("Hello", "World");
    let mut second_context = HashMap::new();
    second_context.insert("Hey", "There");

    let mut new_context = HashMap::new();
    for (key, value) in first_context.iter() {
        new_context.insert(*key, *value);
    }
    for (key, value) in second_context.iter() {
        new_context.insert(*key, *value);
    }
    println!("Inline:\t\t{}", new_context);
    println!("Inline:\t\t{}\t{} [Initial Maps Still Usable]", first_context, second_context);
}

It's easy enough to make a function:

fn abstracted() {
    fn merge<'a>(first_context: &HashMap<&'a str, &'a str>, second_context: &HashMap<&'a str, &'a str>) -> HashMap<&'a str, &'a str> {
        let mut new_context = HashMap::new();
        for (key, value) in first_context.iter() {
            new_context.insert(*key, *value);
        }
        for (key, value) in second_context.iter() {
            new_context.insert(*key, *value);
        }
        new_context
    }

    let mut first_context = HashMap::new();
    first_context.insert("Hello", "World");
    let mut second_context = HashMap::new();
    second_context.insert("Hey", "There");

    println!("Abstracted:\t{}", merge(&first_context, &second_context));
    println!("Abstracted:\t{}\t{} [Initial Maps Still Usable]", first_context, second_context);
}

However, I can't seem to get the generic version to work:

fn generic() {
    fn merge<'a, K: Hash + Eq, V>(first_context: &HashMap<&'a K, &'a V>, second_context: &HashMap<&'a K, &'a V>) -> HashMap<&'a K, &'a V> {
        let mut new_context = HashMap::new();
        for (key, value) in first_context.iter() {
            new_context.insert(*key, *value);
        }
        for (key, value) in second_context.iter() {
            new_context.insert(*key, *value);
        }
        new_context
    }

    let mut first_context = HashMap::new();
    first_context.insert("Hello", "World");
    let mut second_context = HashMap::new();
    second_context.insert("Hey", "There");

    println!("Generic:\t{}", merge(&first_context, &second_context));
    println!("Generic:\t{}\t{} [Initial Maps Still Usable]", first_context, second_context);
}

The above code on play.rust-lang.org.

Compiling it:

error: the trait `core::kinds::Sized` is not implemented for the type `str`

I get that the compiler is confused about the size of the generic value, but I'm not sure why "str" doesn't have a strict memory size? I know its a String slice and not a type, but still this should work, no? Is this a bug?

I thought this would be a relatively trivial function. If someone has a good solution, I'd love to learn. Actually ideally, I'd love to see a solution with a trait Mergeable and write a decorator for HashMap<&K, &V>, such that I can call let new_context = first_context.merge(&second_context); but this can be a different question.

Answer 1

A more up to date answer from this tweet:

use std::collections::HashMap;

// Mutating one map
fn merge1(map1: &mut HashMap<(), ()>, map2: HashMap<(), ()>) {
    map1.extend(map2);
}

// Without mutation
fn merge2(map1: HashMap<(), ()>, map2: HashMap<(), ()>) -> HashMap<(), ()> {
    map1.into_iter().chain(map2).collect()
}

// If you only have a reference to the map to be merged in
fn merge_from_ref(map: &mut HashMap<(), ()>, map_ref: &HashMap<(), ()>) {
    map.extend(map_ref.into_iter().map(|(k, v)| (k.clone(), v.clone())));
}

Rust Playground Link

Answer 2

This version does work:

use std::collections::HashMap;
use std::hash::Hash;

fn main() {
    fn merge<K: Hash + Eq + Copy, V: Copy>(first_context: &HashMap<K, V>, second_context: &HashMap<K, V>) -> HashMap<K, V> {
        let mut new_context = HashMap::new();
        for (key, value) in first_context.iter() {
            new_context.insert(*key, *value);
        }
        for (key, value) in second_context.iter() {
            new_context.insert(*key, *value);
        }
        new_context
    }

    let mut first_context = HashMap::new();
    first_context.insert("Hello", "World");
    let mut second_context = HashMap::new();
    second_context.insert("Hey", "There");

    println!("Generic:\t{}", merge(&first_context, &second_context));
    println!("Generic:\t{}\t{} [Initial Maps Still Usable]", first_context, second_context);
}

The difference is in the signature of merge(). Here is yours:

fn merge<'a, K: Hash + Eq, V>(first_context: &HashMap<&'a K, &'a V>, second_context: &HashMap<&'a K, &'a V>) -> HashMap<&'a K, &'a V>

Here is mine:

fn merge<K: Hash + Eq + Copy, V: Copy>(first_context: &HashMap<K, V>, second_context: &HashMap<K, V>) -> HashMap<K, V>

For some reason you are trying to abstract HashMap<&str, &str> to HashMap<&K, &V>, but this is not really correct: while &str is a borrowed pointer, it is special - it points to dynamically sized type str. Size of str is not known to the compiler, so you can use it only through a pointer. Consequently, neither Hash nor Eq are implemented for str, they are implemented for &str instead. Hence I've changed HashMap<&'a K, &'a V> to HashMap<K, V>.

The second problem is that in general you can't write your function if it takes only references to maps. Your non-generic merge function works only because &str is a reference and references are implicitly copyable. In general case, however, both keys and values can be non-copyable, and merging them into the single map will require moving these maps into the function. Adding Copy bound allows that.

You can also add Clone bound instead of Copy and use explicit clone() call:

fn merge<K: Hash + Eq + Clone, V: Clone>(first_context: &HashMap<K, V>, second_context: &HashMap<K, V>) -> HashMap<K, V> {
    // ...
    for (key, value) in first_context.iter() {
        new_context.insert(key.clone(), value.clone());
    }
    // ...
}

The most general way, however, is moving maps into the function:

fn merge<K: Hash + Eq, V>(first_context: HashMap<K, V>, second_context: HashMap<K, V>) -> HashMap<K, V>  {
    // ...
    for (key, value) in first_context.into_iter() {
        new_context.insert(key, value);
    }
    // ...
}

Note into_iter() method which consumes the map, but returns an iterator of tuples with actual values instead of references.