Splitting a boxed slice in two owned halves

user_774236 0
Viewed 362

My problem

I have a boxed slice s: Box<[Something]> that I would like to split into two owned halves, e.g., s1: Box<[Something]> containing the first s.len()/2 elements of s, and s2: Box<[Something]> containing the rest.

With Vecs

I know something along these lines can be achieved if s: Vec<Something>, using s.split_off(). However, what split_off does is it creates a new t: Vec<Something>, moves s.len()/2 elements from s to t, then shrinks s. While this obviously works, it does not feel very efficient.

Unsafely speaking

If I were writing in C, what I would is just take a pointer to the middle of s, call it t and unsafely ride into the sunset. I am wondering if something like this can be done in Rust too.

(One issue that I see with the above C-style approach is that, while s can be freed, t cannot. So s and t would not be exactly the same, as one of the two would need to be freed, while the other should just be dropped. But, I could imagine this information being carried in some flag attached to s and t.)

rust slice vector split
2 Answers

You can't split Box<[T]> apart in place. Your C example seems to have undefined behaviour.

Imagine next split_in_place function:

let all = Box::new([1,2,3,4]);
let (left: Box<[i32]>, right: Box<[i32]>) = all.split_in_place(2);

println!("{:?}", left); // seems to be ok
std::mem::drop(left);
println!("{:?}", right); // undefined behaviour here. `left` was dropped, so the entire memory of the initial `Box` is dropped and `right` is an invalid pointer.

What you can do is use sub-slices of a slice:

let all = Box::new([1,2,3,4]);

let (left, right) = all.split_at(2);

println!("{:?}", left); // [1, 2]
std::mem::drop(left);
println!("{:?}", right); // [3, 4]

If you need to mutate parts, you can use split_at_mut:

let mut all = Box::new([1,2,3,4]);

let (left, right) = all.split_at_mut(2);

for i in left.iter_mut() {
  *i += 1;
  for j in right.iter_mut() {
    *j += *i; // you can borrow mutably both parts at the same time
  }
}

println!("{:?}", left);
std::mem::drop(left);
println!("{:?}", right);
user_141634220

You can't split a Box<[T]> in two Box<[T]>s. The allocator simply don't allow that.

You can however achieve something similar to what you want using Rc<[T]> (or Arc if needed). This approach is similar to your C-style using-a-flag approach, except that both parts of the slice share ownership.

Here is an example for non-mutable slices:

use core::ops::Deref;
use core::ops::Range;
use std::rc::Rc;

struct SharedSplitSlice<T> {
    range: Range<usize>,
    buffer: Rc<[T]>,
}

impl<T> Deref for SharedSplitSlice<T> {
    type Target = [T];
    
    #[inline(always)]
    fn deref(&self) -> &[T] {
        &self.buffer[self.range.clone()]
    }
}

fn split<T>(b: Box<[T]>, split_at: usize) -> (SharedSplitSlice<T>, SharedSplitSlice<T>) {
    let b = Rc::<[T]>::from(b);
    
    (
        SharedSplitSlice {
            range: 0..split_at,
            buffer: b.clone(),
        },
        SharedSplitSlice {
            range: split_at..b.len(),
            buffer: b,
        },
    )
}

fn main() {
    let b = vec![1, 2, 3, 4, 5].into_boxed_slice();
    
    let (h, t) = split(b, 2);
    
    println!("{:?}", &*h);
    println!("{:?}", &*t);
}
user_27338510
Related