Java 8 容器源码-Vector与迭代器模式

撸了今年阿里、腾讯和美团的面试,我有一个重要发现…….

作者:潘威威
出处:https://blog.csdn.net/panweiwei1994


本文主要讲解迭代器模式Vector源码中的使用。参考的JDK版本为1.8。

迭代器模式(Iterator Pattern):提供一种方法来访问聚合对象中的各个元素,而不用暴露这个对象的内部表示。在Java中,Vector的迭代器有两种:Iterator和ListIterator。值得一提的是,elements()方法也能实现类似迭代器的效果。为什么已经有了迭代器,还特意在Vector中新增了elements()呢?在文章最后会作出解释。

Iterator

迭代器是一个用来遍历并选择序列中的对象。Java的Iterator的只能单向移动。

例子

在写如何实现之前,先看一个使用迭代器Iterator的小例子:

    import java.util.Iterator;
    import java.util.List;
    import java.util.Vector;

    public class ItrOfVectorTest {

            @org.junit.Test
            public void test() {
                List list = new Vector<>();
                list.add("1");
                list.add("2");
                list.add("3");
                list.add("4");
                Iterator iterator = list.iterator();
                while (iterator.hasNext()) {
                    String str = (String) iterator.next();
                    System.out.println(str);
                    iterator.remove();
                }
                System.out.println(list.size());
            }
    }

运行结果

    1
    2
    3
    4
    0

方法

  • iterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。
  • next(),获取序列中的下个元素。
  • hasNext(),检查序列中向下是否还有元素。
  • remove(),将迭代器最近返回的一个元素删除。这也意味着调用remove()前需要先调用next()。

实现

设计模式(16)-迭代器模式这一文章中曾讲过,迭代器模式中有四个角色:

  • 抽象聚合类Aggregate。在Vector的Iterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法iterator()是它自己的。
  • 具体聚合类ConcreteAggregate。在Vector的Iterator迭代器实现中,指的是Vector。
  • 抽象迭代器Iterator。在Vector的Iterator迭代器实现中,指的是Iterator接口。
  • 具体迭代器ConcreteIterator。在Vector中的Iterator迭代器实现中,指的是Itr。

MarkdownPhotos/master/CSDNBlogs/container/5.VectorAndDP/vectorAndIterator.jpg

Vector代码片段

    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        /**
         * 保存vector中元素的数组。vector的容量是数组的长度,数组的长度最小值为vector的元素个数。
         *
         * 任何在vector最后一个元素之后的数组元素是null。
         *
         * @serial
         */
        protected Object[] elementData;
        /**
         * vector中实际的元素个数。
         *
         * @serial
         */
        protected int elementCount;

        /**
         * vector需要自动扩容时增加的容量。
         *
         * 当vector的实际容量elementCount将要大于它的最大容量时,vector自动增加的容量。
         *
         * 如果capacityIncrement小于或等于0,vector的容量需要增长时将会成倍增长。
         * @serial
         */
        protected int capacityIncrement;

        /**
         * 序列版本号
         */
        private static final long serialVersionUID = -2767605614048989439L;

        /**
         * 返回一个用来遍历Vector元素的Iterator迭代器
         *
         * 返回的迭代器是fail-fast的
         */
        public synchronized Iterator<E> iterator() {
            return new Itr();
        }

        /**
         * AbstractList.Itr的最优化的版本
         */
        private class Itr implements Iterator<E> {
            int cursor;       // 下一个要返回的元素的索引
            int lastRet = -1; // i最近的被返回的元素的索引; 如果没有返回-1。
            int expectedModCount = modCount;
            /**
             * 判断是否有下一个元素
             */
            public boolean hasNext() {
                // Racy but within spec, since modifications are checked
                // within or after synchronization in next/previous
                return cursor != elementCount;
            }
            //返回下一个元素
            public E next() {
                synchronized (Vector.this) {
                    checkForComodification();
                    int i = cursor;
                    if (i >= elementCount)
                        throw new NoSuchElementException();
                    cursor = i + 1;
                    return elementData(lastRet = i);
                }
            }
            //删除最近的一个被返回的元素
            public void remove() {
                if (lastRet == -1)
                    throw new IllegalStateException();
                synchronized (Vector.this) {
                    checkForComodification();
                    Vector.this.remove(lastRet);
                    expectedModCount = modCount;
                }
                cursor = lastRet;
                lastRet = -1;
            }

            @Override
            public void forEachRemaining(Consumer<? super E> action) {
                Objects.requireNonNull(action);
                synchronized (Vector.this) {
                    final int size = elementCount;
                    int i = cursor;
                    if (i >= size) {
                        return;
                    }
            @SuppressWarnings("unchecked")
                    final E[] elementData = (E[]) Vector.this.elementData;
                    if (i >= elementData.length) {
                        throw new ConcurrentModificationException();
                    }
                    while (i != size && modCount == expectedModCount) {
                        action.accept(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();
            }
        }

    }

Iterator

    import java.util.function.Consumer;

    public interface Iterator<E> {

        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
        }
    }

Itr.java

作为Vector的内部类。请在上文中的[Vector.java代码片段]中查看。

ListIterator

ListIterator是一个更加强大的Iterator的子类型。它只能用于各种List类的访问。它最大的优点是可以双向移动。它还可以产生相对于迭代器在列表中指向的当前位置的前一个和后一个元素的索引,并且可以使用set()方法替换它访问过的最后一个元素。

例子**

在写如何实现之前,先看一个使用列表迭代器ListIterator的小例子:

    import java.util.Vector;
    import java.util.List;
    import java.util.ListIterator;

    public class Test {

        @org.junit.Test
        public void test() {
            List list = new Vector<>();
            list.add("0");
            list.add("1");
            list.add("2");
            list.add("3");
            ListIterator iterator = list.listIterator();
            System.out.println("--------------------向下遍历--------------------");
            while (iterator.hasNext()) {
                int nextIndex = iterator.nextIndex();
                String next = (String) iterator.next();
                //int previousIndex = iterator.previousIndex();
                System.out.println("当前元素:"+next+",当前元素索引:"+nextIndex/*+",前一个元素的索引"+previousIndex*/);
            }
            System.out.println("--------------------向上遍历--------------------");
            while (iterator.hasPrevious()) {
                int previousIndex = iterator.previousIndex();
                String previous = (String) iterator.previous();
                System.out.println("当前元素:"+previous+",当前元素索引:"+previousIndex);
            }
            System.out.println("-----------测试set()和listIterator(n)----------");
            System.out.println(list);
            iterator = list.listIterator(3);
            while(iterator.hasNext()){
                iterator.next();
                iterator.set("5");
            }
            System.out.println(list);
        }
    }

运行结果

    -------向下遍历-------
    当前元素:0,当前元素索引:0
    当前元素:1,当前元素索引:1
    当前元素:2,当前元素索引:2
    当前元素:3,当前元素索引:3
    -------向上遍历-------
    当前元素:3,当前元素索引:3
    当前元素:2,当前元素索引:2
    当前元素:1,当前元素索引:1
    当前元素:0,当前元素索引:0
    -------测试set()和listIterator(n)-------
    [0, 1, 2, 3]
    [0, 1, 2, 5]

方法**

  • listIterator(),list.iterator()用来从容器对象中返回一个指向list开始处的迭代器。
  • listIterator(n),list.iterator()用来从容器对象中返回一个指向列表索引为n的迭代器。
  • next(),获取序列中的下个元素,运行后索引+1。
  • previous(),获取序列中的上个元素,运行后索引-1。
  • nextIndex,获取序列中的下个元素的索引。
  • previousIndex,获取序列中的下个元素的索引。
  • hasNext(),检查序列中向下是否还有元素。
  • hasPrevious(),检查序列中向上是否还有元素。
  • remove(),从列表中删除next()或previous()返回的最后一个元素。这也意味着调用remove()前需要先调用next()或者previous()。
  • add(E e): 将指定的元素插入列表,插入位置为迭代器当前位置之前。
  • set(E e):从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e。

实现**

设计模式(16)-迭代器模式这一文章中曾讲过,迭代器模式中有四个角色:

  • 抽象聚合类Aggregate。在Vector的ListIterator迭代器实现中,没有抽象聚合类。虽然它实现了AbstractList,实现了List,但它向外部提供的创建迭代器的方法listIterator()是它自己的。
  • 具体聚合类ConcreteAggregate。在Vector的ListIterator迭代器实现中,指的是Vector。
  • 抽象迭代器Iterator。在Vector的ListIterator迭代器实现中,指的是ListIterator。
  • 具体迭代器ConcreteIterator。在Vector中的ListIterator迭代器实现中,指的是ListItr。

Vector代码片段

    public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
    {
        /**
         * 保存vector中元素的数组。vector的容量是数组的长度,数组的长度最小值为vector的元素个数。
         *
         * 任何在vector最后一个元素之后的数组元素是null。
         *
         * @serial
         */
        protected Object[] elementData;
        /**
         * vector中实际的元素个数。
         *
         * @serial
         */
        protected int elementCount;

        /**
         * vector需要自动扩容时增加的容量。
         *
         * 当vector的实际容量elementCount将要大于它的最大容量时,vector自动增加的容量。
         *
         * 如果capacityIncrement小于或等于0,vector的容量需要增长时将会成倍增长。
         * @serial
         */
        protected int capacityIncrement;

        /**
         * 序列版本号
         */
        private static final long serialVersionUID = -2767605614048989439L;

        /**
         * 返回一个一开始就指向列表索引为index的元素处的ListIterator
         *
         * 返回的迭代器是fail-fast的
         *
         * @throws IndexOutOfBoundsException {@inheritDoc}
         * @see #listIterator(int)
         */
        public synchronized ListIterator<E> listIterator(int index) {
            if (index < 0 || index > elementCount)
                throw new IndexOutOfBoundsException("Index: "+index);
            return new ListItr(index);
        }

        /**
         * 返回一个一开始就指向列表索引为0的元素处的ListIterator
         *
         * 返回的迭代器是fail-fast的
         *
         * @see #listIterator(int)
         */
        public synchronized ListIterator<E> listIterator() {
            return new ListItr(0);
        }
        /**
         * AbstractList.ListItr的最优化版本
         */
        final class ListItr extends Itr implements ListIterator<E> {
            //用来从list中返回一个指向list索引为index的元素处的迭代器
            ListItr(int index) {
                super();
                cursor = index;
            }

            //获取list中的上个元素
            public boolean hasPrevious() {
                return cursor != 0;
            }

            //获取list中的下个元素的索引
            public int nextIndex() {
                return cursor;
            }

            //获取list中的上个元素的索引
            public int previousIndex() {
                return cursor - 1;
            }

            //获取list中的上个元素
            public E previous() {
                synchronized (Vector.this) {
                    checkForComodification();
                    int i = cursor - 1;
                    if (i < 0)
                        throw new NoSuchElementException();
                    cursor = i;
                    return elementData(lastRet = i);
                }
            }

            //从列表中将next()或previous()返回的最后一个元素返回的最后一个元素更改为指定元素e
            public void set(E e) {
                if (lastRet == -1)
                    throw new IllegalStateException();
                synchronized (Vector.this) {
                    checkForComodification();
                    Vector.this.set(lastRet, e);
                }
            }


            //将指定的元素插入列表,插入位置为迭代器当前位置之前。
            public void add(E e) {
                int i = cursor;
                synchronized (Vector.this) {
                    checkForComodification();
                    Vector.this.add(i, e);
                    expectedModCount = modCount;
                }
                cursor = i + 1;
                lastRet = -1;
            }
        }
    }

Iterator

请参考上文中的Iterator

ListItr.java

作为Vector的内部类。请在上文中的[Vector.java代码片段]中查看。

总结

什么是fail-fast?**

细心地朋友看文章或源码时一定会发现在iterator()和listIterator()的注释中都有一句话:返回的迭代器是fail-fast的。什么是fail-fast?

详情请移步fail-fast详解

Enumeration 和iterator的不同**

已经有了迭代器,Enumeration elements()有什么意义?

详情请移步Iterator与Enumeration

好了,关于Vector与迭代器模式就写到这里。有什么意见建议欢迎在下方留言^^。

赞(0) 打赏

如未加特殊说明,此网站文章均为原创,转载必须注明出处。Java 技术驿站 » Java 8 容器源码-Vector与迭代器模式
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

关注【Java 技术驿站】公众号,每天早上 8:10 为你推送一篇技术文章

扫描二维码关注我!


关注【Java 技术驿站】公众号 回复 “VIP”,获取 VIP 地址永久关闭弹出窗口

免费获取资源

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏