rust - ¿Cómo actualizar-o-insertar en un Vec?

borrow-checker

Question

Estoy escribiendo una estructura de datos en Rust. Contiene una Vec de pares clave-valor. Al insertar en la estructura, necesito encontrar una clave coincidente y actualizar tanto la clave como el valor (que en realidad es un puntero secundario). El código se parece un poco a esto, donde pivots es una ref mut de Vec<Pivot> y Pivot es solo una estructura con dos campos:

match pivots.iter_mut().find(|ref p| key <= p.min_key) { // first mutable borrow
Some(ref mut pivot) => {
// If there is one, insert into it and update the pivot key
pivot.min_key = key;
pivot.child.insert(key, value) // recursive call
},
// o/w, insert a new leaf at the end
None => pivots.push(Pivot /* ... */) // second mutable borrow
}

Pero hay un problema. Aunque no uso el iterador mutable en el segundo brazo de la match , el verificador de préstamos se queja de que "no puedo pedir prestado *pivots como mutables más de una vez a la vez".

Esto tiene mucho sentido para mí, porque el primer préstamo todavía está en el alcance, a pesar de que no se usa en ese caso del match . Es un poco incómodo: un corrector más inteligente ciertamente podría decir que los préstamos no se superponen. He visto a alguien en línea que aconseja utilizar el retorno temprano para evitar el problema, como este:

match pivots.iter_mut().find(|ref p| key <= p.min_key) {
Some(ref mut pivot) => {
pivot.min_key = key;
pivot.child.insert(key, value);
return
},
None => ()
};
pivots.push(Pivot /* ... */)

pero esto parece difícil de entender, especialmente cuando significa dividir este código en su propia función para permitir el return . ¿Hay alguna forma más idiomática de realizar la operación de actualización o inserción?

Answer 1

Hay una "vida útil no léxica" combinada de RFC que resuelve esto a largo plazo. Usando las vidas no léxicas en Rust 2018, disponibles en Rust 1.31, su código funciona como está:

Playground

use std::collections::HashMap;
pub struct Pivot {
pub min_key: u64,
pub child: HashMap<u64, ()>,
}
fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
match pivots.iter_mut().find(|ref p| key <= p.min_key) {
Some(pivot) => {
// If there is one, insert into it and update the pivot key
pivot.min_key = key;
pivot.child.insert(key, value);
return;
}
// o/w insert a new leaf at the end
None => {
let mut m = HashMap::new();
m.insert(key, value);
pivots.push(Pivot {
min_key: key,
child: m,
});
}
}
}
fn main() {
let mut pivots = Vec::new();
update_or_append(&mut pivots, 100, ());
}

Si esto no funciona para su código, consulte

• ¿Devolver una referencia de un HashMap o Vec hace que un préstamo dure más allá del alcance en el que se encuentra?

Antes de Rust 2018, puede solucionarlo con un control de flujo de control adicional.

Puede hacer que su coincidencia produzca un valor bool independientemente de si la actualización se realizó o no, y tener un bloque condicional a continuación utilizando ese valor para agregar. Considero poner la lógica de "actualizar o agregar" en una función separada (usando el return después de la actualización) el enfoque más idiomático:

Playground

use std::collections::HashMap;
pub struct Pivot {
pub min_key: u64,
pub child: HashMap<u64, ()>,
}
fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
if let Some(pivot) = pivots.iter_mut().find(|ref p| key <= p.min_key) {
// If there is one, insert into it and update the pivot key
pivot.min_key = key;
pivot.child.insert(key, value);
return;
}
// otherwise insert a new leaf at the end
let mut m = HashMap::new();
m.insert(key, value);
pivots.push(Pivot {
min_key: key,
child: m,
});
}
fn main() {
let mut pivots = Vec::new();
update_or_append(&mut pivots, 100, ());
}

Usando un bool para rastrear si la actualización ocurrió

Playground

use std::collections::HashMap;
pub struct Pivot {
pub min_key: u64,
pub child: HashMap<u64, ()>,
}
fn update_or_append(pivots: &mut Vec<Pivot>, key: u64, value: ()) {
let updated = match pivots.iter_mut().find(|ref p| key <= p.min_key) {
Some(pivot) => {
// If there is one, insert into it and update the pivot key
pivot.min_key = key;
pivot.child.insert(key, value);
true
}
// o/w insert a new leaf at the end below
None => false,
};
if !updated {
let mut m = HashMap::new();
m.insert(key, value);
pivots.push(Pivot {
min_key: key,
child: m,
});
}
}
fn main() {
let mut pivots = Vec::new();
update_or_append(&mut pivots, 100, ());
}

Answer 2

Parece que la mejor manera de hacer esto es usar el índice en lugar de un iterador.

match pivots.iter().position(|ref p| key <= p.min_key) {
Some(i) => {
// If there is one, insert into it and update the pivot key
let pivot = &mut pivots[i];
pivot.min_key = key;
pivot.child.insert(key, value)
},
// o/w, insert a new leaf at the end
None => pivots.push(Pivot /* ... */)
}

De esta manera, no hay necesidad de iter_mut . Todavía no estoy del todo contento con esta alternativa, porque significa usar un índice explícito en lugar de un iterador. Esto está bien para un Vec pero no funcionaría para un contenedor con una estructura que no tiene O (1) indexación de acceso aleatorio.

Acepto una respuesta diferente que me permite evitar usar un índice.