Subvector instead of slice

Hi, I've got code for inserting elements of a vector called list into a tree. It splits the vector in half for the left and right node like:

let len = list.len();
left = Rc::new(BvhNode::new(&mut list[0..len / 2].to_vec()));
right = Rc::new(BvhNode::new(&mut list[len / 2..].to_vec()));

I do this by taking slices and convert them back with to_vec(). I'm assuming there's overheard doing vector->slice->vector so would it be possible to skip the slicing part and just get the subvector in one go? :thinking:

The underlying allocator probably wouldn't be fine with you trying to split a single allocation in two separate ones (Vec will always deallocate) so you'd either have to stick to this, or shrink the original vector and reuse it.

This function will take the second half of a vector into a new vector.

fn take_half<T>(v: &mut Vec<T>) -> Vec<T> {
    let half = v.len() / 2;
    v.drain(half..).collect()
}

You cannot just split a Vec in half the way you can a slice, because the Vec has to manage its own allocation and excess space, and can change sizes freely.

Given that you're taking references to temporary vectors, though, I don't think what you're doing is actually what you want. If the nodes don't own their slices, they should probably be slices, and if they do own their slices, they should probably own a Vec.

Why does BvhNode::new need &mut Vec<T> (instead of something like &mut [T])?

1 Like

If you do need a new vector for each half, you can use Vec::split_off. But I'd be curious to see what the new function does, and if it could be changed not to require a Vec.

2 Likes

Thanks all! The info on Vec<T> makes sense and there's no particular reason the type couldn't be &mut [T] too. Switching to slice types ran without a fuss. I was surprised to find that a &mut [T] type would accept a &mut Vec<T> too.

For context, I define my BVH node here where it runs recursively to ultimately create a binary search tree to check for rays hitting objects:

I've been learning rust by writing a raytracer through a really good guide/book. The language it uses is C++ although, so figuring out what might be idiomatic rust has been an ongoing problem.

For completeness: This feature is called “deref coercions”, and is explained in The Book here: https://doc.rust-lang.org/1.29.0/book/2018-edition/ch15-02-deref.html#implicit-deref-coercions-with-functions-and-methods

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.