rust - 如何按字符串字段对结构的 Vec 进行排序？

Question

我在通过 String 字段进行看似微不足道的排序时遇到了困难。复述如下:

struct Dummy {
    x: String,
    y: i8
}

fn main() {
    let mut dummies: Vec<Dummy> = Vec::new();
    dummies.push(Dummy { x: "a".to_string(), y: 1 });
    dummies.push(Dummy { x: "b".to_string(), y: 2 });

    dummies.sort_by_key(|d| d.x); // error[E0507]: cannot move out of borrowed content
    dummies.sort_by_key(|d| d.y); // This is fine
}

有人可以解释一下到底出了什么问题以及如何解决吗？

Answer 1

首先，让我们看看您的原始错误消息，然后我们将进行一些修复并尝试了解所有内容。

在 dummies.sort_by_key(|d| d.x); 中使用的闭包中， d 是对 Dummy 实例的引用。但是，字段访问 d.x 是 String 本身。如果你想返回那个 String ，你必须把它的所有权交给任何称为闭包的东西。但是由于 d 只是一个引用，您不能传递其数据的所有权。

一种简单的解决方法是简单地将字符串克隆为 dummies.sort_by_key(|d| d.x.clone()); 。这会在将字符串返回到闭包之前复制它(这是 Andra 的解决方案)。这工作得很好，但如果性能或内存使用是一个问题，我们可以避免克隆。

这里的想法是使用字符串作为键是浪费的。真的，我们只需要知道两个字符串中哪个更小。如果我们使用字符串作为键，那么每次排序函数需要比较两个 Dummy 时，它​​都会调用每个的键函数，并将字符串传递给一个(非常短的)函数来简单地比较它们。如果我们在与借用相同的上下文中进行比较，我们将能够简单地传递比较的结果，而不是字符串。

解决方案是切片上的 sort_by 方法。这允许我们引用两个 Dummy 并决定一个是否小于另一个。例如，我们可以像 dummies.sort_by(|d1, d2| d1.x.cmp(&d2.x)); (full example here) 一样使用它

附录

为什么我们不能在不克隆 sort_by_key 的情况下使用 String ？当然，必须有一些聪明的方法来使用字符串切片和生命周期来做到这一点。

我们来看看the sort_by_key function.的签名

pub fn sort_by_key<K, F>(&mut self, f: F) where
    F: FnMut(&T) -> K,
    K: Ord, 

这个函数有趣的部分不是有什么，而是没有什么。类型参数 K 不依赖于传递给 f 的引用的生命周期。

当切片被排序时，key 函数会被重复调用并引用 Dummy 实例。由于切片在每次调用之间稍微排序，引用的生命周期必须非常短。如果它更长，它会在下一次移动切片元素时失效。但是，K 不能依赖于那个生命周期。这意味着无论我们的关键函数是什么，它都不能返回依赖于 Dummy 当前位置的任何内容(例如字符串切片、引用或任何其他巧妙的构造1)。

然而，我们可以让 K 依赖于传递给它的任何东西的生命周期。这里的想法是所谓的 Higher-Rank Trait Bounds 。这些目前仅适用于生命周期(尽管理论上它们可以扩展到所有类型参数)。我们可以提出另一个带有签名的切片方法

fn sort_by_key_hrtb<T, F, K>(slice: &mut [T], f: F)
where
    F: Fn(&T) -> &K,
    K: Ord,

为什么这会使事情起作用？在 F: Fn(&T) -> &K, 中，输出引用的生命周期隐含地与输入引用的生命周期相同(或长于)。脱糖，这是 F: for<'a> Fn(&'a T) -> &'a K, ，它表示 f 应该能够获取具有任何生命周期 'a 的引用并返回具有生命周期(大于或等于) 'a 的引用。现在我们有一个方法可以完全按照您想要的方式使用它(讨厌的 & 2 除外)。 (playground link)

实际上，有一种(不安全的)聪明的构造可能有效，但我还没有对其进行审查。您可以在指向 String 的原始指针周围使用包装器，然后为该包装器使用 impl Ord 以便它取消引用该指针以进行比较。3 键函数的返回类型将是 *const String ，因此我们不需要任何生命周期。但这本质上是不安全的，我绝对不会推荐它。一个(可能)工作示例是 here 。

我们需要在这里使用 &mut dummies 的唯一原因是 sort_by_key_hrtb 实际上并不是一个切片方法。如果是这样， dummies 将被自动借用并取消引用到切片中，因此我们可以像 dummies.sort_by_key_hrtb(|d| &d.x); 一样调用该函数。

为什么是包装器而不是指针？ *const T 实现了 Ord ，但它通过比较地址而不是底层值(如果有)来实现，这不是我们在这里想要的。