# Get slice of BTreeMap or similar solution

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!

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)

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.