迭代器模式(控制访问集合中的元素)

正文

JDK中已经为我们提供了大量实现了迭代器的容器类。 因此我们可以不用关心,诸如:LinkedlistArrayList之间的差别,却仍能保障我们完成工作。

现在我们需要思索,JDK是怎么做到这一切的?现在让我们先利用迭代器实现一个数组类型Array,这个类型需要支持添加、移除、遍历操作。

实现

STEP 1

定义迭代器接口,实现该接口的类拥有迭代器职责。这叫好像在20年前,家门口停了一辆小汽车,别人都会知道你是万元户一样。

public interface Iterable<T> {
    Iterator<T> iterator();
}

STEP 2

定义迭代器对象,除却基本的hasNextnext方法。额外定义了addremove方法,这会辅助我们操作集合中的元素。

注意:迭代器不仅仅为了{迭代},而是为了{操作}集合中的元素。

public interface Iterator<E> {
    boolean hasNext();

    E next();

    boolean add(E e);

    boolean addAll(Collection<? extends E> e);

    boolean remove(E e);
}

STEP 3

实现一个数组Array模拟数组的操作,所有访问集合中元素的操作全权委托给iterator对象。Array并不关心操作元素的细节,它只向外暴露操作接口,对收到的请求转发给iterator处理。

public class Array<E> implements Iterable<E> {

    private transient Iterator<E> iterator;

    public Array() {
        this.iterator = iterator();
    }

    public Array(Collection<? extends E> collection) {
        this.iterator = iterator();
        this.iterator.addAll(collection);
    }

    @Override
    public Iterator<E> iterator() {
        synchronized (this) {
            if (iterator == null) {
                iterator = new ArrayIteratorImpl<>();
            }
        }
        return iterator;
    }

    public void add(E e) {
        this.iterator.add(e);
    }

    public void addAll(Collection<? extends E> e) {
        this.iterator.addAll(e);
    }

    public void remove(E e) {
        this.iterator.remove(e);
    }

}

STEP 4

定义迭代器实现类,使用接口抽象迭代器是为了满足开闭原则,这样Array可以随时更换迭代器而不会影响现有的接口。

ArrayIteratorImpl迭代器实现了对数组的添加、移除操作,如何分配元素、选择用什么容器存储、遍历的顺序、甚至是否启用并行操作,这些对于Array都是不可感知的。

public class ArrayIteratorImpl<E> implements Iterator<E> {

    private transient Object[] elementData = {};
    private transient static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static final int DEFAULT_CAPACITY = 10;
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    protected transient int modCount = 0;
    private int size;

    int cursor;       // index of next element to return
    int lastRet = -1; // index of last element returned; -1 if no such

    private void ensureCapacityInternal(int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }

        ensureExplicitCapacity(minCapacity);
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    @Override
    public boolean hasNext() {
        return cursor != size;
    }

    @Override
    public E next() {
        int i = cursor;
        if (i >= size)
            throw new IllegalArgumentException("");
        Object[] elementData = this.elementData;
        if (i >= elementData.length)
            throw new IllegalArgumentException();
        cursor = i + 1;
        return (E) elementData[lastRet = i];
    }

    @Override
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        lastRet = -1;
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> e) {
        final Object[] a = e.toArray();
        final int numNew = e.size();
        ensureCapacityInternal(this.size + numNew);
        System.arraycopy(a, 0, elementData, size, numNew);
        this.size += numNew;
        lastRet = -1;
        return numNew != 0;
    }

    @Override
    public boolean remove(E o) {
        lastRet = -1;
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    fastRemove(index);
                    return true;
                }
        } else {
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    private void fastRemove(int index) {
        modCount++;
        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
    }

}

STEP 5

客户端调用测试

public class Client {

    public static void main(String[] args) {
        Array<String> array = new Array();
        array.add("清华大学");
        array.add("北京大学");
        array.add("浙江大学");
        array.add("武汉大学");
        array.add("西安交通大学");
        array.add("上海交通大学");
        array.add("人民大学");


        Iterator<String> iterator = array.iterator();
        while (iterator.hasNext()) {
            String item = iterator.next();
            System.out.println(item);
        }
    }
}

总结

迭代器模式属于行为模式类别。

迭代器本质:控制访问集合中的元素

迭代器模式.png

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏架构之路

Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例

概要 上一章,我们学习了Collection的架构。这一章开始,我们对Collection的具体实现类进行讲解;首先,讲解List,而List中ArrayLis...

29540
来自专栏编程理解

数据结构(三):二叉树遍历

前序遍历的方式,也就是对每一棵子树,按照根节点、左子树、右子树的顺序进行访问,也就是根-左-右的访问顺序。因为每一棵非空子树,又可拆分为根节点、左子树和右子树,...

20320
来自专栏Android知识点总结

Java容器源码攻坚战--第二战:ArrayList

18720
来自专栏专注 Java 基础分享

从源码解析TreeMap

     上篇文章我们介绍了HashMap集合,这是一个键值对集合,可以高效的按照键查找数值。但是它有一个缺陷:数据如果是无序的可以是很高效的,但是如果数据...

21380
来自专栏用户画像

6.3.2 B+树基本概念

2)非叶根(不是叶子的根结点)结点至少有两棵子树,其他每个分支结点至少有【m/2】(向下取整)棵子树。(B树是要求至少2棵子树)

10120
来自专栏用户画像

4.5.1 二叉排序树

二叉排序树的查找时从根结点开始,沿着某一分支逐层向下进行比较比较的过程。若二叉排序树非空,将给定值与根结点的关键字比较,若相等,则查找成功;若不等,则当根结点的...

11430
来自专栏desperate633

ArrayList实现原理分析(Java源码剖析)ArrayList使用的存储的数据结构ArrayList的初始化ArrayList是如何动态增长ArrayList如何实现元素的移除ArrayList

ArrayList是我们经常使用的一个数据结构,我们通常把其用作一个可变长度的动态数组使用,大部分时候,可以替代数组的作用,我们不用事先设定ArrayList的...

14230
来自专栏haifeiWu与他朋友们的专栏

聊聊ArrayList源码(基于JDK1.8)

打个广告,楼主自己造的轮子,感兴趣的请点[github]: https://github.com/haifeiWu/lightconf

15040
来自专栏我就是马云飞

ArrayList到底是什么?

ArrayList是日常开发中使用最频繁的集合类。首先这边简单介绍一下ArrayList:

18820
来自专栏cmazxiaoma的架构师之路

Java数据结构和算法(1)--自定义一个数组类和动态数组类

17140

扫码关注云+社区

领取腾讯云代金券