Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

IntoIteratorの実装を覗いてみる

pub trait IntoIterator {
    /// The type of the elements being iterated over.
    type Item;

    /// Which kind of iterator are we turning this into?
    type IntoIter: Iterator<Item=Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}

Rustのforループは、

for item in expression {
    code
}

という記法自体は他の言語と似ていますが、expressionに対してIntoIteratorによるIteratorへの変換(into_iter関数)をかける点が変わっています。Rustではこのように、目的とする構造を生成する何かをとるという設計が多用されています。例えばAsRefなどもそうです。

IntoIteratorというのは他の言語(JavaPythonなど)でいうところのIterableというのに近いと思います。expression自身がすでにIteratorの場合は、「自分がすでにIteratorの場合は自分自身をそのまま返す」という実装が選択されます。

impl<I: Iterator> IntoIterator for I {
    type Item = I::Item;
    type IntoIter = I;

    fn into_iter(self) -> I {
        self
    }
}

forループに関するもう1つ、他の言語と比べて変わっている点は、所有権の話も巻き込んでいることです。例えば、

let v = !vec[1,2,3];
for item in &v

では、expressionが参照をとっているので、itemはvの中のアイテムの「参照」となります。&をつけない場合は、所有権自体をmoveします。

では一体これは、どういうIteratorによって実現されているかというと、

Moveバージョンは、

impl<T> IntoIterator for Vec<T> {
    type Item = T;
    type IntoIter = IntoIter<T>;

参照バージョンは、sliceの定義として、

impl<'a, T> IntoIterator for &'a [T] {
    type Item = &'a T;
    type IntoIter = Iter<'a, T>;

impl<'a, T> IntoIterator for &'a mut [T] {
    type Item = &'a mut T;
    type IntoIter = IterMut<'a, T>;

注: 実際には参照バージョンの定義はVecにあるのですが、この時点ではDerefを経てsliceの実装が使われるはずだと思っていたので、sliceの実装を紹介しています。しかしあとになってIntoIteratorの前にDerefは適用されないことがわかりました。以下の記事をご覧ください。

www.rustforbeginners.com

このうち、IterとIterMutがIteratorの実装となっていますが、例えばIterMutについて見てみると、

pub struct IterMut<'a, T: 'a> {
    ptr: *mut T,
    end: *mut T,
    _marker: marker::PhantomData<&'a mut T>,
}

のように、先頭とおしりのポインタを持っている構造になっています。おしりは、例えば右からイテレートする時などに使っています。

IterとIterMutはItemがmutかどうかの違いだけで、イテレートする方法自体は共有出来るので、マクロで実装が生成されています。

macro_rules! iterator {
    (struct $name:ident -> $ptr:ty, $elem:ty, $raw_mut:tt, $( $mut_:tt )*) => {
        impl<'a, T> $name<'a, T> {

        impl<'a, T> Iterator for $name<'a, T> {
            type Item = $elem;

iterator!{struct Iter -> *const T, &'a T, const, /* no mut */}
iterator!{struct IterMut -> *mut T, &'a mut T, mut, mut}