rust 当长度不变时,Vec::splice()是否有效?

gk7wooem  于 2023-10-20  发布在  其他
关注(0)|答案(3)|浏览(111)

当您使用Vec::splice()替换Vec的一部分时,是否足够聪明,可以专门处理替换与它所替换的块长度相同的情况,或者我应该自己处理?
这样做有意义吗?或者array.splice()是否足够聪明,可以这样做?

fn example(array: Vec<u64>, replacement: Vec<u64>, range: std::ops::Range<usize>) {
    if (replacement.len() == range.len()) {
        for i in range {
            array[i] = replacement[i];
        }
    } else {
        array.splice(range, replacement);
    }
}
8i9zcol2

8i9zcol21#

我屈服了,读了代码。他很聪明,足以应付这种情况。代码的工作原理如下:
1.你调用.splice(),它会创建一个Splice对象,其中包含一个Drain迭代器用于替换范围:

pub fn splice<R, I>(&mut self, range: R, replace_with: I) -> Splice<'_, I::IntoIter>
where
    R: RangeBounds<usize>,
    I: IntoIterator<Item = T>,
{
    Splice { drain: self.drain(range), replace_with: replace_with.into_iter() }
}
  1. Splice被丢弃,这将调用其drop()实现。
impl<I: Iterator> Drop for Splice<'_, I> {
    fn drop(&mut self) {

它做的第一件事是删除所有被替换的元素。

self.drain.by_ref().for_each(drop);

然后它检查替换是否在Vec的末尾,如果是,只需扩展它并返回。

unsafe {
            if self.drain.tail_len == 0 {
                self.drain.vec.as_mut().extend(self.replace_with.by_ref());
                return;
            }

接下来,它调用一个辅助函数fill(),用替换迭代器(replace_with)中尽可能多的元素替换被删除的元素。fill()返回false,如果它没有填满整个替换范围,在这种情况下它返回(我不确定在这种情况下尾部移动到哪里?)

// First fill the range left by drain().
            if !self.drain.fill(&mut self.replace_with) {
                return;
            }

现在replace_with可能剩下0个元素(在这种情况下,我们完成了),或者它可能有更多的元素(在这种情况下,尾部需要向后移动该数量)。这就是接下来发生的事情。

// There may be more elements. Use the lower bound as an estimate.
            // FIXME: Is the upper bound a better guess? Or something else?
            let (lower_bound, _upper_bound) = self.replace_with.size_hint();
            if lower_bound > 0 {
                self.drain.move_tail(lower_bound);
                if !self.drain.fill(&mut self.replace_with) {
                    return;
                }
            }

你可能期望if lower_bound == 0 { return; },但lower_bound只是一个估计值,所以它首先尝试,如果失败,它会将替换复制到一个临时向量中,这样它就可以知道完整的长度。

// Collect any remaining elements.
            // This is a zero-length vector which does not allocate if `lower_bound` was exact.
            let mut collected = self.replace_with.by_ref().collect::<Vec<I::Item>>().into_iter();
            // Now we have an exact count.
            if collected.len() > 0 {
                self.drain.move_tail(collected.len());
                let filled = self.drain.fill(&mut collected);
                debug_assert!(filled);
                debug_assert_eq!(collected.len(), 0);
            }

关键是,如果replace_with * 是 * 空的,因为替换大小与范围相同,那么所有这些操作都是相当简单的nop-ish事情。
最后一位删除Drain迭代器本身,这将移动尾部。可能再次?我不知道我有点忘了。不管怎样,如果长度是一样的,它肯定不会移动它。

}
        // Let `Drain::drop` move the tail back if necessary and restore `vec.len`.
    }
}
tktrz96b

tktrz96b2#

根据文档和another answersplice在少数情况下是“智能”(最佳)的,包括“[ replace_with ]的size_hint()的下限是精确的”的情况。
在示例函数中,replacement.iter()上的size_hint()的下限是精确的,因此应该执行一次内存移动。

fafcakar

fafcakar3#

据我所知,Splice::drop是完成大部分工作的,它调用fill,在匹配长度的情况下,它将通过replace_with进行重定向,并返回true,但将replace_with留空,因此lower_bound为0,collected.len()为0。
Drain::drop然后运行。循环应该什么都不做,因为Splice::drop已经迭代过了,然后DropGuard::drop,可能需要移动元素,不应该需要移动/复制元素,因为作为长度匹配的结果,tail应该等于start

相关问题