2023-03-27  阅读(337)
原文作者:ClarenceZero 原文地址:https://blog.csdn.net/ClarenceZero/article/details/106887075

迭代器模式

定义

迭代器模式Iterator Design Pattern也叫游标模式Cursor Design Pattern。用来遍历集合对象(如数组、链表、树、图、跳表)

迭代器模式将集合对象的遍历操作从集合类中拆分出来,让两者的职责更加单一。

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

类图

202303272245235751.png

实现

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)时,表明该元素属于此版本,可以输出。

总结

  1. 迭代器封装集合内部数据结构,开发者不需要了解如何遍历,直接使用容器提供的迭代器即可。
  2. 迭代器模式将集合对象的遍历操作从集合类中拆分出来,使得两者职责更加单一。
  3. 迭代器模式让添加新的遍历算法更加容易,更符合开闭原则。
  4. 文章内容多数引用自设计模式之美
阅读全文
  • 点赞