为什么在使用sort_by_key对向量进行排序时，不能使用返回引用的关键函数？

Question

为什么在使用sort_by_key对向量进行排序时，不能使用返回引用的关键函数？

29

我正在尝试使用返回向量中字符串的引用的键函数对Vec<String>进行排序。一个人为的示例是使用身份函数作为键函数（当然是无用的，但这是复制我的问题的最小示例）：

fn key(x: &String) -> &String {
    x
}

fn example(items: Vec<String>) {
    items.sort_by_key(key);
}

这会产生以下错误：

error[E0308]: mismatched types
   --> src/lib.rs:6:11
    |
6   |     items.sort_by_key(key);
    |           ^^^^^^^^^^^ lifetime mismatch
    |
    = note: expected associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
               found associated type `<for<'r> fn(&'r String) -> &'r String {key} as FnOnce<(&String,)>>::Output`
    = note: the required lifetime does not necessarily outlive the empty lifetime
note: the lifetime requirement is introduced here

我不明白为什么会出现这个错误，所以我试图追踪它。我首先实现了自己的sort_by_key()函数：

fn sort_by_key<T, K: Ord>(a: &mut [T], key: fn(&T) -> K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

尝试调用此函数时，我遇到了一个看起来像“相反”的错误：

error[E0308]: mismatched types
 --> src/lib.rs:6:29
  |
6 |     sort_by_key(&mut items, key);
  |                             ^^^ one type is more general than the other
  |
  = note: expected fn pointer `for<'r> fn(&'r String) -> &String`
             found fn pointer `for<'r> fn(&'r String) -> &'r String`

我可以通过将键类型修复为 &T 而不是使用通用参数 K，或者使用 &K 作为键函数的返回类型来使此代码编译：

fn sort_by_key_v2<T: Ord>(a: &mut [T], key: fn(&T) -> &T) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

fn sort_by_key_v3<T, K: Ord>(a: &mut [T], key: fn(&T) -> &K) {
    a.sort_by(|x, y| key(x).cmp(&key(y)));
}

我也尝试添加生命周期注释，但仅仅是将错误转移，而没有解决它。

这里是 Playground 上 sort_by_key() 函数的三个版本。

为什么会出现这些错误？有没有办法在完全保持键类型 K 的通用性的同时解决这些错误？

- Sven Marnach

3个回答

3

正如@Shepmaster所解释的那样，您不能有一个sort_by_key函数来处理与key函数的返回类型相关的通用关联生命周期，但这里有一个变体，适用于始终返回引用的键函数：

fn sort_by_key_ref<T, F, K>(a: &mut [T], key: F) 
where
    F: Fn(&T) -> &K,
    K: ?Sized + Ord,
{
    a.sort_by(|x, y| key(x).cmp(key(y)));
}

您还可以记录密钥功能的生命周期要求：

    for<'a> F: Fn(&'a T) -> &'a K,

请查看Playground上的示例。

- Stefan

谢谢，我已经弄清楚了（请参见我的问题中的第三个版本）。我仍然想了解这些错误消息到底是什么意思。 - Sven Marnach

哦，完全错过了那个，抱歉。至少 ?Sized 部分增加了一些新内容 :) - Stefan

2

我认为最干净的解决方法是在Shepmaster的答案基础上构建的：

fn ref_key<T, K: Ord + ?Sized>(mut f: impl FnMut(&T) -> &K) -> impl FnMut(&T, &T) -> Ordering {
    move |a, b| f(a).cmp(f(b))
}

只需将 slice.sort_by_key(key) 转换为 slice.sort_by(ref_key(key)) 即可简单使用。

- Sabrina Jewson

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Shepmaster · Accepted Answer

目前，您必须使用“长”表单：

v.sort_by(|x, y| key(x).cmp(&key(y)));

为什么会出现这些错误？有没有办法修复它们？

原因和解决方案是一样的：Rust目前表达不了你想要的东西。所需的功能称为泛型关联类型(GATs); 以前称为关联类型构造器(ATCs)或高阶类型(HKTs)。

来自相关问题:

对于sort_by_key调用，输入引用的生命周期[...]需要并入B，使返回类型为&'a str，但B是类型参数。

我不知道sort_by_key的签名是否能在实现GAT时无缝移动。目前看来似乎不太可能，因为Fn*特性本身可能需要改变。

在类似情况下，如果您控制所有类型的签名，则可以要求返回引用：

use std::cmp::Ordering;

struct User {
    name: String,
}

fn compare_keys<T, R>(a: T, b: T, key: impl Fn(&T) -> &R) -> Ordering
where
    for<'a> &'a R: Ord,
{
    let ak = key(&a);
    let bk = key(&b);
    ak.cmp(&bk)
}

fn main() {
    let alice = User {
        name: String::from("alice"),
    };
    let bob = User {
        name: String::from("bob"),
    };

    compare_keys(alice, bob, |u| &u.name);
}

这种方式并不理想，因为现在你不能返回非引用类型，但在通用关联类型（GATs）实现之前，没有完美的解决方案。根据你的情况，可能可以添加类似于 sort_by 和 sort_by_key 的并行方法。