IntoIter(IntoIter)

让我们继续编写迭代器.由于Deref的魔力,iter和iter_mut已经为我们写了.然而,有两个有趣的迭代器,Vec提供的切片不能:into_iter和drain.

IntoIter通过值消费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> Vec<T> {
  2.     pub fn into_iter(self) -> IntoIter<T> {
  3.         // Can't destructure Vec since it's Drop
  4.         let ptr = self.ptr;
  5.         let cap = self.cap;
  6.         let len = self.len;
  8.         // Make sure not to drop Vec since that will free the buffer
  9.         mem::forget(self);
  11.         unsafe {
  12.             IntoIter {
  13.                 buf: ptr,
  14.                 cap: cap,
  15.                 start: ptr.as_ptr(),
  16.                 end: if cap == 0 {
  17.                     // can't offset off this pointer, it's not allocated!
  18.                     ptr.as_ptr()
  19.                 } else {
  20.                     ptr.as_ptr().add(len)
  21.                 },
  22.                 _marker: PhantomData,
  23.             }
  24.         }
  25.     }
  26. }

这是向前迭代:

  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 any remaining elements
  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. }