为不可变数据类型实现迭代器

Question

对于我目前的大学课程，我们需要为不可变数据类型实现迭代器。到目前为止一切顺利，没有什么太难的，这是它的样子：

public Iterator<T> iterator(){
    return new Iterator<T>() {
        private int index = 0;

        @Override
        public boolean hasNext() {
            //hasNext implementation
        }

        @Override
        public T next() {
            //Next Implementation
        }
    };

我使用了一个指向数据类型中当前位置的可变变量（索引）。该练习要求我们将每个成员变量设为 final（对于不可变数据类型有意义），但它也要求我们将迭代器中的每个成员变量设为 final（索引）。这就是让我感到困惑的原因，因为我没有看到一种在没有可变变量的情况下迭代数据类型的方法，特别是因为您无法从 next() 方法内部更改迭代器... 我不想要问题的解决方案，我只是想知道，这是否可能，也许是对解决方案的轻微提示...谢谢！

Answer 1

如果让每个成员变量 final 是你的要求，你可以把 index 变成一个数组：

public Iterator<T> iterator(){
    return new Iterator<T>() {
      private final int[] index = {0};
      // ...
    };
}

因为数组元素仍然是可变的，即使对它的引用是 final。但这只会让代码更混乱，因为到处都使用 index[0] 而不是 index。

迭代器本质上是可变的；我想不出让它们不可变的方法，因为您希望它们在您使用时改变。

请注意，简单地使所有成员变量 final 确实使类型不可变。成员变量也必须引用 deeply-immutable 个对象； non-zero 长度数组不能完全不可变，因为您可以随时重新分配它们的元素。

Answer 2

注意：我对 Java 不是很熟悉，我是基于我会在 C# 中做什么，但我会试一试。

注意：我无视 'hints only' 请求，因为它现在已经很晚了，所以我假设它不再相关。否则，请不要阅读第一个代码示例以外的内容（包含或不包含，由您决定）。

你可以通过创建一个迭代器类型来解决这个问题，每次移动到下一个元素时，returns 都是一个新的迭代器对象。所以，基本上，每个移动下一步操作都会 return 三件事：

是否有下一个项目（和往常一样）
下一项是什么（和往常一样）
表示下一项的新迭代器对象（即当前迭代器的副本，但向前移动了一个元素）。

这种设计的优点是您可以在任何时候停止迭代，稍后从该点继续 - 无需先遍历集合中的先前元素。使用 Where() 或 OrderBy() 等 .NET LINQ 方法可能需要大量处理才能再次遍历先前的元素，这在某些情况下可能非常有益。

但是，此新模式不支持内置功能（例如 Java foreach 和 LINQ 的等价物）。此外，迭代器对象可能应该是一种值类型以提高性能（因为会为集合中的每个项目创建一个新实例），但是 Java 不支持自定义值类型。 Java 模式因此看起来像：

interface IterationItem<T> {
    public T getValue();
    public boolean hasNext();
    public IterationItem<T> next();
}

实现如下：

class ListIterationItem<T> implements IterationItem<T>
{
    private List<T> _list; // Could be public (so long as it's read-only)
    private int _index;    // ^
    private T _value;

    public ListIterationItem(List<T> list, int index) {
        _list = list;
        _index = index;
        _value = list[index];
    }

    public T getValue() { return _value; } //Or look up the value on-demand, idk which is better

    public boolean hasNext() {
        return _index + 1 < _list.size())
    }

    public IterationItem<T> next() {
        return new ListIterationItem<T>(_list, _index + 1);
    }
}

你可以这样使用：

List<String> list = Arrays.asList("aaa", "bbb", "ccc");
IterationItem<String> item = new ListIterationItem<String>(list, 0);
while (true) {
    String current = item.getValue();

    //Do something with the current value

    if (item.hasNext()) { item = item.next(); }
};

或者，如果您确实需要避免修改任何字段（例如，当使用不允许您这样做的语言时），您可以使用递归：

void Main() {
    List<String> list = Arrays.asList("aaa", "bbb", "ccc");
    ProcessElements(new ListIterationItem<String>(list, 0));
}
void ProcessElements(IterationItem<T> item) {
    String current = item.getValue();
    //Do something with the current value
    if (item.hasNext()) {
        ProcessElements(item.next());
    }
}

您还可以编写一个方法将任何此类迭代器包装为普通迭代器，以便它可以在 for-each 循环等中使用：

public static Iterable<T> AsIterable<T>(IterationItem<T> item)
    return new Iterable<T>() {
        @Override
        public Iterator<T> iterator() {
            return new Iterator<String>() {
                private IterationItem<T> currentItem = item; //Idk if this works

                @Override
                public boolean hasNext() {
                    return item.hasNext();
                }

                @Override
                public String next() {
                    item = item.next();
                    return item.getValue();
                }

                @Override
                public void remove() { throw new UnsupportedOperationException(); }
            };
        }
    };
}

我想到这个想法来到这里，然后决定对其进行研究 - 但这是迄今为止我找到的最相关的页面，所以我想我应该写下我的想法.如果有人知道类似的东西，我很想知道。

为不可变数据类型实现迭代器

Implementing an iterator for a immutable data type

java

iterator

immutability