src/doc/tarpl/vec-into-iter.md

   1 % IntoIter
   2
   3 Let's move on to writing iterators. `iter` and `iter_mut` have already been
   4 written for us thanks to The Magic of Deref. However there's two interesting
   5 iterators that Vec provides that slices can't: `into_iter` and `drain`.
   6
   7 IntoIter consumes the Vec by-value, and can consequently yield its elements
   8 by-value. In order to enable this, IntoIter needs to take control of Vec's
   9 allocation.
  10
  11 IntoIter needs to be DoubleEnded as well, to enable reading from both ends.
  12 Reading from the back could just be implemented as calling `pop`, but reading
  13 from the front is harder. We could call `remove(0)` but that would be insanely
  14 expensive. Instead we're going to just use ptr::read to copy values out of
  15 either end of the Vec without mutating the buffer at all.
  16
  17 To do this we're going to use a very common C idiom for array iteration. We'll
  18 make two pointers; one that points to the start of the array, and one that
  19 points to one-element past the end. When we want an element from one end, we'll
  20 read out the value pointed to at that end and move the pointer over by one. When
  21 the two pointers are equal, we know we're done.
  22
  23 Note that the order of read and offset are reversed for `next` and `next_back`
  24 For `next_back` the pointer is always *after* the element it wants to read next,
  25 while for `next` the pointer is always *at* the element it wants to read next.
  26 To see why this is, consider the case where every element but one has been
  27 yielded.
  28
  29 The array looks like this:
  30
  31 ```text
  32           S  E
  33 [X, X, X, O, X, X, X]
  34 ```
  35
  36 If E pointed directly at the element it wanted to yield next, it would be
  37 indistinguishable from the case where there are no more elements to yield.
  38
  39 Although we don't actually care about it during iteration, we also need to hold
  40 onto the Vec's allocation information in order to free it once IntoIter is
  41 dropped.
  42
  43 So we're going to use the following struct:
  44
  45 ```rust,ignore
  46 struct IntoIter<T> {
  47     buf: Unique<T>,
  48     cap: usize,
  49     start: *const T,
  50     end: *const T,
  51 }
  52 ```
  53
  54 And this is what we end up with for initialization:
  55
  56 ```rust,ignore
  57 impl<T> Vec<T> {
  58     fn into_iter(self) -> IntoIter<T> {
  59         // Can't destructure Vec since it's Drop
  60         let ptr = self.ptr;
  61         let cap = self.cap;
  62         let len = self.len;
  63
  64         // Make sure not to drop Vec since that will free the buffer
  65         mem::forget(self);
  66
  67         unsafe {
  68             IntoIter {
  69                 buf: ptr,
  70                 cap: cap,
  71                 start: *ptr,
  72                 end: if cap == 0 {
  73                     // can't offset off this pointer, it's not allocated!
  74                     *ptr
  75                 } else {
  76                     ptr.offset(len as isize)
  77                 }
  78             }
  79         }
  80     }
  81 }
  82 ```
  83
  84 Here's iterating forward:
  85
  86 ```rust,ignore
  87 impl<T> Iterator for IntoIter<T> {
  88     type Item = T;
  89     fn next(&mut self) -> Option<T> {
  90         if self.start == self.end {
  91             None
  92         } else {
  93             unsafe {
  94                 let result = ptr::read(self.start);
  95                 self.start = self.start.offset(1);
  96                 Some(result)
  97             }
  98         }
  99     }
 100
 101     fn size_hint(&self) -> (usize, Option<usize>) {
 102         let len = (self.end as usize - self.start as usize)
 103                   / mem::size_of::<T>();
 104         (len, Some(len))
 105     }
 106 }
 107 ```
 108
 109 And here's iterating backwards.
 110
 111 ```rust,ignore
 112 impl<T> DoubleEndedIterator for IntoIter<T> {
 113     fn next_back(&mut self) -> Option<T> {
 114         if self.start == self.end {
 115             None
 116         } else {
 117             unsafe {
 118                 self.end = self.end.offset(-1);
 119                 Some(ptr::read(self.end))
 120             }
 121         }
 122     }
 123 }
 124 ```
 125
 126 Because IntoIter takes ownership of its allocation, it needs to implement Drop
 127 to free it. However it *also* wants to implement Drop to drop any elements it
 128 contains that weren't yielded.
 129
 130
 131 ```rust,ignore
 132 impl<T> Drop for IntoIter<T> {
 133     fn drop(&mut self) {
 134         if self.cap != 0 {
 135             // drop any remaining elements
 136             for _ in &mut *self {}
 137
 138             let align = mem::align_of::<T>();
 139             let elem_size = mem::size_of::<T>();
 140             let num_bytes = elem_size * self.cap;
 141             unsafe {
 142                 heap::deallocate(*self.buf as *mut _, num_bytes, align);
 143             }
 144         }
 145     }
 146 }
 147 ```