algorithm - 试图取消引用 `&` 指针

Question

出于学习目的，我正尝试在 Rust 中编写 kmeans 的 naif 实现。其中一个步骤如下:我有一个积分收藏xs和另一个点集合centroids .我想对 xs 进行分组基于质心中最近的邻居。也就是说，如果两个点有一个共同的最近邻，则它们属于同一组。

例如在 Scala 中这看起来像

xs groupBy { x => closest(x, centroids) } values 

找不到 groupBy标准库中的方法，我尝试将其编写如下(假设定义了 Point 和 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
}

我已经评论了中心部分，因为我在创建 TreeMap<Point, Vec<Point>> 时已经遇到问题并将其值作为 Vec<Vec<Point>> 返回.有一种方法values在 TreeMap 上，它返回类型为 Map<...> 的迭代器.我试过:

• 直接返回迭代器，但 Rust 提示说我必须添加一个生命周期说明符，我不确定要使用哪个
• 将其收集到 Vec 中.问题是迭代器的元素实际上是指向 Vec<Point> 的指针。 ，所以我必须做类似 let result: Vec<& Vec<Point>> = groups.values().collect(); 的事情.同样，Rust 不会让我返回那些指针，因为它们的生命周期太短了
• 取消引用所有这些指针，如上所示。我认为这是正确的方法，但 Rust 告诉我 error: cannot move out of dereference of &-pointer

返回该 map 值的正确方法是什么？

此外，如果我对中心部分进行反注释，Rust 会阻止我执行 groups.insert(y, vec![*x]);因为groups在模式匹配中被本地借用为不可变引用。我该如何解决这个问题？

Answer 1

您的第一个问题是 values() 返回一个对象，该对象提供到 TreeMap 的不可变投影，但您正试图在 map 调用中将数据移出它。

两种可能的解决方案是: 1)您创建向量的副本。然而，这是昂贵的操作。

let result: Vec<Vec<Point>> = groups.values().map(|x| x.clone()).collect();

2) 您使用 into_iter() 方法来消耗 TreeMap ，您可以自由地将数据移出它。

let result: Vec<Vec<Point>> = groups.into_iter().map(|(p, v)| v).collect();

那么，注释的代码有两个问题。

首先，您必须获得对找到的项目的可变引用，因此您必须调用 find_mut() 而不是 find()。

其次，在 None 分支中，您试图插入到已经借用的 TreeMap 中(通过 find()/find_mut() 调用的结果)。 Rust 不会让你。目前，唯一的选择是在匹配 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]);
  }

编辑:在新版本的 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]); }
};