Java设计模式-迭代器模式

Java设计模式
收藏 评论

迭代器(Iterator)模式，有时也被称为游标(Cursor)模式，在23种设计模式中属于对象行为型模式。

迭代器模式提供了一种顺序方法用于访问聚合对象中的各个元素，而又不暴露该对象的内部表示。

引言

从接触设计模式以来，其实心中一直有一个疑问，为什么要把迭代器作为一种设计模式单独介绍呢？之所以有这个疑问，可能也与我接触的编程语言有关系。Java作为自己平常开发中最常使用的语言，它的JDK中提供了强大的集合框架，这其中就包含了迭代器Iterator，之所以平常不去实现一个迭代器，很大程度上是因为JDK提供的集合框架就可以满足常规开发需求。比如，比较常用的线性表ArrayList和LinkedList，在遍历它们中的元素时，一般借助于for循环即可，即简单也很直观。但是如果需要遍历的是Set或者Map这些集合容器，由于它们存储的都是非线性且无序的元素，这时候是无法根据索引顺序遍历它们中的元素，此时迭代器模式则提供了一种解决方案，借助于迭代器可以轻松地访问集合容器中的各个元素，而且不用知道它们的内部存储结构。

集合是编程中最常使用的数据结构之一，大部分集合使用简单的列表存储元素。无论集合的构成方式如何，它都必须提供某种访问元素的方式， 便于其他代码使用其中的元素。

迭代器模式不仅仅提供了一种访问元素的方式，更多的则是体现在软件设计思想上面。有时候迭代器中相关方法会放在集合类中实现，这种方式一般称为内部迭代器，开发中并不建议使用内部迭代器，因为它违背了单一职责原则，如果集合改变的话，那么这个类需要改变；如果遍历方式改变的话，那么这个集合类也需要跟着改变。另外一种与内部迭代器相对应的是外部迭代器，外部迭代器才是迭代器模式的推荐方式，它将对集合元素的访问和遍历从集合对象中分离出来并放入一个迭代器对象中。外部迭代器不仅让集合对象的接口和实现变得简单，也可以让集合对象更专注于它所专注的事情上面，而不必去理会遍历的事情。

适用性

  • 访问一个聚合对象的内容而不用暴露它的内部表示。
  • 支持对聚合对象的多种遍历。
  • 为遍历不同的聚合结构提供一个统一的接口。比如遍历数组和List集合，都可以使用迭代器的方式进行遍历访问。

示例：数组转换为迭代器

// 迭代器接口
public interface Iterator {
	boolean hasNext();
	
	T next();
}

public class ArrayIterator implements Iterator {
	private T[] array;
	private int position;

	public ArrayIterator(T[] array) {
		this.array = array;
	}

	@Override
	public boolean hasNext() {
		if (position >= array.length || array[position] == null) {
			return false;
		}
		return true;
	}

	@Override
	public T next() {
		T t=array[position];
		position++;
		return t;
	}
}

public class Client {
	public static void main(String[] args) {
		String[] array={"aaa","bbb","ccc"};
		Iterator it=new ArrayIterator<>(array);
		
		while(it.hasNext()){
			String str=it.next();
			System.out.print(str+" ");
		}
	}
}

示例：二叉树转换为迭代器

本示例其实是LeetCode上的一道二叉搜索树迭代器题目的解析。

实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
提示：
next() 和 hasNext() 操作的时间复杂度是 O(1)，并使用 O(h) 内存，其中 h 是树的高度。
你可以假设 next() 调用总是有效的，也就是说，当调用 next() 时，BST 中至少存在一个下一个最小的数。
一般遍历二叉树有两种方式：递归遍历和借助栈遍历，题目中描述是每一步next()都返回二叉搜索树中的下一个最小的数，可以借助于递归将所有的元素都存入一个List集合列表中，然后顺序遍历该List列表即可，但是这样就不满足O(h)内存要求。 
// 二叉树
public class BinarySearchTree {
	protected TreeNode root;

	public void insert(int data) {
		this.root = insert(data, root);
	}

	private TreeNode insert(int data, TreeNode root) {
		if (root == null) {
			return new TreeNode(data);
		}
		if (data > root.data) {
			root.right = insert(data, root.right);
		} else {
			root.left = insert(data, root.left);
		}
		return root;
	}

	public Iterator toIterator() {
		return new BstIterator(this);
	}

	// 中序遍历二叉树
	public void inOrder(TreeNode root) {
		if (root == null) {
			return;
		}
		inOrder(root.left);
		System.out.println(root.data);
		inOrder(root.right);
	}

	// 二叉树节点
	static class TreeNode {
		int data;
		TreeNode left;
		TreeNode right;

		public TreeNode(int data) {
			this(data, null, null);
		}

		public TreeNode(int data, TreeNode left, TreeNode right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
	}
}

// 中序遍历迭代器
public class BstIterator implements Iterator {
	private LinkedList stack = new LinkedList<>();

	public BstIterator(BinarySearchTree tree) {
		pushToStack(tree.root);
	}

	public TreeNode next() {
		TreeNode node = stack.pop();
		TreeNode cur = node;
		cur = cur.right;
		if (cur != null) {
			pushToStack(cur);
		}
		return node;
	}

	public boolean hasNext() {
		return !stack.isEmpty();
	}

	private void pushToStack(TreeNode treeNode) {
		TreeNode cur = treeNode;
		while (cur != null) {
			stack.push(cur);
			cur = cur.left;
		}
	}
}

// 测试类
public class MainTest {
	public static void main(String[] args) {
		BinarySearchTree tree = new BinarySearchTree();
		tree.insert(3);
		tree.insert(8);
		tree.insert(1);
		tree.insert(4);
		tree.insert(6);
		tree.insert(2);
		tree.insert(10);
		tree.insert(9);
		tree.insert(20);
		tree.insert(25);
		tree.insert(15);
		tree.insert(16);

		Iterator it = tree.toIterator();
		while (it.hasNext()) {
			TreeNode tn = it.next();
			System.out.print(tn.data + " ");
			// 1 2 3 4 6 8 9 10 15 16 20 25 
		}
	}
}

模式分析

迭代器模式类图如下：

  • Iterator抽象迭代器：定义访问和遍历元素的接口。一般next()与hasNext()方法是通用方法，其余方法比如first()、currentItem()方法可选。
  • ConcreteIterator具体迭代器：实现抽象迭代器中定义的方法，完成对聚合对象的遍历。
  • Aggregate抽象聚合类：用于存储和管理元素对象，并且声明一个createIterator()方法用于创建一个迭代器对象，也可以理解为充当了迭代器工厂的角色。
  • ConcreteAggregate具体聚合类：实现了抽象聚合类中声明的createIterator()方法，该方法返回一个与该聚合类对应的一个具体迭代器。

迭代器模式推荐的实现方式是外部迭代器，集合对象负责管理和维护元素对象，将访问和遍历的工作交给迭代器去完成。但是如果迭代器在实现迭代的过程中需要访问集合对象中的私有遍历，外部迭代器则可能破坏集合对象的封装性。

迭代器的目的是为了遍历访问集合中的元素，但是如果在遍历的同时集合又被更改了，这也是迭代器不得不考虑的事情。为了防止因为删除或者增加元素对遍历的影响，一般有两种解决方式：其一，克隆一份原集合对象，迭代器遍历的其实是集合的克隆对象，但是一般来说这样做代价太高。其二，在迭代算法实现的过程中，保证删除或者增加不会干扰遍历，一般实现方式是在迭代器中加入一个内部状态，用于记录集合之前的状态，如果在迭代过程中原集合对象又有更新，此时更新集合的状态，然后将迭代器中的状态与集合中状态做对比，JDK中List生成的迭代器就是采用的这种实现方式。

如下是一个简单的示例，用于展示JDK中迭代器算法的健壮性。

List list=new ArrayList<>();
list.add("aaa");
list.add("bbb");
list.add("ccc");

Iterator it=list.iterator();
while(it.hasNext()){
	String str=it.next();
	System.out.println(str);
	list.remove(2); // 迭代的同时删除某个元素
}

如果运行上述程序，一定会得到如下异常：

Exception in thread "main" java.util.ConcurrentModificationException
	at java.util.ArrayList$Itr.checkForComodification(Unknown Source)
	at java.util.ArrayList$Itr.next(Unknown Source)
	at com.sunny.bst.MainTest.test(MainTest.java:31)
	at com.sunny.bst.MainTest.main(MainTest.java:16)

ArrayList在生成迭代器对象的时候，会将对象中的modCount赋值给迭代器对象的expectedModCount，一旦ArrayList有新增或者删除操作，此时modeCount都会被改变，迭代器在每一次的遍历过程中都会检测modCount与expectedModCount是否相等，如果不相等，就会抛出一个ConcurrentModificationException类型的异常。

模式优点

迭代器模式支持以不同的方式遍历一个聚合元素。比如二叉树，可以使用先序遍历、中序遍历或者后续遍历，也可以使用深度遍历或者广度遍历。

迭代器简化了聚合接口。因为有了迭代器的遍历接口，聚合本身就不需要类似的遍历接口了。

在同一个聚合上可以有多个遍历。由于每个迭代器都有自己的状态，因此可以同时进行多个遍历。

模式缺点

由于迭代器模式将数据存储和数据遍历的职责分离，增加新的聚合类需要对应增加新的迭代器类，类的个数成对增加，这在一定程度上增加了系统的复杂性。

迭代器模式会给遍历方一个有序型的错觉，因为使用迭代器方式遍历的元素大多没有确定的顺序，但是迭代必须以一定的线性进行。如果遍历方误以为聚合元素时有序的，在操作过程中可能过度依赖有序性而产生错误。

与其它模式关系

在组合模式中常常借助于迭代器模式访问组合元素。

在聚合对象创建迭代器对象时可以借助于工厂模式。

结束语

虽然开发中自己去实现一个迭代器的场景不多，但是迭代器模式确实是开发中最常使用的设计模式之一。之所以不需要开发人员自己实现一个迭代器，是因为在面向对象的系统中，大多数集合类库都以不同形式提供了迭代器。

迭代器经常用于遍历那些复杂的非线性的数据结构中，开发中遇到的线性结构，一般借助于数组或者有序列表就可以完成遍历功能，而且实现上也清晰简单。

版权声明：本站文章均可转载，商业转载请联系获得授权，非商业转载请注明出处：https://www.yimipuzi.com/1154.html

评论

您确定要删除吗？删除之后不可恢复