Get slice of BTreeMap or similar solution

help
1

This is a "which data structure will work" question. I have a situation where I need to be able to insert an element by a numeric key, and then, grab a slice starting at a numeric key to the end.

An pseudo code example:

let data = [
        1 = String::from("One"),
        3 = String::from("Three"),
        12 = String::from("Twelve"),
        62 = String::from("Sixty Two"),
        91 = String::from("Ninety One"),
    ]

Where I could insert a new item, say 73, and it would be inserted between 62 and 91. Then, I can take a slice and grab a vector or other iterable collection from 12+.

let twelve_plus = &[12..];

Which would be a vector with three elements.

My first thought was to use vectors. And, I was able to insert into an empty vector

let mut data = vec![];
data[1] = String::from("One");
data[3] = String::from("Three");
// etc

But, I wasn't able to use the vector. I couldn't iterate or grab a range because I got a panic

thread 'main' panicked at 'index out of bounds: the len is 0 but the index is 1'

Which makes sense to me. I have considered the BTreeMap, which will allow for ordering and iteration, but I don't know how to get a slice from that.

The only other solution I can think of is to wrap the vector in a type, and implement my own insert method, which inserts an optional value of None as needed. So, the first insert of 1 would actually insert an empty value into 0 and then a good value into 1. This is acceptable, but I was hoping for a more elegant solution.

Am I missing something obvious? Thanks for the help!

2

You cannot use indexing assignment to insert values into a vector. You must use .push(), .insert(), or .extend(). This is very likely where the out-of-bounds error occurred.

Just curious, why do you require a slice? An iterator should be able to service the majority of needs.

The main property of a slice is that it represents a contiguous array of data, so almost certainly one of the following things will need to be true:

  • You can have O(n) insertion, and O(log n) work to obtain a slice. (This would be your idea of writing a wrapper around Vec)
  • You can have O(log n) insertion, and O(n) work to make it contiguous so that you may obtain a slice. That would basically mean collecting BTree's range iterator into a Vec:
let mut data = BTreeMap::new();
data.insert(1, String::from("One"));
data.insert(3, String::from("Three"));
// ...

// Get a Vec, which can coerce to a slice
let twelve_plus = data.range(12..).collect::<Vec<_>>();

(Edit: actually, I misread your idea. Your idea actually looks more like the second bullet rather than the first, just replacing BTreeMap with some sort of Vec-based "IntMap". This idea will still require collecting the elements into a new vector to make them contiguous if you want a slice)

3

Thank you for the quick and complete answer. That helps me understand what's happening quite a bit better.

I mis-typed. I had tried inserting into the vector with the insert() method. That produced a different error: thread 'main' panicked at 'assertion failed: index <= len', liballoc/vec.rs:848:9.

But you bring up a good point. I don't know that a slice is what I really need. Ultimately, all I need to do is send back a collection of the values in the range. I don't even actually need the keys. In the end, it will be serialized into a simple JSON array and sent through HTTP.

So, 12+ would result in ["Twelve", "Sixty Two", "Ninety One"]

Another caveat is that the elements may be inserted out of order, but need to be retrieved in order.

The BTreeMap example you gave worked. That's top so far.