IntoIter

    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.

    The array looks like this:

    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.

    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:

    Here’s iterating forward:

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

    And here’s iterating backwards.

    1. impl<T> Drop for IntoIter<T> {
    2.         if self.cap != 0 {
    3.             // drop any remaining elements
    4.             for _ in &mut *self {}
    6.             let align = mem::align_of::<T>();
    7.             let elem_size = mem::size_of::<T>();
    8.             let num_bytes = elem_size * self.cap;
    9.             unsafe {
    10.                 heap::deallocate(self.buf.as_ptr() as *mut _, num_bytes, align);
    11.             }
    12.         }
    13.     }
    14. }