甲乙小朋友的房子

甲乙小朋友很笨，但甲乙小朋友不会放弃

0%

Java-Iterator

发表于 更新于 分类于

我们常常使用 JDK 提供的迭代接口进行 Java 集合的迭代。

1
2
3
4
5
Iterator iterator = list.iterator();
        while(iterator.hasNext()){
            String string = iterator.next();
            //do something
        }

迭代其实我们可以简单地理解为遍历，是一个标准化遍历各类容器里面的所有对象的方法类，它是一个很典型的设计模式。Iterator 模式是用于遍历集合类的标准访问方法。它可以把访问逻辑从不同类型的集合类中抽象出来，从而避免向客户端暴露集合的内部结构。 在没有迭代器时我们都是这么进行处理的。如下：

对于数组我们是使用下标来进行处理的:

1
2
3
4
5
6
int[] arrays = new int[10];
   for(int i = 0 ; i < arrays.length ; i++){
       int a = arrays[i];
       //do something
   }

对于 ArrayList 是这么处理的:

1
2
3
4
5
6
List<String> list = new ArrayList<String>();
   for(int i = 0 ; i < list.size() ;  i++){
      String string = list.get(i);
      //do something
   }

对于这两种方式，我们总是都事先知道集合的内部结构，访问代码和集合本身是紧密耦合的，无法将访问逻辑从集合类和客户端代码中分离出来。同时每一种集合对应一种遍历方法，客户端代码无法复用。 在实际应用中如何需要将上面将两个集合进行整合是相当麻烦的。所以为了解决以上问题， Iterator 模式腾空出世，它总是用同一种逻辑来遍历集合。使得客户端自身不需要来维护集合的内部结构，所有的内部状态都由 Iterator 来维护。客户端从不直接和集合类打交道，它总是控制 Iterator，向它发送”向前”，”向后”，”取当前元素”的命令，就可以间接遍历整个集合。

上面只是对 Iterator 模式进行简单的说明，下面我们看看 Java 中 Iterator 接口，看他是如何来进行实现的。

迭代器接口

首先Iterator定义了这个接口：

1
2
3
4
5
6
7
8
public interface Iterator<E> {
    //游标后面是否有下一个元素
    boolean hasNext();
    //先返回当前游标右边的元素，然后游标后移一个位置
    E next();
    //删除最近返回的元素。在调用remove之前，我们至少保证先调用一次next方法，而且调用next之后只能调用一次remove方法。
    void remove();
}

通过上面的示意图我们可以看到，游标并不是指向元素，而是指向元素的间隙！（这里我没有太理解）

Java自带的容器基本上都实现了Iterator这个接口。对于外部访问者来说，不必关心容器内部是怎样的数据结构（不管是arraylist还是array)，我们都可以使用迭代器方式来进行遍历。极大地方便了外部调用者。

ArrayList的Iterator实现

作为一个合格的程序员，我们来看看ArrayList的内部是如何实现Iterator的。

在ArrayList内部首先定义一个内部类Itr，该内部类实现Iterator接口，如下：

1
2
3
4
5
6
7
8
9
10
11
12
class ArrayList{
  ...
  // 该内部类实现Iterator接口
  private class Itr implements Iterator<E>{
    ...
  }
  
  // 通过使用 ArrayList.iterator() 方法返回的是 Itr() 内部类
  public Iterator<E> iterator(){
    return new Itr();
  }
}

通过使用 ArrayList.iterator() 方法返回的是 Itr() 内部类，所以现在我们需要关心的就是 Itr() 内部类的实现。

1
2
3
4
5
private class Itr implements Iterator<E>{
  int cursor = 0;
  int lastRet = -1;
  int expectedModCount = modCount;
}

在 Itr 内部定义了三个 int 型的变量：cursor、lastRet、expectedModCount。其中:

  • cursor 表示下一个元素的索引位置
  • lastRet 表示上一个元素的索引位置

hasNext()方法

1
2
3
public boolean hasNext(){
  return cursor != size;
}

next()方法

next()方法只需要返回cursor索引位置处的元素即可，然后修改cursor, lastRet即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
public E next(){
  checkForComdification();
  int i = cursor; //记录索引位置
  if(i >= size){ //如果获取元素大于集合元素个数，则抛出异常
    throw new NoSuchElementException();
  }
  Object[] elementData = ArrayList.this.elementData;
  if(i >= elementData.length){
    throw new ConcurrentModificationException();
  }
  curson = i + 1; //cursor + 1
  return (E) elementData[lastRet = i]; //lastRet + 1 且返回cursor处元素
}
  • checkForComodification() 主要用来判断集合的修改次数是否合法，即用来判断遍历过程中集合是否被修改过。在 Java 提高篇（二一）—–ArrayList 中已经阐述了。
  • modCount 用于记录 ArrayList 集合的修改次数，初始化为 0，每当集合被修改一次（结构上面的修改，内部update不算），如 add、remove 等方法，modCount + 1，所以如果 modCount 不变，则表示集合内容没有被修改。该机制主要是用于实现 ArrayList 集合的fast-fail机制，在 Java 的集合中，较大一部分集合是存在快速失败机制的，这里就不多说，后面会讲到。所以要保证在遍历过程中不出错误，我们就应该保证在遍历过程中不会对集合产生结构上的修改（当然 remove 方法除外），出现了异常错误，我们就应该认真检查程序是否出错而不是 catch 后不做处理。
1
2
3
4
final void checkForComodification() {
  if (modCount != expectedModCount)
    throw new ConcurrentModificationException();
}

remove()方法

对于 remove() 方法的是实现，它是调用 ArrayList 本身的 remove() 方法删除 lastRet 位置元素，然后修改 modCount 即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void remove() {
  if (lastRet < 0)
    throw new IllegalStateException();
  checkForComodification();

  try {
    ArrayList.this.remove(lastRet);
    cursor = lastRet;
    lastRet = -1;
    expectedModCount = modCount;
  } catch (IndexOutOfBoundsException ex) {
    throw new ConcurrentModificationException();
  }
}

迭代器模式

说完了迭代器。接下来了解一下迭代器模式。

定义：提供一种方法访问一个容器对象中各个元素，而又不暴露该对象的内部细节。

类型：行为类模式

类图：

空心箭头的虚线：实现关系

空心箭头的直接：泛化关系（A继承自B, A -> B）

空心菱形箭头直线：聚合关系（聚合关系用于表示实体对象之间的关系，表示整体由部分构成的语义；例如一个部门由多个员工组成）

如果要问java中使用最多的一种模式，答案不是单例模式，也不是工厂模式，更不是策略模式，而是迭代器模式，先来看一段代码吧：

1
2
3
4
5
6
7
public static void print(Collection coll){
  Iterator it = coll.iterator();
  while(it.hasNext()){
    String str = (String)it.next();
    System.out.println(str);
  }
}

这个方法的作用是循环打印一个字符串集合，里面就用到了迭代器模式，java语言已经完整地实现了迭代器模式，Iterator翻译成汉语就是迭代器的意思。提到迭代器，首先它是与集合相关的，集合也叫聚集、容器等，我们可以将集合看成是一个可以包容对象的容器，例如List，Set，Map，甚至数组都可以叫做集合，而迭代器的作用就是把容器中的对象一个一个地遍历出来。

迭代器模式的结构

  • 抽象容器：一般是一个接口，提供一个iterator()方法，例如java中的Collection接口，List接口，Set接口等。
  • 具体容器：就是抽象容器的具体实现类，比如List接口的有序列表实现ArrayList，List接口的链表实现LinkList，Set接口的哈希列表的实现HashSet等。
  • 抽象迭代器：定义遍历元素所需要的方法，一般来说会有这么三个方法：取得第一个元素的方法first()，取得下一个元素的方法next()，判断是否遍历结束的方法isDone()（或者叫hasNext()），移出当前对象的方法remove(),
  • 迭代器实现：实现迭代器接口中定义的方法，完成集合的迭代。

迭代器模式实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
    // 定义迭代器接口
    interface Iterator {
        public Object next();
        public boolean hasNext();
    }
    // 具体实现了迭代器的容器
    class ConcreteIterator implements Iterator{
        private List list = new ArrayList();
        private int cursor =0;
        public ConcreteIterator(List list){
            this.list = list;
        }
        public boolean hasNext() {
            if(cursor==list.size()){
                return false;
            }
            return true;
        }
        public Object next() {
            Object obj = null;
            if(this.hasNext()){
                obj = this.list.get(cursor++);
            }
            return obj;
        }
    }
    // 聚合接口
    interface Aggregate {
        public void add(Object obj);
        public void remove(Object obj);
        public Iterator iterator();
    }
    // 实现了聚合接口的容器
    class ConcreteAggregate implements Aggregate {
        private List list = new ArrayList();
        public void add(Object obj) {
            list.add(obj);
        }

        public Iterator iterator() {
            return new ConcreteIterator(list);
        }

        public void remove(Object obj) {
            list.remove(obj);
        }
    }
    // 客户端
    public class Client {
        public static void main(String[] args){
            Aggregate ag = new ConcreteAggregate();
            ag.add("小明");
            ag.add("小红");
            ag.add("小刚");
          
==============客户端只需要按照以下套路循环即可，不需要知道具体是什么=================
  
            Iterator it = ag.iterator();
            while(it.hasNext()){
                String str = (String)it.next();
                System.out.println(str);
            }
        }
    }

一定要体会以下aggregate与iterator的用途。

迭代器模式的优缺点

迭代器模式的优点有：

  • 简化了遍历方式，对于对象集合的遍历，还是比较麻烦的，对于数组或者有序列表，我们尚可以通过游标来取得，但用户需要在对集合了解很清楚的前提下，自行遍历对象，但是对于hash表来说，用户遍历起来就比较麻烦了。而引入了迭代器方法后，用户用起来就简单的多了。
  • 可以提供多种遍历方式，比如说对有序列表，我们可以根据需要提供正序遍历，倒序遍历两种迭代器，用户用起来只需要得到我们实现好的迭代器，就可以方便的对集合进行遍历了。
  • 封装性良好，用户只需要得到迭代器就可以遍历，而对于遍历算法则不用去关心。

迭代器模式的缺点：

  • 对于比较简单的遍历（像数组或者有序列表），使用迭代器方式遍历较为繁琐，大家可能都有感觉，像ArrayList，我们宁可愿意使用for循环和get方法来遍历集合。

迭代器模式的适用场景

迭代器模式是与集合共生共死的，一般来说，我们只要实现一个集合，就需要同时提供这个集合的迭代器，就像java中的Collection，List、Set、Map等，这些集合都有自己的迭代器。假如我们要实现一个这样的新的容器，当然也需要引入迭代器模式，给我们的容器实现一个迭代器。

但是，由于容器与迭代器的关系太密切了，所以大多数语言在实现容器的时候都给提供了迭代器，并且这些语言提供的容器和迭代器在绝大多数情况下就可以满足我们的需要，所以现在需要我们自己去实践迭代器模式的场景还是比较少见的，我们只需要使用语言中已有的容器和迭代器就可以了。

总结

跟闫老板请教后，心得：

迭代器是容器对象中的一个成员，所以它可以访问到容器内的东西。那么就是：

1
2
3
4
class myCollection{
	int[] arr;
	Iterator it;
}

对于一个容器，如果想要遍历它的话，如果不用迭代器的话，需要了解其内部实现，比如链表和数组的访问是不一样的

迭代器里提供了抽象的next 和 hasNext方法，通过实现这两个方法，就可以把访问容器内容的逻辑封装成统一的数据访问接口

所有实现了某一种迭代器模型的容器就都可以用统一的方法去访问了而不需要考虑不同容器的内部实现

相关题

Peeking Iterator

实现一个具有peek功能的迭代器

一开始想复杂了。其实很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
Iterator<Integer> iterator;
Integer peek; // 记录下一个即将出去的数据
public PeekingIterator(Iterator<Integer> iterator) {
    // initialize any member here.
    this.iterator = iterator;
    moveNext();
    
}

// Returns the next element in the iteration without advancing the iterator.
public Integer peek() {
    return peek;
}

// hasNext() and next() should behave the same as in the Iterator interface.
// Override them if needed.
@Override
public Integer next() {
    Integer res = peek;
    moveNext();
    return res;
}

@Override
public boolean hasNext() {
    return null != peek;
}

private void moveNext(){
    if(iterator.hasNext()){
        peek = iterator.next();
    }else{
        peek = null;
    }
}