IntoIter

イテレータに移行しましょう。 Deref の魔法のおかげで、 iter と iter_mut は 既に書かれています。しかし、 Vec が提供できて、スライスが提供できない 2 つの 興味深いイテレータがあります。 into_iter と drain です。

IntoIter は Vec を値として消費します。その結果、その要素を値で返します。 これを有効にするために、 IntoIter が Vec のアロケーションを操作する 必要があります。

IntoIter は始端と終端の両方から読み出せるように、両頭である必要があります。 後ろから読み込むのは単に pop を呼び出すよう実装すればよいのですが、 前から読み出すのはもっと難しいです。 remove(0) を呼び出してもよいのですが、 そのコストは馬鹿馬鹿しい位大きいです。その代わりに、バッファを全く変化させずに、 ptr::read を使って両端から値をコピーするようにします。

これをするために、 C のごく普通の配列のイテレーションのイディオムを使います。 2 つのポインタを生成します。 1 つは配列の最初を指し、もう 1 つは配列の最後の 1 つ後ろの要素を指します。終端から要素を 1 つ取得したい場合は、ポインタが 指している値を読み出して、ポインタを 1 だけ動かします。もし 2 つのポインタが 等価な場合、全要素が読み出されたことを意味します。

読み出しとオフセットの操作の順序は next と next_back とで逆転することに 注意してください。 next_back では、ポインタは次に読みたい要素の直後の 要素をいつも指しています。対して next では、ポインタは次に読みたい 要素をいつも指しています。なぜこうなのか、 1 つを除いて全ての要素が 既に返された例を見てみましょう。

配列は以下のようになっています。

          S  E
[X, X, X, O, X, X, X]

もし E が、次に返したい値を直接指していたら、返す値が既に存在しない場合と 区別がつかなくなっているでしょう。

イテレーションの途中では気にしないのですが、 IntoIter がドロップされたら Vec を 解放するため、 Vec のアロケーションの情報を保持する必要もあります。

ですから以下のような構造体を使っていきます。

struct IntoIter<T> {
    buf: Unique<T>,
    cap: usize,
    start: *const T,
    end: *const T,
}

そしてこれが初期化のコードです。

impl<T> Vec<T> {
    fn into_iter(self) -> IntoIter<T> {
        // Vec がドロップされてしまうため、 Vec を分配出来ません。
        let ptr = self.ptr;
        let cap = self.cap;
        let len = self.len;

        // Vec をドロップするとバッファを解放してしまうので、ドロップしないようにします。
        mem::forget(self);

        unsafe {
            IntoIter {
                buf: ptr,
                cap: cap,
                start: *ptr,
                end: if cap == 0 {
                    // このポインタのオフセットを取ることが出来ません。アロケートされていないからです!
                    *ptr
                } else {
                    ptr.offset(len as isize)
                }
            }
        }
    }
}

前方へのイテレーションのコードです。

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                let result = ptr::read(self.start);
                self.start = self.start.offset(1);
                Some(result)
            }
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let len = (self.end as usize - self.start as usize)
                  / mem::size_of::<T>();
        (len, Some(len))
    }
}

そして後方へのイテレーションのコードです。

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        if self.start == self.end {
            None
        } else {
            unsafe {
                self.end = self.end.offset(-1);
                Some(ptr::read(self.end))
            }
        }
    }
}

IntoIter はアロケーションの所有権を受け取るので、それを解放するために Drop を 実装する必要があります。しかし、イテレーションの最中に返されなかった要素を ドロップするためにも Drop も実装する必要があります。

impl<T> Drop for IntoIter<T> {
    fn drop(&mut self) {
        if self.cap != 0 {
            // 残っている要素を全てドロップします
            for _ in &mut *self {}

            let align = mem::align_of::<T>();
            let elem_size = mem::size_of::<T>();
            let num_bytes = elem_size * self.cap;
            unsafe {
                heap::deallocate(*self.buf as *mut _, num_bytes, align);
            }
        }
    }
}