在Vec的中间或开头有效插入或替换多个元素？

Question

是否有任何直接的方法在线性时间内&[T]和/或Vec<T>中间或开始处插入或替换多个元素Vec？

我只能找到std::vec::Vec::insert,但这只是为了O(n)及时插入一个元素,所以我显然无法在循环中调用它.

我可以split_off在那个指数上做一个extend新的元素进入左半部分,然后extend是下半部分进入第一个,但有更好的方法吗？

Answer 1

从Rust 1.21.0开始,Vec::splice可以在任何时候插入,包括完全预先插入:

let mut vec = vec![1, 5];
let slice = &[2, 3, 4];

vec.splice(1..1, slice.iter().cloned());

println!("{:?}", vec); // [1, 2, 3, 4, 5]

文档说明:

注4:如果符合以下条件,则最佳:

• 尾部(范围后向量中的元素)为空
• 或者replace_with产生的元素少于范围长度
• 或者它的下限size_hint()是准确的.

在这种情况下,切片迭代器的下限应该是精确的,因此它应该执行一次内存移动.

splice 它更强大,它允许您删除一系列值(第一个参数),插入新值(第二个参数),并可选择获取旧值(调用的结果).

替换一组项目

let mut vec = vec![0, 1, 5];
let slice = &[2, 3, 4];

vec.splice(..2, slice.iter().cloned());

println!("{:?}", vec); // [2, 3, 4, 5]

获取以前的值

let mut vec = vec![0, 1, 2, 3, 4];
let slice = &[9, 8, 7];

let old: Vec<_> = vec.splice(3.., slice.iter().cloned()).collect();

println!("{:?}", vec); // [0, 1, 2, 9, 8, 7]
println!("{:?}", old); // [3, 4]

Answer 2

好的,在Vec界面中没有合适的方法(我可以看到).但我们总能自己实施同样的事情.

的memmove

当T是Copy时,可能最明显的方法是移动内存,如下所示:

fn push_all_at<T>(v: &mut Vec<T>, offset: usize, s: &[T]) where T: Copy {
    match (v.len(), s.len()) {
        (_, 0) => (),
        (current_len, _) => {
            v.reserve_exact(s.len());
            unsafe {
                v.set_len(current_len + s.len());
                let to_move = current_len - offset;
                let src = v.as_mut_ptr().offset(offset as isize);
                if to_move > 0 {
                    let dst = src.offset(s.len() as isize);
                    std::ptr::copy_memory(dst, src, to_move);
                }
                std::ptr::copy_nonoverlapping_memory(src, s.as_ptr(), s.len());
            }
        },
    }
}

拖曳

如果T不是复制,但它实现了Clone,我们可以将给定的切片附加到Vec的末尾,并使用交换 s在线性时间内将其移动到所需的位置:

fn push_all_at<T>(v: &mut Vec<T>, mut offset: usize, s: &[T]) where T: Clone + Default {
    match (v.len(), s.len()) {
        (_, 0) => (),
        (0, _) => { v.push_all(s); },
        (_, _) => {
            assert!(offset <= v.len());
            let pad = s.len() - ((v.len() - offset) % s.len());
            v.extend(repeat(Default::default()).take(pad));
            v.push_all(s);
            let total = v.len();
            while total - offset >= s.len() {
                for i in 0 .. s.len() { v.swap(offset + i, total - s.len() + i); }
                offset += s.len();
            }
            v.truncate(total - pad);
        },
    }
}

迭代器concat

也许最好的选择是不要修改Vec.例如,如果要通过迭代器访问结果,我们可以从块中构建迭代器链:

let v: &[usize] = &[0, 1, 2];
let s: &[usize] = &[3, 4, 5, 6];
let offset = 2;
let chain = v.iter().take(offset).chain(s.iter()).chain(v.iter().skip(offset));

let result: Vec<_> = chain.collect();
println!("Result: {:?}", result);