原文链接：https://doc.rust-lang.org/nomicon/vec-into-iter.html

IntoIter

我们继续编写迭代器。iter和iter_mut其实已经写过了，感谢神奇的DeRef。但是还有两个有意思的迭代器是Vec提供的而slice没有的：into_iter和drain。

IntoIter以值而不是引用的形式访问Vec，同时也是以值的形式返回元素。为了实现这一点，IntoIter需要获取Vec的分配空间的所有权。

IntoIter也需要DoubleEnd，即从两个方向读数据。从尾部读数据可以通过调用pop实现，但是从头读数据就困难了。我们可以调用remove(0)，但是它的开销太大了。我们选择直接使用ptr::read从Vec的两端拷贝数据，而完全不去改变缓存。

我们要用一个典型的C访问数组的方式来实现这一点。我们先创建两个指针，一个指向数组的开头，另一个指向结尾后面的那个元素。如果我们需要一端的元素，我们就从那一端指针指向的位置处读出值，然后把指针移动一位。当两个指针相等时，就说明迭代完成了。

注意，next和next_back中的读和offset的顺序是相反的。对于next_back，指针总是指向它下一次要读的元素的后面，而next的指针总是指向它下一次要读的元素。为什么要这样呢？考虑一下只剩一个元素还未被读取的情况。

这时的数组像这样：

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

如果E直接指向它下一次要读的元素，我们就无法把上面的情况和所有元素都读过了的情况区分开了。

我们还需要保存Vec的分配空间的信息，虽然在迭代过程中我们并不关心它，但我们在IntoIter被drop的时候需要这些信息来释放空间。

所以我们要用下面这个结构体：

  1. struct IntoIter<T> {
  2.     buf: Unique<T>,
  3.     cap: usize,
  4.     start: *const T,
  5.     end: *const T,
  6. }

这是初始化的代码：

  1. impl<T> Vec<T> {
  2.     fn into_iter(self) -> IntoIter<T> {
  3.         // 因为Vec是Drop，不能销毁它
  4.         let ptr = self.ptr;
  5.         let cap = self.cap;
  6.         let len = self.len;
  8.         // 确保Vec不会被drop，因为那样会释放内存空间
  9.         mem::forget(self);
  11.         unsafe {
  12.             IntoIter {
  13.                 buf: ptr,
  14.                 cap: cap,
  15.                 start: *ptr,
  16.                 end: if cap == 0 {
  17.                     // 没有分配空间，不能计算指针偏移量
  18.                     *ptr
  19.                 } else {
  20.                     ptr.offset(len as isize)
  21.                 }
  22.             }
  23.         }
  24.     }
  25. }

这是前向迭代的代码：

  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 {}
  7.             let align = mem::align_of::<T>();
  8.             let elem_size = mem::size_of::<T>();
  9.             let num_bytes = elem_size * self.cap;
  10.             unsafe {
  11.                 heap::deallocate(self.buf.as_ptr() as *mut _, num_bytes, align);
  12.             }
  13.         }
  14.     }
  15. }