How to build a HashMap of Vectors in Rust?

Question

I'm a Rust newbie. I'm trying to represent a directed graph's adjacency list as a HashMap of char {vertex name} to Vector of (char,int) {vertex name, cost}. I want the final HashMap to be immutable, but I'd like to build up the vector and then not need to make a copy of it to make it immutable.

My code is below. At the indicated line I get "cannot borrow immutable dereference (dereference is implicit, due to indexing) as mutable". This makes sense, as the Vec<(char,int)> in the map is not mutable. But I'm not sure how to fix it.

Is there a way to do this in Rust?

pub struct Edge {
    to:     char,
    from:   char,
    weight: int
}

pub struct digraph {
    _vertices:  Vec<char>,
    _adj_list:  HashMap<char, Vec<(char,int)> >
}

impl digraph {
    pub fn new(nodes: &Vec<char>, edges: &Vec<Edge> ) -> Option<digraph> {
        let mut tmp_adj_list = HashMap::new();
        for node in (*nodes).iter() {
            tmp_adj_list.insert(*node, Vec::new());
        }
        for edge in (*edges).iter() {
            let Edge{ to: to, from:from, weight:weight } = *edge;
            if  !(*nodes).contains(&to) |  !(*nodes).contains(&from) {
                return None;
            }
            tmp_adj_list[from].push((to,weight))  // *********** error here
        }
        Some(digraph { _vertices: (*nodes).clone(), _adj_list: tmp_adj_list })
    }
}

Answer 1

Taking [] onto a HashMap is sugar for the (now deprecated) get(..) function, which declaration is :

fn get<'a>(&'a self, k: &K) -> &'a V

and returns a constant (&) reference. But the push(..) method of Vec expects a &mut reference, hence the error.

What you need is the get_mut(..) method of HashMap, which returns a &mut reference to the value.

Also, some minor points:

• when calling a method, dereference is automatic : (*foo).bar() is exactly the same as foo.bar()
• you can dereference automatically in your loop with for &edge in edges.iter() {...}

Including all this, your function becomes :

impl digraph {
    pub fn new(nodes: &Vec<char>, edges: &Vec<Edge> ) -> Option<digraph> {
        let mut tmp_adj_list = HashMap::new();
        for &node in nodes.iter() {
            tmp_adj_list.insert(node, Vec::new());
        }
        for &edge in edges.iter() {
            let Edge{ to: to, from:from, weight:weight } = edge;
            if  !nodes.contains(&to) |  !nodes.contains(&from) {
                return None;
            }
            tmp_adj_list.get_mut(&from).push((to,weight))
        }
        Some(digraph { _vertices: nodes.clone(), _adj_list: tmp_adj_list })
    }
}