为 HashMap 使用复杂键时如何避免临时分配? [英] How to avoid temporary allocations when using a complex key for a HashMap?

问题描述

我为 HashMap 使用了一个复杂的键，这样键由两部分组成，其中一部分是 String，我不知道该怎么做通过 HashMap::get 方法进行查找，而无需为每次查找分配新的 String.

I'm using a complex key for HashMap such that the key comprises two parts and one part is a String, and I can't figure out how to do lookups via the HashMap::get method without allocating a new String for each lookup.

这是一些代码:

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex {
    n: i32,
    s: String,
}

impl Complex {
    fn new<S: Into<String>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    // OK, but allocates temporary String
    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

问题在于最后的断言.它通过了，但它需要临时堆分配，因为我无法在不构造 String 的情况下构造 Complex.

The problem is with the final assertion. It passes, but it requires a temporary heap allocation because I cannot construct a Complex without constructing a String.

为了消除这样的临时分配，Rust 提供了 借用 trait，HashMap::get 方法使用了它.我了解如何使 Borrow 对简单的键起作用.例如，Rust 标准库的 PathBuf 在底层通过使用 std::mem::transmute 实现了 Borrow，但是我不知道如何使它适用于我的 Complex 类型:

To eliminate temporary allocations like this, Rust provides the Borrow trait, which the HashMap::get method makes use of. I understand how to make Borrow work for simple keys. For example, the Rust Standard Library's PathBuf implements Borrow<Path> by making use of std::mem::transmute under the hood, but I can't figure out how to make it work for my Complex type:

#[derive(Debug)]
struct Borrowable {
    // ??? -- What goes here? Perhaps something like:
    n: i32,
    s1: &str, // ??? -- But what would the lifetime be? Or maybe:
    s2: str,  // ??? -- But how would I extend this to a complex type
              //        containing two or more strings?
}

impl Borrowable {
    fn new(n: i32, s: &str) -> &Self {
         // ??? -- What goes here? It must not allocate.
        unimplemented!();
    }
}

impl std::borrow::Borrow<Borrowable> for Complex {
    fn borrow(&self) -> &Borrowable {
        // ??? -- What goes here? How can I transmute a Complex into a
        //        &Borrowable?
        unimplemented!();
    }
}

这似乎是一个常见的用例，我怀疑我遗漏了一些关于 Borrow 的重要信息，但我完全不知所措.

This seems like a common use case, and I suspect I'm missing something important about Borrow, but I'm at a total loss.

推荐答案

听起来你想要这个.

Cow 将接受 &str 或 String.

use std::borrow::Cow;

#[derive(Debug, Eq, Hash, PartialEq)]
struct Complex<'a> {
    n: i32,
    s: Cow<'a, str>,
}

impl<'a> Complex<'a> {
    fn new<S: Into<Cow<'a, str>>>(n: i32, s: S) -> Self {
        Complex { n: n, s: s.into() }
    }
}

fn main() {
    let mut m = std::collections::HashMap::<Complex<'_>, i32>::new();
    m.insert(Complex::new(42, "foo"), 123);

    assert_eq!(123, *m.get(&Complex::new(42, "foo")).unwrap());
}

关于生命周期参数的评论:

A comment about lifetime parameters:

如果你不喜欢生命周期参数并且你只需要使用 &'static str 或 String 那么你可以使用 Cow<'static, str> 并从 impl 块和结构定义中删除其他生命周期参数.

If you don't like the lifetime parameter and you only need to work with &'static str or String then you can use Cow<'static, str> and remove the other lifetime parameters from the impl block and struct definition.

这篇关于为 HashMap 使用复杂键时如何避免临时分配?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！