¿Cómo buscar e insertar en un HashMap de manera eficiente?

102

Me gustaría hacer lo siguiente:

  • Busque una Vecclave determinada y guárdela para su uso posterior.
  • Si no existe, cree un vacío Vecpara la clave, pero manténgalo en la variable.

¿Cómo hacer esto de manera eficiente? Naturalmente, pensé que podría usar match:

use std::collections::HashMap;

// This code doesn't compile.
let mut map = HashMap::new();
let key = "foo";
let values: &Vec<isize> = match map.get(key) {
    Some(v) => v,
    None => {
        let default: Vec<isize> = Vec::new();
        map.insert(key, default);
        &default
    }
};

Cuando lo probé, me dio errores como:

error[E0502]: cannot borrow `map` as mutable because it is also borrowed as immutable
  --> src/main.rs:11:13
   |
7  |     let values: &Vec<isize> = match map.get(key) {
   |                                     --- immutable borrow occurs here
...
11 |             map.insert(key, default);
   |             ^^^ mutable borrow occurs here
...
15 | }
   | - immutable borrow ends here

Terminé haciendo algo como esto, pero no me gusta el hecho de que realiza la búsqueda dos veces ( map.contains_keyy map.get):

// This code does compile.
let mut map = HashMap::new();
let key = "foo";
if !map.contains_key(key) {
    let default: Vec<isize> = Vec::new();
    map.insert(key, default);
}
let values: &Vec<isize> = match map.get(key) {
    Some(v) => v,
    None => {
        panic!("impossiburu!");
    }
};

¿Existe una forma segura de hacer esto con solo uno match?

Yusuke Shinyama
fuente

Respuestas:

119

La entryAPI está diseñada para esto. En forma manual, puede parecer

use std::collections::hash_map::Entry;

let values: &Vec<isize> = match map.entry(key) {
    Entry::Occupied(o) => o.into_mut(),
    Entry::Vacant(v) => v.insert(default)
};

O se puede utilizar la forma más breve:

map.entry(key).or_insert_with(|| default)

Si defaultestá bien / es barato de calcular incluso cuando no está insertado, también puede ser:

map.entry(key).or_insert(default)
huon
fuente
¡Gracias por una respuesta rápida! Ahora que he aprendido que debo mirar un poco más a fondo los documentos.
Yusuke Shinyama
22
el problema con entry () es que siempre tienes que clonar la clave, ¿hay alguna forma de evitar esto?
Pascalius
@Pascalius, podría hacer su tipo de clave &T(si las claves sobreviven al mapa, por ejemplo, cadenas estáticas) o en Rc<T>lugar de T, pero no es bonito en ninguno de los casos
kbolino
@Pascalius: puede usar v.key()en la expresión for default, y luego obtendrá una referencia a la clave tal como existe en el hashmap, por lo que puede evitar un clon de esta manera
Chris Beck