イテレータって何？

※イメージ最優先で、記述は正確ではありません。

# ねらい

　以下のコードがどのように動作しているのかをなんとなく理解する

```python
for i in range(5):
    print(i)
# 0
# 1
# 2
# 3
# 4
```

## イテレーターってなによ

>Pythonのfor文はイテレータにたいして動作します。

と言われてもピンと来ないと思います。そこで、なんでこんな概念を必要なのかを説明します。

## いったんwhile文で再現してみる

　以下のfor文のサンプルを考えます。

```python
l = ['Alpha', 'Beta', 'Charlie']

for name in l:
    print(name)
```

　Pythonを学習してきた皆様ならこれでなにが出力されるかわかりますね？

```
Alpha
Beta
Charlie
```

　そうです、配列から取り出して名前を表示してくれます。これをwhileで書き換えるとこんな感じに書き換えることができます。

```python
l = ['Alpha', 'Beta', 'Charlie']
i = 0
while True:
    if i == len(l):
        break
    print(l[i])
    i += 1
```

## 同じことをSetにもやってみる

　出力は同じです。Pythonのfor文はいろんな配列に対してこのような操作を簡単にかけるようにする機能なのでしょうか？以下の例を考えてみます。今度は配列の代わりにset（集合）型を使った例です。setは集合を表すオブジェクトで、同じ数字を入れても一つとして保存されます。

```
s = {1, 2, 2, 3, 1, 4}
↓
{1, 2, 3, 4}
```

　このオブジェクトに対して今までと同じように操作しようとします。

```python
s = {1, 2, 3, 4, 5}

i = 0
while True:
    if i == len(s):
        break
    print(s[i])
    i += 1
```

　このプログラムを実行するとエラーがでて怒られます。

```
Traceback (most recent call last):
  File "a.py", line 7, in <module>
    print(s[i])
TypeError: 'set' object is not subscriptable
```

　なぜでしょう？SetやDict型などオブジェクトは、配列のように横一列に並んでいるわけではないからです。ハッシュテーブルという構造で表現されます。

![1200px-HASHTB08.svg.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/106327/b8cdf045-3280-6965-c0d7-08c5cd5d0734.png)
(画像はWikipediaから)


　また、世の中には木で表現されるようなデータ構造もあります。今回は分かりやすいので、これを例に考えます。
![Binary_tree.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/106327/7f647bb5-1f3b-3dfe-7ee9-8b1eb12622da.png)
(画像はWikipediaから)

　このように表現されたオブジェクトは、「5番目のやつとってきて！」みたいに指示してもすぐにはとってこれません。この図で言う頭の2から順番にたどっていかないといけません。なので、添字によるアクセスを禁止しています。そのかわり、「hogehogeって書かれてるやつ探して！」のような指示にはすぐに答えてくれます。辞書型はそのような特性を活かしたオブジェクトです。

　ではどういうふうに同じ挙動をwhile文で再現するのでしょうか？次に一例を示します。

```python
s = {1, 2, 3, 4, 5}

while True:
    if s == set():
        break
    print(s.pop())
```

　詳細なアルゴリズムは省きますが、listとは全く違う操作をしている事がわかります。しかし、このset型にたいしてもfor文が使えます。

```python
s = {1, 2, 3, 4, 5}

for num in s:
    print(num)
```

　なぜでしょう？これが「Pythonのfor文がイテレータを動かす」の本質です。listやsetにはイテレータが実装されています。そしてfor文はlistやsetのイテレータオブジェクトを渡しています。なので、以下のように書いても同じように動作します。

```py
s = {1, 2, 3, 4, 5}

a = iter(s)
for num in a:
    print(num)
```

## イテレーターの動作のイメージ

　そして、イテレータオブジェクトには\_\_next\_\_()が必ず実装され、今いるイテレーターの次に場所の値を返してくれる関数です。

　なので、これでも同じ出力になります

```py
s = {1, 2, 3, 4, 5}

a = iter(s)

print(next(a)) # __next__を外から呼び出す
print(next(a))
print(next(a))
print(next(a))
print(next(a))
```

　これを図示すると以下のようになります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/106327/c4f852c7-807b-62e5-485b-c02abae7a718.png" width=500px>

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/106327/c6101814-f0b9-1ffd-90ff-a82121588d3a.png" width=500px>
　イテレーターの便利さがなんとなくわかったかと思います。イテレーターは次の値さえとってくれればいいので、データをすべて保持する必要がありません。

## ねらいを理解する

　次のコードを見てください。ねらいで書いたコードです

```python
for i in range(5):
    print(i)
# 0
# 1
# 2
# 3
# 4
```

このコードは次のように考えることもできます。

```python
a = [0, 1, 2, 3, 4]

for i in a:
    print(i)
# 0
# 1
# 2
# 3
# 4
```

　もしこれが5個ではなく10000だったら？1000000だったら？0から999999までのリストを生成するのでしょうか？違います。数字を一個だけ用意して、増やしていけばいいのです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/106327/9a8ca11e-3708-e807-6e1c-1b805117dac5.png" width=500px>

　このようにして、実際に0から999999までのリストをつくらずに済むので、メモリを節約できます。そして、for文はこのイテレーターを呼び出すことで、様々なオブジェクトを効率的に使うことができます。

## 編集履歴

2020-06-19 shiracamusさんの指摘により、そとから__next__を呼んでいたソースコードを修正しました
2020-06-21 https://github.com/zerokpr さんの指摘によりSetのデータ構造周りの誤りを修正しました