Iterator :: unzip中SizeHint的目的是什么？

Question

从Rust标准库的实现unzip:

fn unzip<A, B, FromA, FromB>(self) -> (FromA, FromB) where
    FromA: Default + Extend<A>,
    FromB: Default + Extend<B>,
    Self: Sized + Iterator<Item=(A, B)>,
{
    struct SizeHint<A>(usize, Option<usize>, marker::PhantomData<A>);
    impl<A> Iterator for SizeHint<A> {
        type Item = A;

        fn next(&mut self) -> Option<A> { None }
        fn size_hint(&self) -> (usize, Option<usize>) {
            (self.0, self.1)
        }
    }

    let (lo, hi) = self.size_hint();
    let mut ts: FromA = Default::default();
    let mut us: FromB = Default::default();

    ts.extend(SizeHint(lo, hi, marker::PhantomData));
    us.extend(SizeHint(lo, hi, marker::PhantomData));

    for (t, u) in self {
        ts.extend(Some(t));
        us.extend(Some(u));
    }

    (ts, us)
}

这两行:

ts.extend(SizeHint(lo, hi, marker::PhantomData));
us.extend(SizeHint(lo, hi, marker::PhantomData));

实际上并没有扩展ts或us任何东西,因为返回的next方法.这样做的目的是什么？SizeHintNone

Answer 1

这是一个很酷的技巧.通过给这个尺寸暗示,它提供了ts和us预留空间,为有机会extend在循环调用.根据documentation

size_hint()主要用于优化,例如为迭代器的元素保留空间,但不能信任,例如省略不安全代码中的边界检查.不正确的实施size_hint()不应导致内存安全违规.

请注意,创建SizeHint是必要的,因为extendfor循环中的调用是使用Some值(Optional实现Iterator特征),而size_hintfor Some是(1, Some(1)).这对预分配没有帮助.

但是查看代码Vec,这将没有任何影响(无论是在HashMap和VecDeque).其他Extend实现可能不同.

执行ts.extend(SizeHint(lo, hi, marker::PhantomData));不会触发a resize,因为next返回None.也许有人应该写一个补丁.

impl<T> Vec<T> {
    fn extend_desugared<I: Iterator<Item = T>>(&mut self, mut iterator: I) {
        // This function should be the moral equivalent of:
        //
        //      for item in iterator {
        //          self.push(item);
        //      }
        while let Some(element) = iterator.next() {
            let len = self.len();
            if len == self.capacity() {
                let (lower, _) = iterator.size_hint();
                self.reserve(lower.saturating_add(1));
            }
            unsafe {
                ptr::write(self.get_unchecked_mut(len), element);
                // NB can't overflow since we would have had to alloc the address space
                self.set_len(len + 1);
            }
        }
    }
}

Answer 2

这是一个可疑的黑客！

它实现了一个带有虚假（高估）大小提示的迭代器，以鼓励生成的集合预先保留最终合适的容量。

很酷的技巧，但是，它通过实现一个大小提示来实现，其中估计的下限大于生成的实际元素数 (0)。如果下限未知，迭代器应该返回一个下限 0。由于这个原因，这个实现可以说是非常有问题的，并且集合的 Extend impl 可能会因此产生错误（但当然不是内存不安全。）