在Java中克隆一个迭代器？

Question

在一个游戏中，我有一个玩家列表，就像这样：

LinkedList<String> players = new LinkedList<String>();

我想让每个玩家与其他所有玩家交互，所以我写了两个嵌套的循环：

Iterator<String> i1 = players.iterator();
while (i1.hasNext()) {
    String p1 = i1.next();
    Iterator<String> i2 = players.iterator();
    // But I want to do this: Iterator<String> i2 = i1.clone();
    while (i2.hasNext()) {
        String p2 = i2.next();
        System.out.println("Interact: " + p1 + ", " + p2);
    }
}

由于我只希望每对玩家仅进行一次互动，因此我希望内部循环从外部循环的当前玩家之后的玩家开始。所以我想克隆迭代器，但是这样不会编译。

那么，我应该做些什么呢？

- Thomas Padron-McCarthy

---

为什么不直接使用 ArrayList<String> 呢？使用这种数据结构会使得基于位置的算法变得非常简单。 - Kirk Woll

这样会导致将玩家A与A匹配吗？ - matt b

@Kirk：是的，ArrayList 可以使用，但由于我可能需要在列表中间插入和删除玩家，所以我想要一个 LinkedList。 - Thomas Padron-McCarthy

@Thomas，通常情况下，重新排列数组比使用LinkedList更快，因为实例化列表元素条目的成本通常比简单地移动内存要高。 - Kirk Woll

可能是Java中克隆迭代器的重复问题。 - gmarmstrong

Answer 1

以下代码能实现该功能：

ListIterator<String> i1 = players.listIterator(0);
while (i1.hasNext()) {
    String p1 = i1.next();
    ListIterator<String> i2 = players.listIterator(i1.nextIndex());
    while (i2.hasNext()) {
        String p2 = i2.next();
        System.out.println("Interact: " + p1 + ", " + p2);
    }
}

它依赖于ListIterator从给定位置开始，并且知道其当前位置的能力。

- NPE

---

AIX再次发威。+1，完美的解决方案。 - aioobe

谢谢！但是，有一个问题：listIterator(int)方法如何工作 - 它不是从列表的头开始迭代到给定位置，对吗？ - Thomas Padron-McCarthy

@ThomasPadron-McCarthy：这并没有作为接口的一部分来指定。然而，考虑到链表的性质，它几乎肯定会发生这种情况。另一方面，我不知道任何避免这种情况的解决方案。 - NPE

@aix，对你的评论点个赞。然而，如果楼主愿意从 O(1) 的内存消耗上升到 O(n) 的话，我的回答中有一个显而易见的解决方案。 - aioobe

我最终将我的LinkedList更改为ArrayList。在其他地方可能会慢一些，但至少我不会有（大多数是美学上的）不必要遍历的问题。但我仍然不明白为什么他们决定不让你克隆迭代器。我甚至考虑使用专门构建的列表，带有可克隆的迭代器，但在我知道需要性能之前，我会等待。 - Thomas Padron-McCarthy

对于Java的LinkedList，它会从起点或终点开始遍历，取决于哪个距离更短。 - Paŭlo Ebermann

Answer 2

除了aix的答案之外，我想指出无论你如何创建一个从特定索引开始的迭代器，它都将是一个线性操作。如果不是这样，您将能够在常数时间内对列表进行任意访问。

elementN = createIterator(linkedList, N).next();

这可能会产生矛盾。

因此，在你的情况下，我认为最有效的解决方案实际上是执行

List<String> tmp = new ArrayList<String>(players);
for (int p1 = 0; p1 < tmp.size(); p1++)
    for (int p2 = p1+1; p2 < tmp.size(); p2++)
        System.out.println("Interact: " + tmp.get(p1) + ", " + tmp.get(p2));

请注意，这种解决方法的复杂度与aix的解决方案相同，仍为O(n²)，但可能具有更小的常数因子。

- aioobe

---

我不同意。如果你有一个指向所需索引的迭代器，只要接口允许，你应该能够立即到达该索引。这个想象中的i1.clone()方法将是 O(1)，而 players.listIterator(i1.nextIndex()) 则是 O(n)。 clone() 方法会提供当前节点的克隆迭代器，消除了在列表中迭代到该点的需要。 - Michael Dorst

原则上你是正确的。虚构克隆方法很容易实现。但在这种情况下，OP最可能指的是java.util.LinkedList，它不支持克隆。关于这个话题有很多问题，例如https://dev59.com/cG025IYBdhLWcg3wf2SE - aioobe

Answer 3

对于避免与listIterator(int)相关的线性成本的解决方案（NPE的答案），请参见我的类似问题的答案。简而言之，只要您不关心访问列表的顺序，就可以从最后一个元素开始外部循环并向后迭代，从第一个元素开始内部循环并向前迭代，直到两个迭代器相遇。调用list.listIterator(list.size())很快，因为list是LinkedList，即双向链表，并且访问最后一个元素不需要迭代整个列表。请参见下面的示例：

public static int iterRevIterator(List<Integer> list) {
    int sum = 0;
    for(ListIterator<Integer> outer = list.listIterator(list.size()); outer.hasPrevious(); ) {
        Integer oVal = outer.previous();
        for(ListIterator<Integer> inner = list.listIterator(); inner.nextIndex() <= outer.previousIndex(); ) {
            sum += oVal * inner.next();
        }
    }
    return sum;
}

- Luca Citi