CODEWITHSUNDEEP
stringvectorrust
ispilledthejava
ispilledthejava

Reputation: 193

Allocating/instantiating vector of strings/vectors in Rust hashmap?

I'm trying to implement a toy hashmap in Rust from scratch and getting snagged at actually initializing the buckets I need. I've gotten this working with an array of buckets with other primitives like u8 (shown in comments in snippet below).

What I can't figure out is how to tell the compiler to allocate me a mutable vector that holds other vectors--in this case, ~str. This code compiles, but fails at runtime with an index out of bounds error.

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()
    }

}

Short of calling an unsafe from_buf allocation or just copypasting the std Hashmap lib, i'm unsure how to proceed.

I realize that it'd be better practice to pass an <T> around the class so it'd be flexible, but prefer to figure this bit out first.

EDIT: revised the get() to avoid capturing the whole struct.

Upvotes: 3

Views: 1668

Answers (1)

Vladimir Matveev
Vladimir Matveev

Reputation: 128061

As far as I understand, you want to construct a vector of given length to write something into it by index.

You can't do this in Rust safely unless you specify default value for each element of the vector. It worked with ~[u8] because you did specify the default value (zero), and because u8 is implicitly copyable:

[0, ..DEFAULT_NUMBER_OF_BUCKETS]

But what default value you would expect for ~str? It is a pointer, and pointers can't be equal to null in Rust, which would have been the most natural default value for a pointer. The next most natural value for ~str, I think, is ~"", that is, an empty string. You can use it to create a vector of N strings:

vec::from_elem(N, ~"")

This will create a vector of empty boxed strings. But it also means N allocations, not something you should do without considering.

However, you can't do that with arbitrary type T, because in general arbitrary type T does not have any default value. Moreover, arbitrary T may also be not Cloneable, which is required by from_elem(). But you can create another type from T, which does have a default value. You use Option for this:

contents: ~[Option<T>]

To overcome non-cloneability, you can use from_fn() function with a closure:

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

BTW, the reason it fails with "index out of bounds" error is because you're using with_capacity() function. This function creates a vector of zero length but with the specified capacity. You can use push() method on the vector to append elements to the end of it, and it won't be reallocated until you have reached its capacity, but you cannot access elements "outside" of the added ones.

Upvotes: 6

Related Questions