迭代器模式
2018-04-12 本文已影响0人
thebigsilly
新手，刚开始写。如果有没明白可以在下面评论哦，每天晚上下班回家都会在线。对文章结构和叙述请大家给予批评并且给出建议（最重要的一点）
文章中可点击的链接都是我自己写的。
本章内容主要包括
1 简介
2 UML
3 代码演示
4 Java应用
5 Java增强版Iterator(ListIterator)
6 总结
- 简介
在没有迭代器模式的情况下，当我们每次遍历一个集合的时候都会采用以下操作。
for (int i = 0 ; i < list.length; i++){
System.out.println(list.get[i]);
}
很明显访问数据和存储数据耦合在一起。而迭代器模式用来解耦访问数据和存储数据之间的耦合。
下面是迭代器模式的遍历
while(Iterator.hasNext()){
System.out.println(iterator.next);
}
到这里也许你会问，这也没有什么卵用啊，代码也没有什么太大的变化。
那么我们下面再说一个例子你就能看出来区别了。存在一个任务列表list，你需要以此执行这个任务列表。并且这个任务列表还是在两个线程中执行。以下为两个版本的伪代码
//没有迭代器,共用索引值i
thread1 {
if (i++ < list.length) {执行任务}
}
thread2 {
if (i++ < list.length) {执行任务}
}
//迭代器版本,共用迭代器Iterator
thread1 {
if (iterator.hasNext()) {执行任务}
}
thread2 {
if (iterator.hasNext()) {执行任务}
}
在多线程的情况下没有迭代器的版本会因为执行顺序的问题，造成一个任务被多次执行或者有的任务没有执行。我们为了解决这个问题会选择加锁机制。但同时这也导致了一个问题，我们每次增加一个线程都需要添加锁。
而在迭代器的版本中我们只需要保证iterator中的索引是线程安全的，取出的任务都会是顺序的。此处使用的原理为栈封闭
迭代器模式在顺序访问聚合对象的时候比较有用。它将聚合对象的内部封装。将存储数据和访问数据分离开保证了聚合对象的内部安全。但同时也增加了代码的复杂度，每一个聚合对象都要重新实现迭代器。迭代器模式属于行为性模式。
-
UML
UML
- 代码演示
Iterator
public interface Iterator<E> {
boolean hasNext();
E next();
}
Container
public interface Container<E> {
Iterator<E> getIterator();
}
ClassPeople
public class ClassPeople<E> implements Container<E> {
private int total;
private E[] peoples;
public ClassPeople(E[] peoples) {
this.peoples = peoples;
if (peoples == null)
total = -1;
else
total = peoples.length;
}
public Iterator getIterator() {
return new ClassIterator();
}
private class ClassIterator implements Iterator<E>{
private int index = 0;
public boolean hasNext() {
if (index >= total) {
return false;
}
return true;
}
public E next() {
return peoples[index++];
}
}
}
Test
public class Test {
public static void main(String[] args) {
String[] peoples = {"张三","李四","王五"};
Container<String> container = new ClassPeople<String>(peoples);
Iterator iterator = container.getIterator();
while (iterator.hasNext()) {
System.out.println(iterator.next());
}
}
}
- Java应用
Iterator
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();
/**
* Removes from the underlying collection the last element returned
* by this iterator (optional operation). This method can be called
* only once per call to {@link #next}. The behavior of an iterator
* is unspecified if the underlying collection is modified while the
* iteration is in progress in any way other than by calling this
* method.
*
* @implSpec
* The default implementation throws an instance of
* {@link UnsupportedOperationException} and performs no other action.
*
* @throws UnsupportedOperationException if the {@code remove}
* operation is not supported by this iterator
*
* @throws IllegalStateException if the {@code next} method has not
* yet been called, or the {@code remove} method has already
* been called after the last call to the {@code next}
* method
*/
default void remove() {
throw new UnsupportedOperationException("remove");
}
/**
* Performs the given action for each remaining element until all elements
* have been processed or the action throws an exception. Actions are
* performed in the order of iteration, if that order is specified.
* Exceptions thrown by the action are relayed to the caller.
*
* @implSpec
* <p>The default implementation behaves as if:
* <pre>{@code
* while (hasNext())
* action.accept(next());
* }</pre>
*
* @param action The action to be performed for each element
* @throws NullPointerException if the specified action is null
* @since 1.8
*/
default void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (hasNext())
action.accept(next());
}
}
ArrayList简化版本
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
transient Object[] elementData;
private int size;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {}; //标记null，也就是把DEFAULTCAPACITY_EMPTY_ELEMENTDATA 当做null值
private static final Object[] EMPTY_ELEMENTDATA = {}; //没有元素
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
//检查索引位置是否合法
private void rangeCheck(int index) {
if (index >= size)
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
//删除元素
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
private class Itr implements Iterator<E> {
int cursor; // 索引位置
int lastRet = -1; // 标记上一次遍历的索引位置
int expectedModCount = modCount;
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];
}
//删除元素并修改期望值，modCount是在ArrayList.this.remove()中＋1。
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();
}
}
//根据条件进行遍历，Consumer会另开新篇章此处不解释
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
//检查更新次数。
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
checkForComodification()实现了即时失效机制。即时失效机制让我们在多线程的情况下会很容易发现错误。
假设有线程A和线程B。他们分别持有一个相同的Iterator。modCount初始值为0。
线程A删除一个元素，删除元素之后modCount为1。当在 线程A执行cursor = lastRet期间线程B执行了删除操作，那么在checkForComdication时，expectedModCount为0而modCount为1就会抛出。ConcurrentModificationExceotion。此思想类似于CAS。
- Java增强版Iterator(ListIterator)
此Iterator是ArrayList的内部类
private class ListItr extends Itr implements ListIterator<E> {
ListItr(int index) {
super();
cursor = index;
}
public boolean hasPrevious() {
return cursor != 0;
}
public int nextIndex() {
return cursor;
}
public int previousIndex() {
return cursor - 1;
}
@SuppressWarnings("unchecked")
public E previous() {
checkForComodification();
int i = cursor - 1;
if (i < 0)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i;
return (E) elementData[lastRet = i];
}
public void set(E e) {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.set(lastRet, e);
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
public void add(E e) {
checkForComodification();
try {
int i = cursor;
ArrayList.this.add(i, e);
cursor = i + 1;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
}
ListIterator在Iterator的基础上添加了增加，设置，获取索引值等操作。
- 总结
迭代器模式虽然将访问数据和存储数据解耦了，但是却只能适应顺序迭代内聚集合，并且我们需要为每种聚合对象添加迭代器。
