IntoIter

Let’s move on to writing iterators. iter and iter_mut have already beenwritten for us thanks to The Magic of Deref. However there’s two interestingiterators that Vec provides that slices can’t: into_iter and drain.

IntoIter consumes the Vec by-value, and can consequently yield its elementsby-value. In order to enable this, IntoIter needs to take control of Vec’sallocation.

IntoIter needs to be DoubleEnded as well, to enable reading from both ends.Reading from the back could just be implemented as calling pop, but readingfrom the front is harder. We could call remove(0) but that would be insanelyexpensive. Instead we’re going to just use ptr::read to copy values out ofeither end of the Vec without mutating the buffer at all.

To do this we’re going to use a very common C idiom for array iteration. We’llmake two pointers; one that points to the start of the array, and one thatpoints to one-element past the end. When we want an element from one end, we’llread out the value pointed to at that end and move the pointer over by one. Whenthe two pointers are equal, we know we’re done.

Note that the order of read and offset are reversed for next and next_backFor next_back the pointer is always after the element it wants to read next,while for next the pointer is always at the element it wants to read next.To see why this is, consider the case where every element but one has beenyielded.

The array looks like this:

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

If E pointed directly at the element it wanted to yield next, it would beindistinguishable from the case where there are no more elements to yield.

Although we don’t actually care about it during iteration, we also need to holdonto the Vec’s allocation information in order to free it once IntoIter isdropped.

So we’re going to use the following struct:

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

And this is what we end up with for initialization:

  1. impl<T> Vec<T> {
  2.     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,
  16.                 end: if cap == 0 {
  17.                     // can't offset off this pointer, it's not allocated!
  18.                     *ptr
  19.                 } else {
  20.                     ptr.offset(len as isize)
  21.                 }
  22.             }
  23.         }
  24.     }
  25. }

Here’s iterating forward:

  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. }

And here’s iterating backwards.

  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. }

Because IntoIter takes ownership of its allocation, it needs to implement Dropto free it. However it also wants to implement Drop to drop any elements itcontains that weren’t yielded.

  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 {}
  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. }