IntoIter

让我们继续，接下来写迭代器。iter和iter_mut已经为我们写好了，感谢 Deref 的魔法。然而，有两个有趣的迭代器是 Vec 提供的，而 slice 不能提供：into_iter和drain。

IntoIter 通过消耗掉 Vec 的值（获取 Vec 的所有权），并因此可以产生其元素的值（所有权）。为了实现这个目的，IntoIter 需要控制 Vec 的分配。

IntoIter 也需要是 DoubleEnded，以便能够从两端读取。从后面读取可以通过调用pop来实现，但是从前面读取就比较困难了。我们可以调用remove(0)，但这将是非常昂贵的。相反，我们将使用ptr::read来复制 Vec 两端的值，而不改变缓冲区。

为了做到这一点，我们将使用一个非常常见的 C 语言的数组迭代习惯。我们将建立两个指针；一个指向数组的开始，另一个指向数组结束后的一个元素。当我们想从一端获得一个元素时，我们将读出指向那一端的值，并将指针移到另一端。当这两个指针相等时，我们就知道我们已经完成了。

注意，对于next和next_back来说，读取和偏移的顺序是相反的。对于next_back来说，指针总是在它想读取的元素之后，而对于next来说，指针正好在它想读取的元素上。要想知道为什么会这样，请考虑除一个元素外的所有元素都已经产生的情况。

这个数组看起来像这样：

  1.           S  E
  2. [X, X, X, O, X, X, X]

如果 E 直接指向它想产生的下一个元素，它将与没有更多元素可以产生的情况没有区别。

虽然我们在迭代过程中实际上并不关心它，但我们也需要保留 Vec 的分配信息，以便在 IntoIter 被丢弃后释放它。

所以我们将使用下面的结构。

  1. pub struct IntoIter<T> {
  2.     buf: NonNull<T>,
  3.     cap: usize,
  4.     start: *const T,
  5.     end: *const T,
  6.     _marker: PhantomData<T>,
  7. }

而这就是我们最终的初始化结果：

  1. impl<T> IntoIterator for Vec<T> {
  2.     type Item = T;
  3.     type IntoIter = IntoIter<T>;
  4.     fn into_iter(self) -> IntoIter<T> {
  5.         // 因为 Vec 实现了 Drop，所以我们不能销毁它
  6.         let ptr = self.ptr;
  7.         let cap = self.cap;
  8.         let len = self.len;
  10.         // 确保 Vec 不会被 drop，因为那样会释放内存
  11.         mem::forget(self);
  13.         unsafe {
  14.             IntoIter {
  15.                 buf: ptr,
  16.                 cap: cap,
  17.                 start: ptr.as_ptr(),
  18.                 end: if cap == 0 {
  19.                     // 不能通过这个指针获取偏移，因为没有分配内存
  20.                     ptr.as_ptr()
  21.                 } else {
  22.                     ptr.as_ptr().add(len)
  23.                 },
  24.                 _marker: PhantomData,
  25.             }
  26.         }
  27.     }
  28. }

向前迭代：

  1. impl<T> Iterator for IntoIter<T> {
  2.     type Item = T;
  3.     fn next(&mut self) -> Option<T> {
  4.         if self.start == self.end {
  5.             None
  6.         } else {
  7.             unsafe {
  8.                 let result = ptr::read(self.start);
  9.                 self.start = self.start.offset(1);
  10.                 Some(result)
  11.             }
  12.         }
  13.     }
  15.     fn size_hint(&self) -> (usize, Option<usize>) {
  16.         let len = (self.end as usize - self.start as usize)
  17.                   / mem::size_of::<T>();
  18.         (len, Some(len))
  19.     }
  20. }

向后迭代：

  1. impl<T> DoubleEndedIterator for IntoIter<T> {
  2.     fn next_back(&mut self) -> Option<T> {
  3.         if self.start == self.end {
  4.             None
  5.         } else {
  6.             unsafe {
  7.                 self.end = self.end.offset(-1);
  8.                 Some(ptr::read(self.end))
  9.             }
  10.         }
  11.     }
  12. }

因为 IntoIter 拥有其分配的所有权，它需要实现 Drop 来释放它；并且，它也需要在 Drop 里丢弃它所包含的任何没有被迭代到的元素。

  1. impl<T> Drop for IntoIter<T> {
  2.     fn drop(&mut self) {
  3.         if self.cap != 0 {
  4.             // 将剩下的元素 drop
  5.             for _ in &mut *self {}
  6.             let layout = Layout::array::<T>(self.cap).unwrap();
  7.             unsafe {
  8.                 alloc::dealloc(self.buf.as_ptr() as *mut u8, layout);
  9.             }
  10.         }
  11.     }
  12. }