Java 在迭代期间向集合添加元素

Adding elements to a collection during iteration

提问by grifaton

Is it possible to add elements to a collection while iterating over it?

是否可以在迭代时将元素添加到集合中？

More specifically, I would like to iterate over a collection, and if an element satisfies a certain condition I want to add some other elements to the collection, and make sure that these added elements are iterated over as well. (I realise that this couldlead to an unterminating loop, but I'm pretty sure it won't in my case.)

更具体地说，我想迭代一个集合，如果一个元素满足某个条件，我想向集合中添加一些其他元素，并确保这些添加的元素也被迭代。（我意识到这可能会导致无限循环，但我很确定在我的情况下不会。）

The Java Tutorialfrom Sun suggests this is not possible: "Note that Iterator.removeis the onlysafe way to modify a collection during iteration; the behavior is unspecified if the underlying collection is modified in any other way while the iteration is in progress."

Sun的Java 教程表明这是不可能的：“请注意，这Iterator.remove是在迭代期间修改集合的唯一安全方法；如果在迭代进行期间以任何其他方式修改底层集合，则行为是未指定的。”

So if I can't do what I want to do using iterators, what do you suggest I do?

所以如果我不能使用迭代器做我想做的事情，你建议我做什么？

采纳答案by Avi

How about building a Queue with the elements you want to iterate over; when you want to add elements, enqueue them at the end of the queue, and keep removing elements until the queue is empty. This is how a breadth-first search usually works.

用你想要迭代的元素构建一个队列怎么样？当你想添加元素时，将它们排在队列的末尾，并不断移除元素，直到队列为空。这就是广度优先搜索通常的工作方式。

回答by Matthew Flaschen

In general, it's not safe, though for some collections it may be. The obvious alternative is to use some kind of for loop. But you didn't say what collection you're using, so that may or may not be possible.

在一般的，这不是安全的，但对于一些藏品可能。显而易见的替代方法是使用某种 for 循环。但是你没有说你使用的是什么集合，所以这可能也可能不可能。

回答by coobird

There are two issues here:

这里有两个问题：

The first issue is, adding to an Collectionafter an Iteratoris returned. As mentioned, there is no defined behavior when the underlying Collectionis modified, as noted in the documentation for Iterator.remove:

第一个问题是，Collection在Iterator返回之后添加到一个。如前所述，Collection修改底层时没有定义的行为，如文档中所述Iterator.remove：

... The behavior of an iterator is unspecified if the underlying collection is modified while the iteration is in progress in any way other than by calling this method.

...如果在迭代正在进行时以除调用此方法以外的任何方式修改了底层集合，则迭代器的行为是未指定的。

The second issue is, even if an Iteratorcould be obtained, and then return to the same element the Iteratorwas at, there is no guarantee about the order of the iteratation, as noted in the Collection.iteratormethod documentation:

第二个问题是，即使Iterator可以获取an ，然后返回到与之前相同的元素Iterator，也无法保证迭代的顺序，如Collection.iterator方法文档中所述：

... There are no guarantees concerning the order in which the elements are returned (unless this collection is an instance of some class that provides a guarantee).

...没有关于元素返回顺序的保证（除非此集合是提供保证的某个类的实例）。

For example, let's say we have the list [1, 2, 3, 4].

例如，假设我们有 list [1, 2, 3, 4]。

Let's say 5was added when the Iteratorwas at 3, and somehow, we get an Iteratorthat can resume the iteration from 4. However, there is no guarentee that 5will come after 4. The iteration order may be [5, 1, 2, 3, 4]-- then the iterator will still miss the element 5.

比方说，5加入时Iterator是在3，不知何故，我们得到了一个Iterator能够恢复从迭代4。但是，没有保证5之后会出现4。迭代顺序可能是[5, 1, 2, 3, 4]- 那么迭代器仍然会错过元素5。

As there is no guarantee to the behavior, one cannot assume that things will happen in a certain way.

由于无法保证行为，人们不能假设事情会以某种方式发生。

One alternative could be to have a separate Collectionto which the newly created elements can be added to, and then iterating over those elements:

一种替代方法是Collection将新创建的元素添加到一个单独的对象中，然后迭代这些元素：

Collection<String> list = Arrays.asList(new String[]{"Hello", "World!"});
Collection<String> additionalList = new ArrayList<String>();

for (String s : list) {
    // Found a need to add a new element to iterate over,
    // so add it to another list that will be iterated later:
    additionalList.add(s);
}

for (String s : additionalList) {
    // Iterate over the elements that needs to be iterated over:
    System.out.println(s);
}

Edit

编辑

Elaborating on Avi's answer, it is possible to queue up the elements that we want to iterate over into a queue, and remove the elements while the queue has elements. This will allow the "iteration" over the new elements in addition to the original elements.

详细说明Avi 的答案，可以将我们想要迭代的元素排入队列，并在队列中有元素时删除元素。这将允许对除原始元素之外的新元素进行“迭代”。

Let's look at how it would work.

让我们看看它是如何工作的。

Conceptually, if we have the following elements in the queue:

从概念上讲，如果队列中有以下元素：

[1, 2, 3, 4]

[1, 2, 3, 4]

And, when we remove 1, we decide to add 42, the queue will be as the following:

并且，当我们删除时1，我们决定添加42，队列将如下所示：

[2, 3, 4, 42]

[2, 3, 4, 42]

As the queue is a FIFO(first-in, first-out) data structure, this ordering is typical. (As noted in the documentation for the Queueinterface, this is not a necessity of a Queue. Take the case of PriorityQueuewhich orders the elements by their natural ordering, so that's not FIFO.)

由于队列是FIFO（先进先出）数据结构，因此这种排序是典型的。（如Queue接口文档中所述，这不是 a 的必要条件Queue。以PriorityQueue元素按自然顺序排序的情况为例，这不是 FIFO。）

The following is an example using a LinkedList(which is a Queue) in order to go through all the elements along with additional elements added during the dequeing. Similar to the example above, the element 42is added when the element 2is removed:

以下是使用 a LinkedList（即 a Queue）的示例，以便遍历所有元素以及在出队期间添加的其他元素。与上面的例子类似，42当元素2被移除时添加元素：

Queue<Integer> queue = new LinkedList<Integer>();
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);

while (!queue.isEmpty()) {
    Integer i = queue.remove();
    if (i == 2)
        queue.add(42);

    System.out.println(i);
}

The result is the following:

结果如下：

1
2
3
4
42

As hoped, the element 42which was added when we hit 2appeared.

正如所希望的，42我们点击时添加的元素2出现了。

回答by McDowell

You may also want to look at some of the more specialised types, like ListIterator, NavigableSetand (if you're interested in maps) NavigableMap.

您可能还想查看一些更专业的类型，例如ListIterator、NavigableSet和（如果您对地图感兴趣）NavigableMap。

回答by javamonkey79

Using iterators...no, I don't think so. You'll have to hack together something like this:

使用迭代器...不，我不这么认为。你必须像这样一起破解：

    Collection< String > collection = new ArrayList< String >( Arrays.asList( "foo", "bar", "baz" ) );
    int i = 0;
    while ( i < collection.size() ) {

        String curItem = collection.toArray( new String[ collection.size() ] )[ i ];
        if ( curItem.equals( "foo" ) ) {
            collection.add( "added-item-1" );
        }
        if ( curItem.equals( "added-item-1" ) ) {
            collection.add( "added-item-2" );
        }

        i++;
    }

    System.out.println( collection );

Which yeilds:
[foo, bar, baz, added-item-1, added-item-2]

哪个产量：
[foo, bar, baz, added-item-1, added-item-2]

回答by Nat

I prefer to process collections functionally rather than mutate them in place. That avoids this kind of problem altogether, as well as aliasing issues and other tricky sources of bugs.

我更喜欢从功能上处理集合，而不是就地改变它们。这完全避免了这种问题，以及别名问题和其他棘手的错误来源。

So, I would implement it like:

所以，我会像这样实现它：

List<Thing> expand(List<Thing> inputs) {
    List<Thing> expanded = new ArrayList<Thing>();

    for (Thing thing : inputs) {
        expanded.add(thing);
        if (needsSomeMoreThings(thing)) {
            addMoreThingsTo(expanded);
        }
    }

    return expanded;
}

回答by Michael Zilbermann

IMHO the safer way would be to create a new collection, to iterate over your given collection, adding each element in the new collection, and adding extra elements as needed in the new collection as well, finally returning the new collection.

恕我直言，更安全的方法是创建一个新集合，遍历给定的集合，在新集合中添加每个元素，并根据需要在新集合中添加额外的元素，最后返回新集合。

回答by dmeister

Besides the solution of using an additional list and calling addAll to insert the new items after the iteration (as e.g. the solution by user Nat), you can also use concurrent collections like the CopyOnWriteArrayList.

除了使用附加列表并调用 addAll 在迭代后插入新项目的解决方案（例如用户 Nat 的解决方案），您还可以使用并发集合，如CopyOnWriteArrayList。

The "snapshot" style iterator method uses a reference to the state of the array at the point that the iterator was created. This array never changes during the lifetime of the iterator, so interference is impossible and the iterator is guaranteed not to throw ConcurrentModificationException.

“快照”样式的迭代器方法使用对创建迭代器时数组状态的引用。这个数组在迭代器的生命周期内永远不会改变，所以干扰是不可能的，并且迭代器保证不会抛出 ConcurrentModificationException。

With this special collection (usually used for concurrent access) it is possible to manipulate the underlying list while iterating over it. However, the iterator will not reflect the changes.

使用这个特殊的集合（通常用于并发访问），可以在迭代的同时操作底层列表。但是，迭代器不会反映更改。

Is this better than the other solution? Probably not, I don't know the overhead introduced by the Copy-On-Write approach.

这比其他解决方案更好吗？可能不是，我不知道 Copy-On-Write 方法引入的开销。

回答by PatlaDJ

Actually it is rather easy. Just think for the optimal way. I beleive the optimal way is:

其实还是比较容易的。只考虑最佳方式。我相信最佳方法是：

for (int i=0; i<list.size(); i++) {
   Level obj = list.get(i);

   //Here execute yr code that may add / or may not add new element(s)
   //...

   i=list.indexOf(obj);
}

The following example works perfectly in the most logical case - when you dont need to iterate the added new elements before the iteration element. About the added elements after the iteration element - there you might want not to iterate them either. In this case you should simply add/or extend yr object with a flag that will mark them not to iterate them.

以下示例在最合乎逻辑的情况下完美运行 - 当您不需要在迭代元素之前迭代添加的新元素时。关于迭代元素之后添加的元素 - 您可能也不希望迭代它们。在这种情况下，您应该简单地添加/或扩展带有标志的 yr 对象，该标志将标记它们而不是迭代它们。

回答by csd

public static void main(String[] args)
{
    // This array list simulates source of your candidates for processing
    ArrayList<String> source = new ArrayList<String>();
    // This is the list where you actually keep all unprocessed candidates
    LinkedList<String> list = new LinkedList<String>();

    // Here we add few elements into our simulated source of candidates
    // just to have something to work with
    source.add("first element");
    source.add("second element");
    source.add("third element");
    source.add("fourth element");
    source.add("The Fifth Element"); // aka Milla Jovovich

    // Add first candidate for processing into our main list
    list.addLast(source.get(0));

    // This is just here so we don't have to have helper index variable
    // to go through source elements
    source.remove(0);

    // We will do this until there are no more candidates for processing
    while(!list.isEmpty())
    {
        // This is how we get next element for processing from our list
        // of candidates. Here our candidate is String, in your case it
        // will be whatever you work with.
        String element = list.pollFirst();
        // This is where we process the element, just print it out in this case
        System.out.println(element);

        // This is simulation of process of adding new candidates for processing
        // into our list during this iteration.
        if(source.size() > 0) // When simulated source of candidates dries out, we stop
        {
            // Here you will somehow get your new candidate for processing
            // In this case we just get it from our simulation source of candidates.
            String newCandidate = source.get(0);
            // This is the way to add new elements to your list of candidates for processing
            list.addLast(newCandidate);
            // In this example we add one candidate per while loop iteration and 
            // zero candidates when source list dries out. In real life you may happen
            // to add more than one candidate here:
            // list.addLast(newCandidate2);
            // list.addLast(newCandidate3);
            // etc.

            // This is here so we don't have to use helper index variable for iteration
            // through source.
            source.remove(0);
        }
    }
}