string - 在 Rust hashmap 中分配/实例化字符串/向量的向量？

Question

我正在尝试从头开始在 Rust 中实现一个玩具 HashMap ，但在实际初始化我需要的桶时遇到了困难。我已经使用一系列桶和其他原语(如 u8)(在下面的代码片段中的评论中显示)。

我想不通的是如何告诉编译器给我分配一个包含其他向量的可变向量——在本例中，~str .此代码编译，但在运行时失败并显示 index out of bounds错误。

static DEFAULT_NUMBER_OF_BUCKETS: uint = 64;
static DEFAULT_VALUE_LENGTH: uint = 32; //unused

struct NaiveHashMap {
    hashmap_size: uint, //unused.
    string_capacity: uint, //unused.
    //contents: ~[ u8 ]
    contents: ~[ ~str ]
}

impl NaiveHashMap {

    fn new(hash_size: uint, string_size: uint) -> NaiveHashMap {
        NaiveHashMap {
            hashmap_size: hash_size, //unused
            string_capacity: string_size, //unused
            //contents: ~[ 0, ..DEFAULT_NUMBER_OF_BUCKETS ]
            contents: std::vec::with_capacity::<~str>(DEFAULT_NUMBER_OF_BUCKETS)
        }
    }

    fn get_hash(&self, key: &str) -> u32 {
        let hash: u32 = jenkins_hash(key);
        hash % self.hashmap_size.to_u32().unwrap()
    }

    //fn add(&mut self, key: &str, value: u8) {
    fn add(&mut self, key: &str, value: ~str) {
        let bucket = self.get_hash(key);
        self.contents[bucket] = value;
    }

    //fn get(self, key: &str) -> u8 {
    fn get(&self, key: &str) -> ~str {
        let bucket = self.get_hash(key);
        self.contents[bucket].clone()
    }

}

如果没有调用不安全的 from_buf 分配或只是复制粘贴 std Hashmap 库，我不确定如何继续。

我意识到传递 <T> 是更好的做法围绕类进行，因此它会很灵活，但更愿意先弄清楚这一点。

编辑:修改了 get() 以避免捕获整个结构。

Answer 1

据我了解，您想构造一个给定长度的向量，以按索引向其中写入内容。

除非您为向量的每个元素指定默认值，否则您无法在 Rust 中安全地执行此操作。它与 ~[u8] 一起工作，因为您确实指定了默认值(零)，并且因为 u8 是隐式可复制的:

[0, ..DEFAULT_NUMBER_OF_BUCKETS]

但是您期望 ~str 的默认值是多少？它是一个指针，在 Rust 中指针不能等于 null，这本来是指针最自然的默认值。我认为 ~str 的下一个最自然的值是 ~""，即空字符串。您可以使用它来创建一个包含 N 个字符串的向量:

vec::from_elem(N, ~"")

这将创建一个空盒装字符串向量。但这也意味着 N 分配，不是你应该不考虑就做的事情。

但是，您不能对任意类型 T 执行此操作，因为通常任意类型 T 没有任何默认值。此外，任意T 也可能无法Clone，这是from_elem() 所要求的。但是您可以从 T 创建另一种类型，它确实具有默认值。您为此使用 Option:

contents: ~[Option<T>]

为了克服不可克隆性，您可以使用带有闭包的 from_fn() 函数:

contents: vec::from_fn(N, |_| None)

顺便说一句，它因“索引越界”错误而失败的原因是因为您正在使用 with_capacity() 函数。此函数创建一个零长度但具有指定容量的向量。您可以在 vector 上使用 push() 方法将元素附加到它的末尾，并且在达到其容量之前不会重新分配它，但是您不能访问 vector 的“外部”元素添加的。