Эффективно вставить или заменить несколько элементов в середине или в начале Vec?

Есть ли простой способ вставить или заменить несколько элементов из &[T] и / или Vec<T> в середине или в начале Vec в линейное время?

Я мог только найти std::vec::Vec::insert, но это только для вставки одного элемента в O(n) время, поэтому я, очевидно, не могу назвать это в цикле.

Я мог бы сделать split_off по этому показателю, extend новые элементы в левой половине раскола, а затем extend вторая половина в первую, но есть ли лучший способ?

Источник

2 ответа

Решение

По состоянию на 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]
Источник

Хорошо, в интерфейсе Vec нет подходящего метода (как я вижу). Но мы всегда можем реализовать то же самое сами.

memmove

Когда T - Копия, вероятно, самый очевидный способ - переместить память, например так:

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 и переместить его в требуемую позицию, используя swap 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);
        },
    }
}

Конкретные итераторы

Возможно, лучшим выбором будет вообще не модифицировать 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);
Источник

Я пытался добавить вектор в ржавчину и нашел этот закрытый вопрос, который был связан здесь (несмотря на то, что этот вопрос был как добавлением, так и вставкой И эффективности. Я думаю, что мой ответ будет лучше в качестве ответа на этот другой, более точный вопрос, потому что Я не могу подтвердить эффективность), но следующий код помог мне добавить (и наоборот). [Я уверен, что два других ответа более эффективны, но способ, которым я учусь, мне нравится получать ответы, которые могут быть вставлены с примерами, демонстрирующими применение ответа.]

pub trait Unshift<T> { fn unshift(&mut self, s: &[T]) -> (); }
pub trait UnshiftVec<T> { fn unshift_vec(&mut self, s: Vec<T>) -> (); }
pub trait UnshiftMemoryHog<T> { fn unshift_memory_hog(&mut self, s: Vec<T>) -> (); }
pub trait Shift<T> { fn shift(&mut self) -> (); }
pub trait ShiftN<T> { fn shift_n(&mut self, s: usize) -> (); }

impl<T: std::clone::Clone> ShiftN<T> for Vec<T> {
    fn shift_n(&mut self, s: usize) -> ()
    // where
    //    T: std::clone::Clone,
    {   
        self.drain(0..s);
    }
}

impl<T: std::clone::Clone> Shift<T> for Vec<T> {
    fn shift(&mut self) -> ()
    // where
    //    T: std::clone::Clone,
    {   
        self.drain(0..1);
    }
}

impl<T: std::clone::Clone> Unshift<T> for Vec<T> {
    fn unshift(&mut self, s: &[T]) -> ()
    // where
    //    T: std::clone::Clone,
    {   
        self.splice(0..0, s.to_vec());
    }
}
impl<T: std::clone::Clone> UnshiftVec<T> for Vec<T> {
    fn unshift_vec(&mut self, s: Vec<T>) -> ()
    where
        T: std::clone::Clone,
    {   
        self.splice(0..0, s);
    }
}

impl<T: std::clone::Clone> UnshiftMemoryHog<T> for Vec<T> {
    fn unshift_memory_hog(&mut self, s: Vec<T>) -> ()
    where
        T: std::clone::Clone,
    {
        let mut tmp: Vec<_> = s.to_owned();
        //let mut tmp: Vec<_> = s.clone(); // this also works for some data types
        /*
        let local_s: Vec<_> = self.clone(); // explicit clone()
        tmp.extend(local_s);                // to vec is possible
        */
        tmp.extend(self.clone());
        *self = tmp;
        //*self = (*tmp).to_vec(); // Just because it compiles, doesn't make it right.
    }
}

// this works for: v = unshift(v, &vec![8]);
// (If you don't want to impl Unshift for Vec<T>)

#[allow(dead_code)]
fn unshift_fn<T>(v: Vec<T>, s: &[T]) -> Vec<T>
where
    T: Clone,
{
    // create a mutable vec and fill it
    // with a clone of the array that we want
    // at the start of the vec.
    let mut tmp: Vec<_> = s.to_owned();
    // then we add the existing vector to the end
    // of the temporary vector.
    tmp.extend(v);
    // return the tmp vec that is identitcal
    // to unshift-ing the original vec.
    tmp
}

/*
    N.B. It is sometimes (often?) more memory efficient to reverse
    the vector and use push/pop, rather than splice/drain;
    Especially if you create your vectors in "stack order" to begin with.
*/

fn main() {
    let mut v: Vec<usize> = vec![1, 2, 3];
    println!("Before push:\t {:?}", v);
    v.push(0);
    println!("After push:\t {:?}", v);
    v.pop();
    println!("popped:\t\t {:?}", v);
    v.drain(0..1);
    println!("drain(0..1)\t {:?}", v);
    /*
        // We could use a function
    let c = v.clone();
    v = unshift_fn(c, &vec![0]);
    */
    v.splice(0..0, vec![0]);
    println!("splice(0..0, vec![0]) {:?}", v);
    v.shift_n(1);
    println!("shift\t\t {:?}", v);
    v.unshift_memory_hog(vec![8, 16, 31, 1]);
    println!("MEMORY guzzler unshift {:?}", v);
    //v.drain(0..3);
    v.drain(0..=2);
    println!("back to the start: {:?}", v);
    v.unshift_vec(vec![0]);
    println!("zerothed with unshift: {:?}", v);

    let mut w = vec![4, 5, 6];
    /*
    let prepend_this = &[1, 2, 3];
    w.unshift_vec(prepend_this.to_vec());
    */
    w.unshift(&[1, 2, 3]);

    assert_eq!(&w, &[1, 2, 3, 4, 5, 6]);
    println!("{:?} == {:?}", &w, &[1, 2, 3, 4, 5, 6]);
}
Источник
Другие вопросы по тегам