4

当您Vec::splice()用来替换 a 的一部分时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);
    }
}
4

3 回答 3

5

我屈服并阅读了代码。处理这种情况足够聪明。以下是代码的工作原理:

  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() }
    }
    
  2. 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`.
        }
    }
    
于 2020-06-24T16:00:12.470 回答
1

据我所知,Splice::drop大部分工作是什么,并且调用fill,在匹配长度的情况下,它将遍历replace_with,并返回true但保留为replace_with空,因此lower_bound为 0 和collected.len()为 0。

Drain::drop然后运行。循环不应该做任何事情,因为Splice::drop已经对其进行了迭代,然后DropGuard::drop可能需要移动元素,不应该移动/复制元素,因为长度匹配的结果tail应该等于start

于 2020-06-24T15:51:25.623 回答
1

根据文档另一个答案,在某些情况下是“智能”(最佳),包括“[ ]splice的下限是准确的”。replace_withsize_hint()

size_hint()在您的示例函数中, on的下限replacement.iter()是精确的,因此应该执行一次内存移动。

于 2020-06-24T15:05:09.440 回答