如何按字符串字段对结构的 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

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

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

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

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

解决方案是sort_by切片的方法。这允许我们引用两个Dummys 并确定一个是否小于另一个。例如，我们可以像这样使用它dummies.sort_by(|d1, d2| d1.x.cmp(&d2.x)); （完整示例在这里）

附录

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

让我们看看签名的sort_by_key功能。

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

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

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

但是，我们可以K依赖传递给它的任何东西的生命周期。这里的想法是所谓的高阶特质界限。这些目前仅适用于生命周期（尽管理论上它们可以扩展到所有类型参数）。我们可以提出另一个带有签名的切片方法

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。现在我们有一个方法可以完全按照您想要的方式使用它（讨厌的&²除外）。（游乐场链接）

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

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

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