可在迭代过程中发生变化的可迭代集合

13 浏览
0 Comments

可在迭代过程中发生变化的可迭代集合

在Java（和如果你知道的话，C#）中有一种可以进行迭代的集合数据结构，具有以下属性：

  • 当前元素可以被移除，而不会影响当前迭代器（已经开始迭代的迭代器的剩余迭代）。
  • 可以添加新元素，但是这些元素也不会影响当前迭代器，即在当前迭代器的迭代仍在进行时不会作为迭代值包含。在我的情况下，每次迭代只会添加一个新元素，但在从可迭代对象获取新迭代器之前不应该看到任何新元素。
  • 元素的顺序无关紧要。

实际上，存在一个输入列表和一个输出列表的项目。遍历输入列表，并将其中一些项目复制到新列表中。在迭代过程中可以向新列表添加一些新元素。迭代结束后，旧的输入列表将被新的输出列表替换。整个过程本身位于一个循环中。

因此，与每次将元素复制到新构造的集合对象相比，似乎效率较低，后者具有这些添加/移除属性。

我在想的是一种队列，让我可以预览当前项目，然后将其出队或不出队，并继续下一个项目。我可以向队列头部添加更多项目，但是因为我正在向尾部移动，所以看不到它们。一个双向链表可能具有这些属性，对吗？

如果你真的想知道它是用来做什么的，那是为了改进我的一个答案中的第二个大代码块。

0

3 答案

0 Comments

在Java中，有一种叫做CopyOnWriteArrayList的类可以实现你想要的功能：每次修改数据时都会复制一份备份数组。这意味着一旦开始遍历，遍历过程中的数据是“固定的”，因此你可以随意对底层集合进行删除/添加操作，而不会影响正在运行的迭代器。

你也可以构建自己的集合类型以具有这种行为。只需三行代码：

public class ConstantIterationArrayList<T> extends ArrayList<T> {
    public Iterator<T> iterator() {
        return new ArrayList<T>(this).iterator();
    }
}

（上述代码会复制列表，并为复制的列表提供一个迭代器，从而确保对此列表的任何修改都不会影响该迭代器）。

以下是你问题的真正问题：

上述方法会不时地复制底层数据存储（上述代码片段在每次创建迭代器时都会复制一次列表，CopyOnWriteArrayList在每次调用remove()或add()时都会复制）。复制底层数据存储的操作的时间复杂度是O(n)，也就是说，如果列表的大小翻倍，复制操作需要的时间也会翻倍。

ArrayList的一般属性是，除非你删除的元素在列表末尾或非常靠近列表末尾，否则remove()操作的时间复杂度是O(n)。如果列表的大小翻倍，从列表中删除一个元素所需的时间将翻倍。

幸运的是，现代CPU具有较大的缓存，并且可以在缓存页内工作得非常快。这意味着尽管复制数据可能感觉效率低下，但实际上，只要备份数组适合一个页面左右的大小，它比基于LinkedList语义的数据存储要快得多。这里大约是1000个元素左右。（注意，通常对LinkedList执行的几乎所有操作都是O(n)，而ArrayList在现代CPU架构下表现良好，而LinkedList的性能很差。重点是，LinkedList很少是正确的答案！）

因此，如果列表中的项目不超过1000个，我建议使用CopyOnWriteArrayList或我上面为你写的自定义类。

然而，如果超过这个数量，ArrayList不是在这里使用的正确数据存储方式。即使你暂时忘记了常量迭代的需求；在大型ArrayList上调用remove()是一个坏主意（除非删除的元素非常靠近列表的末尾）。在这种情况下，我建议你精确地描述你需要在这个数据类型上执行的操作，并确定哪些操作需要快速执行，一旦你有了完整的列表，尝试找到一个完全符合你需求的集合类型，如果没有完全匹配的特定集合类型，可以自己创建一个。就像上面所说的，当你不得不自己创建数据类型时，最好让大部分工作由现有的数据类型完成，所以要么扩展现有的数据类型，要么封装一个。

那么，我最初在链接答案中提到的实现可能是我能得到的最好的解决方案，不是吗？

0
0 Comments

在C#中，我们可以使用`List`和`for (...)`来实现可变的可迭代集合，而不是使用`foreach (...)`。关键是使用索引而不是`foreach`，并且不要在当前索引之前改变任何内容。但是，如果需要在当前索引之前添加或删除元素，则这种方法就不起作用了，或者至少会变得更加复杂。

在上述代码中，我们创建了一个名为`list`的`List`对象，其中包含了从1到10的整数。然后，我们使用`for`循环遍历列表中的每个元素。如果元素是3的倍数，我们就移除它；如果元素是4的倍数，我们就在当前元素后添加一个新元素（2*当前元素+1）；否则，我们不做任何操作。最后，我们将修改后的列表中的元素用逗号分隔的形式输出。

但是，上述方法只适用于在当前索引之后添加或删除元素的情况。如果需要在当前索引之前添加或删除元素，这种方法就不起作用了，或者至少会变得更加复杂。此外，需要注意的是，从列表中删除元素的性能是O(n)，n为列表中剩余元素的数量。

根据问题的要求，我们期望最终列表中的元素为1、2、4、5、7、8、10和17。但实际上，由于在迭代过程中添加了新元素，并且在当前迭代之后的迭代中也会对这些新元素进行迭代，因此最终列表中的元素为1、2、4、5、7、8、10、17和新添加的元素。

根据的问题，我们可以得出一个解决方法：根据实际需求，创建一个新的集合可能是最好且最简单的方法。通过创建新的集合，我们可以在迭代过程中添加或删除元素，而不会影响当前迭代或任何未来的迭代。

总结起来，问题的出现是因为在迭代过程中对集合进行了修改，而解决方法是创建一个新的集合来操作元素，以避免在迭代过程中对集合进行修改。

0
0 Comments

在使用迭代过程中，如果在迭代过程中可以修改的可迭代集合，会导致一些问题。解决这个问题的方法是在迭代过程中跳过新添加的元素。具体来说，对于C#，可以使用LinkedList来解决这个问题。通过使用LinkedList的First属性和Next属性，可以在迭代过程中访问节点的值、删除节点以及添加新的节点。使用LinkedList可以实现各种迭代操作。如果只想迭代原始元素，可以在执行任何操作之前缓存下一个节点，并记住最后一个节点。对于Java，相应的数据结构是LinkedList。然而，在标准List上使用ListIterator可能更简洁。要避免在迭代过程中看到新元素，可以通过跳过添加的元素来解决问题。具体方法是在调用listIterator.add(e)添加元素后，立即调用listIterator.next()。

0