SizeHint在Iterator::unzip中的用途是什么？

Question

来自锈蚀标准库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扩展为任何东西，因为SizeHint的next方法返回None。这样做的目的是什么？

Answer 1

这是个很酷的把戏。通过给出这个大小提示，它使ts和us有机会为循环中的extend调用预留空间。根据documentation

size_hint()主要用于优化，例如为迭代器的元素预留空间，但不能信任它省略不安全代码中的边界检查。不正确的size_hint()实现不应导致内存安全冲突。

注意，创建SizeHint是必要的，因为extend调用for循环使用Some值(Optional实现Iterator特性)，而Some值的size_hint是(1, Some(1))。这对预先分配没有帮助。

但是，看看Vec的代码，这不会有任何影响(在HashMap和VecDeque中都不会)。其他的Extend实现可能不同。

ts.extend(SizeHint(lo, hi, marker::PhantomData));的执行不会触发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的下限。由于这个原因，这个实现可以说是非常错误的，并且集合的扩展进程可能会因此出现错误(当然，不是内存不安全)。