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.