How to update-or-insert on a Vec?
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, ());
}
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.