title: Java-Iterable&Iterator
date: 2018-04-08 10:24:57
tags: [Java]

why iterate ?

很多语言都有类似于迭代器(Iterator)的结构，无论是语言本身的还是各种库提供的。

Python有Iterable，Iterator和generator

C++有STL里面的iterator

Java也有Iterable和Iterator

既然这么多地方都有迭代器的身影，那么就一定有使用它的优点。

不用关心内部结构

一个容器，内部实现可以是数组，也可以是链表。有了迭代器，我们就能用一种统一的方法遍历元素，而不用关心其内部实现。

机制

Java中的Iterable和Iterator是两个泛型接口，如下(JavaSE 8)

public interface Iterable<E>{
    Iterator<E> iterator();
}

public interface Iterator<E>{
    boolean hasNext();
    E next();
    default void forEachRemaining(Consumer<? super E> action);
    default void remove();
}

下面一个示例遍历ArrayList

import java.util.*;
public class ClassA{
    public static void main(String[] argv){
        ArrayList<String> list = new ArrayList<>();
        list.add("element1");
        list.add("element2");
        list.add("element3");
        for (String s: list)
            System.out.println(s);
    }
}

ArrayList实现了Collection接口，而Collection又继承了Iterable接口，上面的foreach遍历相当于这样：

Iterator<String> it = list.iterator();
while (it.hasNext())
    System.out.println(it.next());

再来看下foreach的使用，见链接

The type of the Expression must be Iterable or an array type, or a compile-time error occurs.

即foreach必须被应用于数组或实现了Iterable接口的对象

所以到现在对于Iterable对象的foreach遍历过程已经很明了了

1. 调用iterator()获得迭代器it
2. 调用it.hasNext() 如果返回真的话调用it.next()

自定义迭代

知道Iterable和Iterator的工作过程之后，我们可以尝试自己实现一个类似与容器的类。

import java.util.*;

public class Container implements Iterable<String> {
    private String[] data;
    private int N;

    // 内部迭代器类，对以小写s开头的字符串迭代
    private class SIter implements Iterator<String>{
        public int start;
        public int end;
        public SIter(){
            start = 0;
            end = N;
        }

        public String next(){
            while (!Container.this.data[start].startsWith("s") && start < end)
                start++;
            
            // 一旦调用next返回了一个值
            // 那么这个值就被'越过'了，所以要更新start
            return start < end ? Container.this.data[start++] : null; 
        }
        public boolean hasNext(){
            while (start < end)
            {
                if (Container.this.data[start].startsWith("s"))
                    break;
                start++;
            }
            return start < end;
        }
    }

    public Container(int capacity){
        data = new String[capacity];
        N = 0;
    }

    public Iterator<String> iterator(){
        return new SIter();
    }

    public boolean add(String s){
        // 判断是否已满
        if (N == data.length)
            return false;
        data[N++] = s;
        return true;
    }

    public static void main(String[] argv){
        Container c = new Container(10);
        c.add("super");
        c.add("uber");
        c.add("supreme");
        c.add("this is not shown");

        for (String s: c)
            System.out.println(s);
    }
}

可以将Iterator当成指向两个元素间隙的指针，一旦调用了next()那么它就越过一个元素到达下一个间隙，返回越过的元素，如果调用remove()（这里没详细讲）那么就越过一个元素并删除刚越过的元素。