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`.
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
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.
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.
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
29 The array looks like this:
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.
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
43 So we're going to use the following struct:
54 And this is what we end up with for initialization:
58 fn into_iter(self) -> IntoIter<T> {
59 // Can't destructure Vec since it's Drop
64 // Make sure not to drop Vec since that will free the buffer
73 // can't offset off this pointer, it's not allocated!
76 ptr.offset(len as isize)
84 Here's iterating forward:
87 impl<T> Iterator for IntoIter<T> {
89 fn next(&mut self) -> Option<T> {
90 if self.start == self.end {
94 let result = ptr::read(self.start);
95 self.start = self.start.offset(1);
101 fn size_hint(&self) -> (usize, Option<usize>) {
102 let len = (self.end as usize - self.start as usize)
103 / mem::size_of::<T>();
109 And here's iterating backwards.
112 impl<T> DoubleEndedIterator for IntoIter<T> {
113 fn next_back(&mut self) -> Option<T> {
114 if self.start == self.end {
118 self.end = self.end.offset(-1);
119 Some(ptr::read(self.end))
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.
132 impl<T> Drop for IntoIter<T> {
135 // drop any remaining elements
136 for _ in &mut *self {}
138 let align = mem::align_of::<T>();
139 let elem_size = mem::size_of::<T>();
140 let num_bytes = elem_size * self.cap;
142 heap::deallocate(*self.buf as *mut _, num_bytes, align);