Como pesquisar e inserir em um HashMap de forma eficiente?

102

Eu gostaria de fazer o seguinte:

  • Procure uma Vecdeterminada chave e armazene-a para uso posterior.
  • Se não existir, crie um vazio Vecpara a chave, mas ainda mantenha-o na variável.

Como fazer isso de forma eficiente? Naturalmente, pensei que poderia 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
    }
};

Quando experimentei, encontrei erros 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

Acabei fazendo algo assim, mas não gosto do fato de ele realizar a pesquisa duas vezes ( map.contains_keye 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 uma maneira segura de fazer isso com apenas um match?

Yusuke Shinyama
fonte

Respostas:

119

A entryAPI foi projetada para isso. Na forma manual, pode 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)
};

Ou pode-se usar a forma mais breve:

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

Se defaultestiver OK / barato para calcular, mesmo quando não está inserido, também pode ser apenas:

map.entry(key).or_insert(default)
Huon
fonte
Obrigado por um rápido anser! Agora aprendi que devo examinar os documentos um pouco mais a fundo.
Yusuke Shinyama
22
o problema com a entrada () é que você sempre precisa clonar a chave. Existe uma maneira de evitar isso?
Pascalius
@Pascalius você poderia fazer seu tipo de chave &T(se as chaves sobreviverem ao mapa, por exemplo, strings estáticas) ou em Rc<T>vez de T- mas não é bonito em nenhum dos casos
kbolino
@Pascalius: você pode usar v.key()na expressão para default, e então obterá uma referência à chave como ela existe no mapa de hash, portanto, você pode evitar um clone desta forma
Chris Beck