rust - 在Rust中高效执行反向split_off操作

Question

我的用例涉及两个可变向量a和b和一个usize参数x。我要进行以下更改:

将元素b[0..x]附加到a的末尾(根据需要更改a的容量)

将b转换为b[x..]，而无需更改b的原始容量

目前，我正在执行以下操作:

while a.len() < x && !b.is_empty() {
    a.push(b.pop_front().unwrap());
    // here `b` is a VecDeque but I am happy to use a Vec if pop_front was not required
}

显然，这似乎是一个非常缓慢的操作，检查两个条件并在每次迭代时调用 unwrap。如果有一个 rev_split_off操作，它将非常好:

let mut front = b.rev_split_off(x);
a.append(&mut front);

在此， rev_split_off返回为切片 b[0..x]重新分配的向量，并将 b转换为容量不变的其余切片。
问题:如何在不使用 rev_split_off之类的情况下有效地执行用例？

Answer 1

好吧，我认为您将必须自己实现rev_split_off(即使我可能将其称为split_off_back也是一样的)。
这是我将如何实现它:

/// Moves the `i` first elements of `vec` at the end of `buffer`.
fn split_off_back<T>(vec: &mut Vec<T>, i: usize, buffer: &mut Vec<T>) {
    // We have to make sure vec has enough elements.
    // You could make the function unsafe and ask the caller to ensure
    // this condition.
    assert!(vec.len() >= i);

    // Reserve enough memory in the target buffer
    buffer.reserve(i);
    // Now we know `buffer.capacity() >= buffer.len() + i`.

    unsafe {
        // SAFETY:
        //  * `vec` and `buffer` are two distinct vectors (they come from mutable references)
        //     so their allocations cannot overlap.
        //  * `vec` is valid for reads because we have an exclusive reference to it and we
        //     checked the value of `i`.
        //  * `buffer` is valid for writes because we ensured we had enough memory to store
        //     `i` additional elements.
        std::ptr::copy_nonoverlapping(vec.as_ptr(), buffer.as_mut_ptr().add(buffer.len()), i);

        // Now the memory is moved.
        // we are not allowed to use it again from the `vec` vector.

        // We just extanded `buffer`, we need to update its length.
        // SAFEFY:
        //  * We ensured that the new length is less than the capacity (with `Vec::reserved`)
        //  * The vector is initialized for this new length (we moved the values).
        buffer.set_len(buffer.len() + i);

        // Now we need to update the first vector. The values from index `i` to its end
        // need to be moved at the begining of the vector.
        // SAFETY:
        //  * We have an exclusive reference to the vector. It is both valid for reads and writes.
        std::ptr::copy(vec.as_ptr().add(i), vec.as_mut_ptr(), i);

        // And update the length of `vec`.
        // SAFETY: This subtraction is safe because we previously checked that `vec.len() >= i`.
        vec.set_len(vec.len() - i);
    }
}

请注意，我将 buffer放在函数的参数中，以避免分配矢量。如果您希望使用与 split_off相同的语义，则可以执行以下操作。

fn split_of_back<T>(vec: &mut Vec<T>, i: usize) -> Vec<T> {
    assert!(vec.len() >= i);
    
    let mut buffer = Vec::with_capacity(i);

    unsafe { /* same thing */ }

    buffer
}