在使用sort_by_key对向量进行排序时，为什么不能使用返回引用的键函数? [英] Why can't I use a key function that returns a reference when sorting a vector with sort_by_key?

问题描述

我正在尝试使用键函数对Vec<String>进行排序，该键函数返回对向量中字符串的引用.一个人为的例子是将身份函数用作关键函数(这当然没用，但这是重现我的问题的最小例子):

I'm trying to sort a Vec<String> using a key function that returns references to the strings in the vector. A contrived example is to use the identity function as key function (which of course is useless, but it's the minimal example to reproduce my problem):

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

现在给定items: Vec<String>，我希望能够做到

Now given items: Vec<String>, I'd like to be able to do

items.sort_by_key(key);

这会出现以下错误:

error[E0271]: type mismatch resolving `for<'r> <fn(&std::string::String) -> &std::string::String {main::key} as std::ops::FnOnce<(&'r std::string::String,)>>::Output == _`
  --> src/main.rs:19:11
   |
19 |     items.sort_by_key(key);
   |           ^^^^^^^^^^^ expected bound lifetime parameter, found concrete lifetime
   |
   = note: concrete lifetime that was found is lifetime '_#16r

我不明白为什么会收到此错误，因此我试图对此进行跟踪.我首先实现了自己的sort_by_key()版本:

I don't understand why I get this error, so I tried to track this down. I first implemented my own version of 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)));
}

尝试调用此函数时，出现类似相反"的错误:

When trying to call this function, I get what looks like the "opposite" error:

error[E0308]: mismatched types
  --> src/main.rs:22:29
   |
22 |     sort_by_key(&mut items, key);
   |                             ^^^ expected concrete lifetime, found bound lifetime parameter
   |
   = note: expected type `fn(&std::string::String) -> _`
              found type `fn(&std::string::String) -> &std::string::String {main::key}`

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

I can make this code compile by fixing the key type to &T instead of using the generic parameter K, or by using &K instead of K as return type for the key function:

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)));
}

我还尝试添加了生命周期注释，但这只是转移了错误，而没有解决它.

I also tried adding lifetime annotations, but that only shifted the error around without resolving it.

这是操场上sort_by_key()函数的三个版本.

Here's the three versions of the sort_by_key() function on the Playground.

为什么会出现这些错误?在保持键类型K完全通用的同时，有什么方法可以解决这些问题?

Why am I getting these errors? Is there any way to fix them while keeping the key type K completely generic?

推荐答案

现在，您必须使用长"格式:

For now, you have to use the "long" form:

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

为什么会出现这些错误?有什么办法可以解决它们?

Why am I getting these errors? Is there any way to fix them?

起因和解决方法是相同的:Rust目前表现得不足以表示您想要的东西.所需的功能称为 通用关联类型(GAT)；以前称为关联类型构造器(ATC)或更高类型的类型(HKT).

The cause and fix are one-and-the same: Rust is simply not currently expressive enough to represent what you want. The feature needed is called generic associated types (GATs); previously known as associated type constructors (ATCs) or higher-kinded types (HKTs).

来自相关问题:

为使sort_by_key调用正常，需要将输入引用的生存期合并到B中以使返回类型为&'a str，但是B是类型参数.

For the sort_by_key call to be okay, the lifetime of the input reference [...] needs to be incorporated into B to make the return type &'a str, but B is a type parameter.

我不知道sort_by_key的签名在实施时是否能够无缝地移动到GAT.

I don't know if the signature for sort_by_key will be able to be seamlessly moved to a GAT when they are implemented.

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

In similar cases where you control the signature of all the types, you can require that a reference be returned:

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);
}

这是不理想的，因为现在您不能返回非参考，但是在实施GAT之前根本没有完整的解决方案.根据情况，您也许可以添加sort_by和sort_by_key之类的并行方法.

This is non-ideal because now you cannot return a non-reference, but there's simply no complete solution until GATs are implemented. You may be able to add a parallel methods like sort_by and sort_by_key, depending on your case.

这篇关于在使用sort_by_key对向量进行排序时，为什么不能使用返回引用的键函数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！