How to update-or-insert on a Vec?

Solution 1:

There is a merged RFC "non-lexical lifetimes" which solves this in the long run. Using the non-lexical lifetimes in Rust 2018, available in Rust 1.31, your code works as-is:

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, ());
}

If this doesn't work for your code, check out

• Returning a reference from a HashMap or Vec causes a borrow to last beyond the scope it's in?

Before Rust 2018, you can workaround it with some additional control flow handling.

You could have your match produce a bool value whether the update happened or not, and have a conditional block below using that value to append. I consider putting the "update-or-append" logic into a separate function (using return after the update) the more idiomatic approach:

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, ());
}

Using a bool to track whether the update happened:

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, ());
}

Solution 2:

It seems like the best way to do this is to use the index instead of an iterator.

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 /* ... */)
}

This way, there's no need for iter_mut. I'm still not entirely happy with this alternative, because it means using an explicit index instead of an iterator. This is fine for a Vec but wouldn't work for a container with a structure that doesn't have O(1) random-access indexing.

I'd accept a different answer that lets me avoid using an index.