制作使用项目字段作为键的查找表的惯用方法是什么? [英] What's the idiomatic way to make a lookup table which uses field of the item as the key?

问题描述

我有一个 Foo 的集合.

struct Foo {
    k: String,
    v: String,
}

我想要一个 HashMap，它有键 &foo.k 和值 foo.

I want a HashMap which has the key &foo.k and the value foo.

显然，不通过引入Rc或克隆/复制k来重新设计Foo是不可能的.

Apparently, it is not possible without redesigning Foo by introducing Rc or clone/copy the k.

fn t1() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashMap<&str, Foo> = HashMap::new();
    a.insert(&foo.k, foo); // Error
}

滥用 HashSet 中的 get() (游乐场):

There seems to be a workaround by abusing get() from HashSet (Playground):

use std::collections::{HashMap, HashSet};
use std::hash::{Hash, Hasher, BuildHasher};
use std::collections::hash_map::Entry::*;

struct Foo {
    k: String,
    v: String,
}

impl PartialEq for Foo {
    fn eq(&self, other: &Self) -> bool { self.k == other.k }
}

impl Eq for Foo {}

impl Hash for Foo {
    fn hash<H: Hasher>(&self, h: &mut H) { self.k.hash(h); }
}

impl ::std::borrow::Borrow<str> for Foo {
    fn borrow(&self) -> &str {
        self.k.as_str()
    }
}

fn t2() {
    let foo = Foo { k: "k".to_string(), v: "v".to_string() };
    let mut a: HashSet<Foo> = HashSet::new();
    a.insert(foo);
    let bar = Foo { k: "k".to_string(), v: "v".to_string() };
    let foo = a.get("k").unwrap();
    println!("{}", foo.v);
}

这很乏味.如果一个 Foo 有多个字段和不同的 Foo 集合来键入不同的字段怎么办?

This is pretty tedious. What if a Foo has multiple fields and different collections of Foo to key on different fields?

推荐答案

显然，不通过引入Rc或克隆/复制k来重新设计Foo是不可能的.

Apparently, it is not possible without redesigning Foo by introducing Rc or clone/copy the k.

这是正确的，不可能有 HashMap<&K, V> 键指向值的某个组件.

That's correct, it is not possible to have HashMap<&K, V> where the key points to some component of the value.

HashMap 拥有键和值，概念上将两者存储在大向量中.当一个新值被添加到 HashMap 中时，这些现有的值可能由于哈希冲突而需要移动或者向量可能需要重新分配以容纳更多项目.这两个操作都会使任何现有密钥的地址无效，使其指向无效内存.这会破坏 Rust 的安全保证，因此是不允许的.

The HashMap owns the key and the value, conceptually storing both in big vectors. When a new value is added to the HashMap, these existing values might need to be moved around due to hash collisions or the vectors might need to be reallocated to hold more items. Both of these operations would invalidate the address of any existing key, leaving it pointing at invalid memory. This would break Rust's safety guarantees, thus it is disallowed.

阅读为什么我不能在同一个结构中存储一个值和对该值的引用?讨论.

此外，trentcl 指出 HashMap::get_mut 将允许您获得对 键 的可变引用，这将允许您在没有映射的情况下更改键会心.正如文档所述:

Additionally, trentcl points out that HashMap::get_mut would allow you to get a mutable reference to the key, which would allow you to change the key without the map knowing. As the documentation states:

如果键的哈希值(由 Hash trait 确定)或其相等性(由 Eq trait 确定)在映射中发生变化，则修改键是一个逻辑错误.

It is a logic error for a key to be modified in such a way that the key's hash, as determined by the Hash trait, or its equality, as determined by the Eq trait, changes while it is in the map.

<小时>

解决方法包括:

---

Workarounds include:

• 从结构中删除密钥并单独存储.代替 HashMap<&K, V>，其中 V 是 (K, Data)，而是存储 HashMap.您可以返回一个将键和值的引用粘合在一起的结构(示例)

• Remove the key from the struct and store it separately. Instead of HashMap<&K, V> where V is (K, Data), store HashMap<K, Data>. You can return a struct which glues references to the key and value together (example)

使用 Rc 共享密钥的所有权(示例)

Share ownership of the key using Rc (example)

使用Clone 或Copy 创建重复键.

Create duplicate keys using Clone or Copy.

像您一样使用 HashSet，由 Sebastian Redl 的建议增强.HashSet 实际上只是一个 HashMap，因此通过将所有所有权转移到密钥来工作.

Use a HashSet as you have done, enhanced by Sebastian Redl's suggestion. A HashSet<K> is actually just a HashMap<K, ()>, so this works by transferring all ownership to the key.

这篇关于制作使用项目字段作为键的查找表的惯用方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！