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

3回答

SMILET

对于 C#，您可以LinkedList<T>在好的 ol' C 中使用like：public DoStuff<T>(LinkedList<T> list){    var node = list.First;    while(node != null)    {        // do stuff with node        node = node.Next;    }}该node是类型LinkedListNode<T>。您可以使用访问该值node.Value，使用删除list.Remove(node)。因为T elem你还有list.AddAfter(node, elem), list.AddBefore(node, elem),list.AddFirst(elem)和list.AddLast(elem)。所有这些操作都是 O(1)。你可以用它做各种迭代，如果你只想迭代原始元素，然后在做任何事情之前缓存下一个节点并记住最后一个节点：var lastNode = list.Last;var node = list.First;while(node != lastNode.Next){    var nextNode = node.Next;    // do stuff with node    node = nextNode;}Java 中的等效数据结构也称为LinkedList<E>. 但是，ListIterator<E>在标准List<E>上使用可能更清洁。

0 0

宝慕林4294392

在 C# 中，这很容易用List<T>andfor (...)而不是foreach (...)：using System;using System.Collections.Generic;using System.Linq;namespace Demo{    static class Program    {        static void Main()        {            List<int> list = Enumerable.Range(1, 10).ToList();            for (int i = 0; i < list.Count; ++i)            {                if ((list[i] % 3) == 0) // Remove multiples of 3.                    list.RemoveAt(i--); // NOTE: Post-decrement i                else if ((list[i] % 4) == 0) // At each multiple of 4, add (2*value+1)                    list.Add(list[i] * 2 + 1);                else                    ; // Do nothing.            }            Console.WriteLine(string.Join(", ", list)); // Outputs 1, 2, 4, 5, 7, 8, 10, 17        }    }}这里的关键是使用索引而不是foreach，并且在当前索引之前不要更改任何内容（从阅读您的要求来看，不需要）。但是，如果您确实需要在当前索引之前添加或删除元素，那么这种方法不起作用（或者至少，它变得更加复杂）。

0 0

慕容708150

在 Java 中有CopyOnWriteArrayList可以执行您想要的操作：每次更改任何内容时，它都会创建一个后备数组的副本。但这确实意味着一旦开始迭代，任何迭代都是“一成不变的”，因此您可以随意删除/添加基础集合，而不会影响任何正在运行的迭代器。您还可以构建自己的具有此行为的集合类型。这将是一个 3 班轮：public class ConstantIterationArrayList<T> extends ArrayList<T> {    public Iterator<T> iterator() {        return new ArrayList<T>(this).iterator();    }}（上面制作了列表的副本，然后为您提供了副本的迭代器，从而方便地确保对此列表的任何修改绝对不会影响该迭代器）。这是你的问题的真正问题：上面的代码会不时地制作底层数据存储的副本（我上面的代码片段每次制作迭代器时都会这样做。CopyOnWriteArrayList每次调用remove()or时都会这样做add()）。“复制底层数据存储”操作需要O(n)时间，因为对于两倍大的列表，它需要两倍的时间。ArrayList通常具有这样的属性remove()，除非您要删除列表末尾或非常接近列表末尾的元素，否则操作是O(n)操作：如果列表是两倍，则从列表中删除元素需要两倍的时间大的。幸运的是，现代 CPU 具有相当大的缓存，并且可以在缓存页面内以极快的速度运行。翻译为：尽管数据复制过的感觉效率不高，在实践中，只要在页面左右的时间内支持数组的配合，这是很多快于基于数据存储的LinkedList语义。我们正在谈论最多约 1000 个元素的给予或接受。（请注意，一般来说，您对 a 所做的几乎所有事情LinkedList都是O(n)并且在ArrayList现代 CPU 架构中LinkedList往往表现良好的地方往往表现不佳。重点是：LinkedList也很少是正确的答案！）因此，如果此列表中的项目不超过 1000 项，我会继续使用CopyOnWriteArrayList我在上面为您编写的自定义类。但是，如果您有更多，这里ArrayList就不是正确的数据存储。即使您暂时忘记了不断迭代的需求；调用remove()大型数组列表是一个坏主意（除非删除非常接近列表末尾）。在这种情况下，我会准确地勾勒出您需要对这种数据类型执行哪些操作以及哪些操作确实需要快速，一旦您有了完整的列表，请尝试找到完全符合您需求的集合类型，并且在（可能）情况下，没有任何特定的东西可以完美匹配，请自己制作。像上面一样，当您必须滚动自己的数据类型时，让大部分工作由现有数据类型完成通常是一个好主意，因此要么扩展现有数据类型，要么封装一个。

0 0