I'm creating a map-like data structure in which every value provides a means of retrieving its unique key via implementing a trait. The keys are expected to reference one or more fields of the corresponding value (or just reference stack data or whatever when created temporarily to e.g. look up a value in the map). The keys clearly need to be Ord for the data structure to work with them correctly. The data structure is currently implemented using a sorted vector.

我正在创建一个类似于映射的数据结构，其中每个值都提供了一种通过实现特征来检索其唯一键的方法。当临时创建关键字以例如在映射中查找值时，期望关键字引用相应值的一个或多个字段(或者仅引用堆栈数据等)。显然，键需要是Ord，数据结构才能正确使用它们。该数据结构目前是使用排序向量实现的。

I run into lifetime difficulties when I need to compare keys which have different lifetimes. For example, one key is a parameter and another key is from data already in the map, or one key is a parameter and another key is retrieved from a separate data value parameter. (In my real code I didn't run into this problem until I wrote a replace method corresponding to the latter example, but in the minimal repro I created for this question I'm also running into it for a simple get method which is more like the former example; I'm not sure why my original get method didn't run into this problem, I guess I changed something after I implemented it.)

当我需要比较具有不同生存期的密钥时，我会遇到终身困难。例如，一个键是参数，另一个键来自映射中已有的数据，或者一个键是参数，另一个键是从单独的数据值参数检索的。(在我的实际代码中，直到我编写了对应于后一个示例的Replace方法，我才遇到这个问题，但在我为这个问题创建的最小重现中，我还遇到了一个更像前一个示例的简单Get方法；我不确定为什么我的原始Get方法没有遇到这个问题，我想我在实现它之后进行了一些更改。)

Here's some stripped down code:

以下是一些精简的代码：

trait HasKey {
    type Key<'a>: Ord where Self: 'a;
    fn get_key<'a>(&'a self) -> Self::Key<'a>;
}

struct Data {
    id: String,
    // more data
}

#[derive(Ord, PartialOrd, Eq, PartialEq)]
struct DataKey<'a>(&'a str); // might also contain more fields

struct Map<T>(Vec<T>) where T: HasKey;

impl HasKey for Data {
    type Key<'a> = DataKey<'a>;
    fn get_key<'a>(&'a self) -> Self::Key<'a> {
        DataKey(&self.id)
    }
}

impl<T> Map<T> where T: HasKey {
    fn compare_keys<'a>(left: &T::Key<'a>, right: &T::Key<'a>) -> std::cmp::Ordering {
        left.cmp(right)
    }
    
    fn replace<'a>(&self, key: &T::Key<'a>, value: T) {
        Self::compare_keys(key, &value.get_key());
        // if keys are equal, replace old value with new value in place
        // otherwise remove key and insert value, moving only items in between
    }
}

fn main() {
    let m = Map(vec![
        // test data already sorted; normally Map constructor would sort it
        Data { id: "bar".to_string() },
        Data { id: "foo".to_string() },
    ]);
    m.replace(DataKey("foo"), Data { id: "foobar".to_string() })
}

The compiler complains as follows:

编译器抱怨如下：

error[E0597]: `value` does not live long enough
  --> src/main.rs:44:35
43 |     fn replace<'a>(&self, key: T::Key<'a>, value: T) {
   |                --                          ----- binding `value` declared here
   |                |
   |                lifetime `'a` defined here
44 |         Self::compare_keys(&key, &value.get_key());
   |                                   ^^^^^^^^^^^^^^^
   |                                   |
   |                                   borrowed value does not live long enough
   |                                   argument requires that `value` is borrowed for `'a`
...
47 |     }
   |     - `value` dropped here while still borrowed

After much consideration and troubleshooting, it finally dawned on me that the reason value is required to be borrowed for 'a is that compare_keys is using the same lifetime for both of its arguments, meaning that callers need to provide arguments with matching lifetimes. That is definitely not what I intended, so I try to rewrite compare_keys to accept arguments with different lifetimes:

经过反复考虑和故障排除，我终于意识到需要为a借用值的原因是Compare_Key对其两个参数使用相同的生存期，这意味着调用者需要提供具有匹配生存期的参数。这绝对不是我想要的，所以我尝试重写Compare_Key以接受具有不同生存期的参数：

    fn compare_keys<'a, 'b>(left: &T::Key<'a>, right: &T::Key<'b>) -> std::cmp::Ordering {
        left.cmp(right)
    }

Now the compiler effectively makes the same complaint about the call left.cmp(right), saying both that 'a must outlive 'b and that 'b must outlive 'a, so it suggests that I combine them into a single lifetime (i.e. go back to what I had before). At this point I realize that Ord requires PartialOrd<Self> and Eq (which in turn requires PartialEq<Self>), and I'm pretty sure that Self there includes any lifetime parameters, leading me to conclude that Ord is creating the restriction that I can only compare keys whose data references have the same lifetime.

现在，编译器实际上对调用left.cmp(右)提出了同样的抱怨，说‘a必须比’b‘生存时间长，’b‘必须比’a‘生存时间长，所以它建议我将它们组合成一个生命周期(即，回到我以前拥有的)。在这一点上，我意识到ord需要PartialOrd 和Eq(这反过来又需要PartialEq )，我非常确定那里的self包括任何生命周期参数，这使我得出结论，Ord正在创建一种限制，即我只能比较数据引用具有相同生命周期的键。

This is when I realize that Ord doesn't take a parameter like PartialOrd does, but as a workaround I try changing my trait so that it requires keys to be PartialOrd instead so that I can specify that the type to compare against can have a different lifetime, like so:

这时，我意识到Ord不像PartialOrd那样接受参数，但作为一种解决办法，我尝试更改我的特征，以便它需要键为PartialOrd，这样我就可以指定要比较的类型可以具有不同的生存期，如下所示：

trait HasKey {
    type Key<'a>: for<'b> PartialOrd<Self::Key<'b>> where Self: 'a;
    fn get_key<'a>(&'a self) -> Self::Key<'a>;
}

This requires me to provide my own PartialOrd and PartialEq implementations instead of relying on the default ones, but they're trivial and not a big deal. I also modify compare_keys to call partial_cmp instead of cmp and just unwrap the result. That finally makes the compiler happy.

这需要我提供自己的PartialOrd和PartialEq实现，而不是依赖默认的实现，但它们很琐碎，也不是什么大事。我还修改了COMPARE_KEYS，以调用PARTIAL_CMP而不是CMPs，并只解开结果。这最终使编译器感到高兴。

Playground with the initial code and the changes/fixes in comments.

包含初始代码和注释中的更改/修复的游乐场。

My questions:

我的问题：

1. Did I draw the right conclusion that the errors are effectively caused by Ord requiring the lifetime parameters of my key structures to match, or does this actually have some other problem that I missed (but that my workaround still resolves)?


2. Are there other/better solutions than I came up with? Is there a better way for me to define methods like replace? Is there a better way for me to express that keys need to have a total ordering with respect to their values but not their lifetimes?

Naively, I want Ord to take a generic parameter, but since Ord implies Eq then Eq would also need to take a generic parameter (or maybe not?.. though that feels weird), and I understand that that wouldn't really make sense since the whole point of Eq is to express that a thing will always equal itself (in addition to PartialEq requirements). I feel like there's some sort of gap here, but I can't quite express its definition, and that makes me think that there's something here that I'm either not seeing or not understanding well. What am I missing?

我天真地希望Ord接受泛型参数，但由于Ord暗示Eq，那么Eq也需要接受泛型参数(也可能不是？虽然这感觉很奇怪)，但我理解这并没有真正的意义，因为EQ的全部意义就是表示事物总是等于它自己(除了PartialEq要求之外)。我觉得这里有某种差距，但我不能很好地表达它的定义，这让我认为这里有一些我没有看到或没有很好理解的东西。我遗漏了什么？

Did I draw the right conclusion that the errors are effectively caused by Ord requiring the lifetime parameters of my key structures to match, or does this actually have some other problem that I missed (but that my workaround still resolves)?

Yes, you drew the right conclusions. Good work!

是的，你得出了正确的结论。干得好！

Are there other/better solutions than I came up with?

The reason it usually works without special attention is because of variance. When the type is covariant, we can shrink the lifetime, and so we pick the "lowest common denominator" lifetime to both and compare it. But generics associated types are always invariant over their parameters (meaning they cannot shrink or grow), since they may be used with invariant types. Unfortunately there isn't currently way to specify that it must be covariant. As I answered recently we can though provide a method that fills the place of what done automatically by covariance:

它通常在没有特别注意的情况下工作的原因是因为差异。当类型是协变的时，我们可以缩短生存期，因此我们为两者选择“最小公分母”的生存期并对其进行比较。但是泛型关联类型始终在其参数上是不变的(这意味着它们不能缩小或增长)，因为它们可以与不变类型一起使用。不幸的是，目前还没有办法指定它必须是协变的。正如我最近回答的那样，我们可以提供一种方法来填补由协方差自动完成的工作的位置：

trait HasKey {
    type Key<'a>: Ord
    where
        Self: 'a;
    fn get_key<'a>(&'a self) -> Self::Key<'a>;

    fn shrink_key_lifetime<'a: 'b, 'b, 'c>(key: &'c Self::Key<'a>) -> &'c Self::Key<'b>;
}

struct Map<T>(Vec<T>)
where
    T: HasKey;

impl HasKey for Data {
    type Key<'a> = DataKey<'a>;
    fn get_key<'a>(&'a self) -> Self::Key<'a> {
        DataKey(&self.id)
    }

    fn shrink_key_lifetime<'a: 'b, 'b, 'c>(key: &'c Self::Key<'a>) -> &'c Self::Key<'b> {
        key
    }
}

impl<T> Map<T>
where
    T: HasKey,
{
    fn compare_keys<'a>(left: &T::Key<'a>, right: &T::Key<'a>) -> std::cmp::Ordering {
        left.cmp(right)
    }

    fn replace<'a>(&self, key: &T::Key<'a>, value: T) {
        Self::compare_keys(
            T::shrink_key_lifetime(key),
            T::shrink_key_lifetime(&value.get_key()),
        );
        // if keys are equal, replace old value with new value in place
        // otherwise remove key and insert value, moving only items in between
    }
}

This allows you to use Ord as well as derive it. If you don't want the users to mess with this method, you can split the trait and have it in a supertrait and provide a macro to implement it.

这允许您使用Ord并派生它。如果您不想让用户搞砸这个方法，您可以拆分特征并将其放在一个上层特征中，并提供一个宏来实现它。