Attempting to dereference `&` -pointer
I am trying to write a naive implementation of kmeans in Rust for educational purposes. One of the steps is as follows: I have a set of points xs
and another set of points centroids
. I want to group xs
based on nearest neighbor among centroids. That is, two points belong to the same group if they have a common nearest neighbor.
For example, in Scala it would look like
xs groupBy { x => closest(x, centroids) } values
Not finding the method groupBy
in the standard library, I tried to write it like below (it is assumed that Point
and closest
):
fn clusters(xs: & Vec<Point>, centroids: & Vec<Point>) -> Vec<Vec<Point>> {
let mut groups: TreeMap<Point, Vec<Point>> = TreeMap::new();
// for x in xs.iter() {
// let y = closest(*x, centroids);
// match groups.find(&y) {
// Some(mut val) => val.push(*x),
// None => {
// groups.insert(y, vec![*x]);
// },
// }
// }
let result: Vec<Vec<Point>> = groups.values().map(|x| *x).collect();
result
}
I commented out the central part because I already had problems creating TreeMap<Point, Vec<Point>>
and returning its values as Vec<Vec<Point>>
. There is a method values
on TreeMap that returns an iterator of the type Map<...>
. I tried:
- returns an iterator directly, but Rust complains that then I need to add a lifetime specifier and I'm not sure which one to use
- collect it in
Vec
. The problem is that the elements of the iterator are actually pointing toVec<Point>
, so I have to do something likelet result: Vec<& Vec<Point>> = groups.values().collect();
. Again, Rust won't let me return these pointers because they live too short. - dereferencing all those pointers as above. I think this is the right way, but Rust tells me
error: cannot move out of dereference of &-pointer
What is the correct way to return the values of this card?
Also, if I decompose the centerpiece, Rust discourages me from doing groups.insert(y, vec![*x]);
because it groups
is borrowed locally as an immutable reference in pattern matching. How can I fix this?
source to share
Your first problem is that values () returns an object that provides immutable projection in the TreeMap, but you are trying to move data out of it in a map call.
Two possible solutions: 1) You create a copy of the vector. This, however, is an expensive operation.
let result: Vec<Vec<Point>> = groups.values().map(|x| x.clone()).collect();
2) You are using in_iter () method which uses treemap and you are free to move data from it.
let result: Vec<Vec<Point>> = groups.into_iter().map(|(p, v)| v).collect();
Then there are two problems in the commented code.
First, you need to get a variable reference to the element found, so you must call find_mut () instead of find ().
Second, in the No branch, you are trying to insert into an already borrowed treemap (via the result of calling find () / find_mut ()). Rust won't let you. Currently the only option is to defer the insert after the match block:
let should_insert = match groups.find_mut(&y) {
Some(mut val) => {
val.push(*x);
false
}
None => {
true
},
};
if should_insert {
groups.insert(y, vec![*x]);
}
EDIT: There is a better way in newer versions of Rust:
use std::collections::btree_map::Entry;
match groups.entry(&y) {
Entry::Occupied(mut view) => { val.get_mut().push(*x); }
Entry::Vaccant(view) => { view.insert(vec![*x]); }
};
source to share
returns an iterator directly, but Rust complains that then I need to add a lifetime specifier and I'm not sure which one to use
The borrowing controller in this case saved you from error after use. Since you create the treemap locally in the function and don't move it anywhere, its elements are automatically destroyed after the function is executed. So it's actually good that the Rust compiler didn't let you return an iterator to a data structure that ceases to exist as soon as the function returns.
dereferencing all those pointers as above. I think this is the correct way, but Rust is telling me an error: cannot exit dereferencing & -pointer
Right. The situation is similar to this:
let mut mystrings = vec!["hello".to_string(), "world".to_string()];
let x = *mystrings.get(0);
Here you are getting the same error because you cannot transfer the first line from this vector. Keep in mind that moving is destructive. This means that the source will be invalid. But you really don't want to have a vector where the first object is in some invalid state. This is why Rust doesn't let you strip ticks from links. You can callclone
let x = mystrings.get(0).clone();
but that is probably not what you want either. Cloning vectors and strings is expensive. But you can use replace
like this:
let mut mystrings = vec!["hello".to_string(), "world".to_string()];
let x = ::std::mem::replace(mystrings.get_mut(0), String::new());
This moves the string from vector to x, moving the empty string into the vector as a replacement. This way, the String object in the vector remains valid. Something like this also works with vectors.
Another way to move things out of the collection is with a "move iterator" as PEPP suggested. He defeated me.
source to share