迭代器模式
定义
迭代器模式
Iterator Design Pattern也叫游标模式Cursor Design Pattern。用来遍历集合对象(如数组、链表、树、图、跳表)。迭代器模式将集合对象的遍历操作从集合类中拆分出来，让两者的职责更加单一。
迭代器模式提供一种方法顺序访问一个聚合对象中的各个元素，而不暴露其内部的表示。
类图
实现
1. 定义迭代器接口
public interface MyIterator<E> {
/**
* 判断是否有下一个元素
* @return
*/
boolean hasNext();
/**
* 迭代器内部指针+1动作
*/
void next();
/**
* 返回当前元素
* @return
*/
E currentItem();
}
2. 定义相对应容器迭代器实现
public class ArrayIterator<E> implements MyIterator {
private int cursor;
private ArrayList<E> arrayList;
public ArrayIterator(ArrayList<E> arrayList) {
this.cursor = 0;
this.arrayList = arrayList;
}
@Override
public boolean hasNext() {
return cursor != arrayList.size();
}
@Override
public void next() {
cursor++;
}
@Override
public Object currentItem() {
return arrayList.get(cursor);
}
}
3. 使用迭代器
public class T {
public static void main(String[] args) {
ArrayList<String> name = new ArrayList<>();
name.add("jjj");
name.add("zwf");
name.add("xxx");
MyIterator<String> iterator = new ArrayIterator<>(name);
while (iterator.hasNext()) {
System.out.println(iterator.currentItem());
iterator.next();
}
}
}
JAVA迭代器实现
1. 迭代器定义
public interface Iterator<E> {
/**
* Returns {@code true} if the iteration has more elements.
* (In other words, returns {@code true} if {@link #next} would
* return an element rather than throwing an exception.)
*
* @return {@code true} if the iteration has more elements
*/
boolean hasNext();
/**
* Returns the next element in the iteration.
*
* @return the next element in the iteration
* @throws NoSuchElementException if the iteration has no more elements
*/
E next();
default void remove() {
throw new UnsupportedOperationException("remove");
}
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
2. ArrayList迭代器实现
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
// modCount这是ArrayList中定义的一个成员变量: 记录集合被修改的次数。集合每调用一次增加或删除元素的函数，就会把modcount++
// 当我们通过iterator()创建迭代器进行迭代元素时，会把modCount传给expectedModCount。之后每次调用 hasNext()、next()、currentItem()函数时
// 都会检查modCount是否变更过。如果存在变量，则表明集合被其他人修改过，抛出ConcurrentModificationException()异常。fail-fast解决方式。
int expectedModCount = modCount;
// prevent creating a synthetic constructor
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];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
// lastRet:记录游标指向的前一个元素。
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
final int size = ArrayList.this.size;
int i = cursor;
if (i < size) {
final Object[] es = elementData;
if (i >= es.length)
throw new ConcurrentModificationException();
for (; i < size && modCount == expectedModCount; i++)
action.accept(elementAt(es, i));
// update once at end to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
3. ArraysList类组合迭代器
public Iterator<E> iterator() {
return new Itr();
}
4. ArrayList小结
关于迭代删除操作
Java迭代器中的remove()方法还是比较鸡肋的，作用有限。它只能删除游标指向的前一个元素，而且一个next()函数之后，只能跟着最多一个remove()操作。多次调用removce()操作会报错。
支持快照功能的迭代器
public class MyArraysList<E> implements List<E> {
// 初始化容量大小
private static final int DEFAULT_CAPACITY = 10;
// 使用数组存储元素
private Object[] elementData;
// 存放元素添加时间戳
private long[] addTimeStamp;
// 存放元素删除时间戳
private long[] deleteTimeStamp;
// 集合总大小(包含被删除元素、元素并未进行删除，只是删除动作修改了deleteTimeStamp时间戳)
private int totalSize;
// 集合实际大小
private int actualSize;
public MyArraysList() {
this.elementData = new Object[DEFAULT_CAPACITY];
this.addTimeStamp = new long[DEFAULT_CAPACITY];
this.deleteTimeStamp = new long[DEFAULT_CAPACITY];
this.totalSize = 0;
this.actualSize = 0;
}
public MyArraysList(int size) {
this.elementData = new Object[size];
this.addTimeStamp = new long[size];
this.deleteTimeStamp = new long[size];
this.totalSize = 0;
this.actualSize = 0;
}
@Override
public boolean add(E e) {
elementData[totalSize] = e;
addTimeStamp[totalSize] = System.currentTimeMillis();
deleteTimeStamp[totalSize] = Long.MAX_VALUE;
actualSize++;
totalSize++;
return true;
}
/**
* 元素删除动作
* 1.将deleteTimeStamp相应的数组序号置为当前时间
* 2.实际元素统计值actualSize减一
* @param o
* @return
*/
@Override
public boolean remove(Object o) {
for (int i = 0; i < totalSize; i++) {
if (elementData[i].equals(o)) {
deleteTimeStamp[i] = System.currentTimeMillis();
actualSize--;
}
}
return true;
}
/**
* 创建一个新的迭代器
* @return
*/
@Override
public Iterator<E> iterator() {
return new SnapshotArrayIteraotr(System.currentTimeMillis());
}
private class SnapshotArrayIteraotr<E> implements Iterator<E> {
// 创建迭代器时间戳
private long snapshotTimestap;
// 当前游标位置
private int cursor;
public SnapshotArrayIteraotr(long snapshotTimestap) {
this.snapshotTimestap = snapshotTimestap;
this.cursor = 0;
}
/**
* 是否还有下一个元素
* @return
*/
@Override
public boolean hasNext() {
return cursor <= totalSize;
}
/**
* 有两个步骤
* 1.获取cursor游标的值
* 2.找寻下一个游标位置
* @return
*/
@Override
public E next() {
E result =(E) elementData[cursor];
jumpToNextCursor();
return result;
}
/**
* 找寻下一个可用的游标
*/
private void jumpToNextCursor() {
while (cursor++ < totalSize) {
long addTime = addTimeStamp[cursor];
long deleteTime = deleteTimeStamp[cursor];
if (snapshotTimestap >= addTime && snapshotTimestap < deleteTime) {
// 在这个时间范围内的
break;
}
}
}
}
}
- 类似于数据库的MVVC。
- 容器中维护两个多出来的数组。分别是添加时间、删除时间。当
元素添加时间时间<=迭代器创建时间<元素删除时间(初始默认值为Long.MAX_VALUE)时，表明该元素属于此版本，可以输出。
总结
- 迭代器封装集合内部数据结构，开发者不需要了解如何遍历，直接使用容器提供的迭代器即可。
- 迭代器模式将集合对象的遍历操作从集合类中拆分出来，使得两者职责更加单一。
- 迭代器模式让添加新的遍历算法更加容易，更符合开闭原则。
- 文章内容多数引用自
设计模式之美。
