如何实现不消耗密钥的类似于 HashMap::entry 的功能？

Question

我正在尝试实现类似于 HashMap::entry 但不允许使用密钥的东西（参见 this RFC with a similar purpose). Here is my code, modeled after the Index impl for HashMap (See this and this）。

use std::collections::HashMap;
use std::hash::{Hash, BuildHasher};
use std::borrow::Borrow;

trait MapExt<Q: ?Sized, V> {
    fn get_or_insert(&mut self, key: &Q, value: V) -> &V;
}

impl<'a, Q: ?Sized, K, V, S> MapExt<&'a Q, V> for HashMap<K, V, S>
where
    K: Eq + Hash + Borrow<Q>,
    Q: Eq + Hash + ToOwned,
    S: BuildHasher,
{
    fn get_or_insert(&mut self, key: &Q, value: V) -> &V {
        if !self.contains_key(key) {
            self.insert(key.to_owned(), value);
        }
        self[key]
    }
}

这给了我以下错误。

error[E0053]: method `get_or_insert` has an incompatible type for trait
  --> src/main.rs:15:42
   |
6  |         fn get_or_insert(&mut self, key: &Q, value: V) -> &V;
   |                                          -- type in trait
...
15 |         fn get_or_insert(&mut self, key: &Q, value: V) -> &V {
   |                                          ^^ expected reference, found type parameter
   |
   = note: expected type `fn(&mut std::collections::HashMap<K, V, S>, &&'a Q, V) -> &V`
              found type `fn(&mut std::collections::HashMap<K, V, S>, &Q, V) -> &V`

这里有什么问题，我该如何解决？

另外一个我觉得会出现的问题是编译器不知道Q::Owned是不是K。如果是，我们如何处理？

Answer 1

我也是一个比较新手，但是从我看来有以下三个问题：

MapExt<&'a Q, V>

应该是

MapExt<Q, V>

否则你正在将特征类型更改为参考。

Q: Eq + Hash + ToOwned,

应该明确

Q: Eq + Hash + ToOwned<Owned=K>,

以便它知道 to_owned() 将 return.

的类型

和

self[key]

应该是

&self[key]

Answer 2

你的问题可以简化为：

trait Alpha<A> {
    fn alpha(&self, key: &A);
}

impl<'a, A> Alpha<&'a A> for () {
    fn alpha(&self, key: &'a A) {}
}

基本上，您是在混淆泛型类型。使用单独的字母更清楚：

impl<'a, B> Alpha<&'a B> for () {}

也就是说，Alpha的A的值实际上是&'a B。然后 trait 表示它引用了那个值。一个有效的实现是：

impl<'a, B> Alpha<&'a B> for () {
    fn alpha(&self, key: &&'a B) {}
}

一旦你理解了这一点，你就可以按照解决实施中的剩余问题。

如何实现不消耗密钥的类似于 HashMap::entry 的功能？

How do I implement a function similar to HashMap::entry that doesn't consume the key?

generics

traits

rust