【设计模式】备忘录模式和迭代器模式

备忘录模式

备忘录模式，也叫快照（Snapshot）模式。
在 GoF的《设计模式》⼀书中，备忘录模式是这么定义的：

Captures and externalizes an object’s internal state so that it can be restored later, all without violating encapsulation.

在不违背封装原则的前提下，捕获⼀个对象的内部状态，并在该对象之外保存这个状态，以便之后恢复对象为先前的状态，属于行为型模式。

备忘录模式主要分为三个角色 :
发起人角色(Originator): 它是一个需要保存状态的类，可以创建一个备忘录/备份，并存储它的当前内部状态，也可以使用备忘录来恢复其内部状态。

**备忘录角色 Memento：**存储原发器的内部状态。除了发起人，备忘录类不能被其他类创建和修改。一般通过将Memento类与Originator类定义在同一个包中来实现封装（也可以作为内部类），使用默认访问标识符来定义Memento类，即保证其包内可见。

**负责人角色 Caretaker：**负责人又称为管理者，它负责保存备忘录。在负责人类中可以存储一个或多个备忘录对象，它只负责存储备忘录对象，而不能修改备忘录对象（负责人类只提供备忘录对象的读写接口，不提供备忘录属性的读写接口）。

代码示例

以一个文本编辑器为例，用户可以不断输入文本内容，也可以撤销上次输入的内容，按照备忘录模式实现如下:

public class InputText {private StringBuilder text = new StringBuilder();public void input(String input) {text.append(input);}public String show() {return text.toString();}public Snapshot createSnapshot() {return new Snapshot(this.text.toString());}public void restoreSnapshot(Snapshot snapshot) {text.replace(0, this.text.length(), snapshot.getText());}}

public class Snapshot {private String text;public Snapshot(String text) {this.text = text;}public String getText() {return text;}
}

public class SnapshotHolder {private Stack<Snapshot> stack = new Stack<>();public Snapshot getSnapshot() {return stack.pop();}public void pushSnapshot(Snapshot snapshot) {stack.push(snapshot);}
}

public class Test {public static void main(String[] args) {SnapshotHolder snapshotHolder = new SnapshotHolder();InputText text = new InputText();text.input("你好");System.out.println(text.show());snapshotHolder.pushSnapshot(text.createSnapshot());text.input("我是Xiaoming");System.out.println(text.show());System.out.println("=============回撤==========");text.restoreSnapshot(snapshotHolder.getSnapshot());System.out.println(text.show());}}

对于⼤对象的备份来说，备份占⽤的存储空间会⽐较⼤，备份和恢复的耗时会⽐较⻓。针对这个问题，不同的业务场景有不同的处理⽅式。⽐如，只备份必要的恢复信息，结合最新的数据来恢复；
再⽐如，全量备份和增量备份相结合，低频全量备份，⾼频增量备份，两者结合来做恢复。

迭代器模式

迭代器模式（Iterator Design Pattern），也叫作游标模式（Cursor Design Pattern），它提供一种顺序访问容器或者集合对象元素的方法，而又无需暴露集合内部表示。属于行为型模式

迭代器模式，一般包含四个角色
抽象容器 : 提供创建迭代器的接口
具体容器 : 创建具体迭代器
抽象迭代器 : 定义遍历元素的接口
具体迭代器 : 实现元素遍历行为

一般来说我们会在容器中定义
iterator() ⽅法，⽤来创建迭代器。迭代器接⼝中需要定义 hasNext()、next() 两个最基本的⽅法用于遍历。

代码示例

public interface Iterator<T> {public boolean hasNext();T next();
}

public class ListIterator implements Iterator<String>{private List<String> queue;private int cursor = 0;public ListIterator(List<String> queue) {this.queue = queue;}@Overridepublic boolean hasNext() {return cursor != queue.size();}@Overridepublic String next() {String name = queue.get(cursor);cursor++;return name;}
}

public interface Queue {void add(String name);void remove(String name);Iterator iterator();}

public class QueueImpl implements Queue{private List<String> list = new ArrayList<>();@Overridepublic void add(String name) {list.add(name);}@Overridepublic void remove(String name) {list.remove(name);}@Overridepublic Iterator iterator() {return new ListIterator(list);}
}

public class Test {public static void main(String[] args) {QueueImpl queue = new QueueImpl();queue.add("小明");queue.add("小花");queue.add("王一");Iterator<String> iterator = queue.iterator();while (iterator.hasNext()) {String name = iterator.next();System.out.println(name);}}
}

使用迭代器遍历集合的同时不能删除/增加元素

在通过迭代器来遍历集合元素的同时，增加或者删除集合中的元素，有可能会导致某个元素被重复遍历或遍历不到。(这是因为为了保持数组存储数据的连续性，数组的删除/插入操作会涉及元素的搬移)

针对这种问题有两种解决⽅案：⼀种是遍历的时候不允许增删元素，另⼀种是增删元素之后让遍历报错。

第一种实现比较困难，我们可以方便的知道遍历开始的时间点，但是我们无法知晓遍历什么时候结束(它可能获取到某个满足条件的值之后就结束遍历了)，而通过新方法告知集合遍历结束也比较容易遗漏。
Java采用的是第二种方法: 增删元素之后让遍历报错

Java在ArrayList 中定义了一个成员变量modCount，记录集合被修改的次数。集合每次新增或者删除元素，就会给modCount+1。
当用户创建迭代器的时候，我们把modCount 值传递给迭代器的 expectedModCount 成员变量，之后每次调⽤迭代器上的next()方法，我们都会检查集合上的 modCount 是否等于expectedModCount，也就是判断在创建完迭代器之后，集合是否改变过。

 private class Itr implements Iterator<E> {int cursor;       // index of next element to returnint lastRet = -1; // index of last element returned; -1 if no suchint expectedModCount = modCount;Itr() {}public boolean hasNext() {return cursor != size;}@SuppressWarnings("unchecked")public E next() {checkForComodification();int i = cursor;if (i >= size)throw new NoSuchElementException();Object[] elementData = ArrayList.this.elementData;if (i >= elementData.length)throw new ConcurrentModificationException();cursor = i + 1;return (E) elementData[lastRet = i];}final void checkForComodification() {if (modCount != expectedModCount)throw new ConcurrentModificationException();}}

总结

集合遍历⼀般有三种⽅式：for 循环、foreach 循环、迭代器遍历。
后两种本质上属于⼀种，都可以看作迭代器遍历。

相对于 for 循环遍历，利⽤迭代器来遍历有下⾯三个优势：

1. 迭代器模式封装集合内部的复杂数据结构，开发者不需要了解如何遍历，直接使⽤容器提供的迭代器即可
2. 迭代器模式将集合对象的遍历操作从集合类中拆分出来，放到迭代器类中，让两者的职责更加单⼀ (对于复杂的数据结构，图，树等，客户端自己实现遍历算法比较复杂也容易出错)
3. 因为迭代器都实现⾃相同的接⼝，在开发中，基于接⼝⽽⾮实现编程，替换/新增迭代器也变得更加容易