在迭代它时从java中的集合中删除项目

Removing items from a collection in java while iterating over it

提问by nash

I want to be able to remove multiple elements from a set while I am iterating over it. Initially I hoped that iterators were smart enough for the naive solution below to work.

我希望能够在迭代时从集合中删除多个元素。最初我希望迭代器足够聪明，可以让下面的简单解决方案工作。

Set<SomeClass> set = new HashSet<SomeClass>();
fillSet(set);
Iterator<SomeClass> it = set.iterator();
while (it.hasNext()) {
    set.removeAll(setOfElementsToRemove(it.next()));
}

But this throws a ConcurrentModificationException.

但这会抛出一个ConcurrentModificationException.

Note that iterator.remove() will not work as far as I can see because I need to remove multiple things at a time. Also assume that it is not possible to identify which elements to remove "on the fly", but it is possible to write the method setOfElementsToRemove(). In my specific case it would take up a lot of memory and processing time to determine what to remove while iterating. Making copies is also not possible because of memory constraints.

请注意，就我所见， iterator.remove() 将无法正常工作，因为我需要一次删除多个内容。还假设无法确定要“即时”删除哪些元素，但可以编写方法setOfElementsToRemove()。在我的特定情况下，它会占用大量内存和处理时间来确定迭代时要删除的内容。由于内存限制，也无法进行复制。

setOfElementsToRemove()will generate some set of SomeClass instances that I want to remove, and fillSet(set)will fill the set with entries.

setOfElementsToRemove()将生成一些我想要删除的 SomeClass 实例集，fillSet(set)并将用条目填充该集。

After searching Stack Overflow I could not find a good solution to this problem but a few hours break later I realized the following would do the job.

在搜索 Stack Overflow 后，我找不到解决这个问题的好方法，但几个小时后我意识到以下方法可以解决这个问题。

Set<SomeClass> set = new HashSet<SomeClass>();
Set<SomeClass> outputSet = new HashSet<SomeClass>();
fillSet(set);
while (!set.isEmpty()) {
    Iterator<SomeClass> it = set.iterator();
    SomeClass instance = it.next();
    outputSet.add(instance);
    set.removeAll(setOfElementsToRemoveIncludingThePassedValue(instance));
}

setOfElementsToRemoveIncludingThePassedValue()will generate a set of elements to remove that includes the value passed to it. We need to remove the passed value so setwill empty.

setOfElementsToRemoveIncludingThePassedValue()将生成一组要删除的元素，其中包括传递给它的值。我们需要删除传递的值，以便为set空。

My question is whether anyone has a better way of doing this or whether there are collection operations that support these kind of removals.

我的问题是是否有人有更好的方法来做到这一点，或者是否有支持此类删除的收集操作。

Also, I thought I would post my solution because there seems to be a need and I wanted to contribute the the excellent resource that is Stack Overflow.

另外，我想我会发布我的解决方案，因为似乎有需要，我想贡献 Stack Overflow 的优秀资源。

采纳答案by Peter

Normally when you remove an element from a collection while looping over the collection, you'll get a Concurrent Modification Exception. This is partially why the Iteratorinterface has a remove() method. Using an iterator is the only safe way to modify a collection of elements while traversing them.

通常，当您在循环遍历集合时从集合中删除元素时，您会得到一个并发修改异常。这就是Iterator接口具有 remove() 方法的部分原因。使用迭代器是在遍历元素集合时修改元素集合的唯一安全方法。

The code would go something like this:

代码将是这样的：

Set<SomeClass> set = new HashSet<SomeClass>();
fillSet(set);
Iterator<SomeClass> setIterator = set.iterator();
while (setIterator.hasNext()) {
    SomeClass currentElement = setIterator.next();
    if (setOfElementsToRemove(currentElement).size() > 0) {
        setIterator.remove();
    }
}

This way you'll safely remove all elements that generate a removal set from your setOfElementsToRemove().

这样您就可以安全地从 setOfElementsToRemove() 中删除所有生成删除集的元素。

EDIT

编辑

Based on a comment to another answer, this may be more what you want:

根据对另一个答案的评论，这可能更符合您的要求：

Set<SomeClass> set = new HashSet<SomeClass>();
Set<SomeClass> removalSet = new HashSet<SomeClass>();
fillSet(set);

for (SomeClass currentElement : set) {
    removalSet.addAll(setOfElementsToRemove(currentElement);
}

set.removeAll(removalSet);

回答by Andrzej Doyle

There's a simple answer to this - use the Iterator.remove() method.

对此有一个简单的答案 - 使用 Iterator.remove() 方法。

回答by Ben S

Why don't you use the iterator's remove methodon the objects you want to remove?

为什么不在要删除的对象上使用迭代器的 remove 方法？

Iterators were introduced mainly because enumerators couldn't handle deleting while enumerating.

引入迭代器主要是因为枚举器在枚举时无法处理删除。

回答by Alexander Pogrebnyak

You should call Iterator.removemethod.

你应该调用Iterator.remove方法。

Also note, that on most java.utilcollections the removemethod will generate exception if the contents of the collection have changed. So, if the code is multi-threaded use extra caution, or use concurrent collections.

另请注意，在大多数java.util集合中，remove如果集合的内容发生更改，该方法将生成异常。因此，如果代码是多线程的，请格外小心，或者使用并发集合。

回答by Kevin Bourrillion

Any solution that involves removing from the set you're iterating while you're iterating it, but not via the iterator, will absolutely not work. Except possibly one: you could use a Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(sizing params)). The catch is that now your iterator is only weakly consistent, meaning that each time you remove an element that you haven't encountered yet, it's undefined whether that element will show up later in your iteration or not. If that's not a problem, this might work for you.

任何涉及在您迭代时从您正在迭代的集合中删除但不通过迭代器的解决方案，都绝对不起作用。除了可能的一个：你可以使用. 问题是现在你的迭代器只是弱一致的，这意味着每次你删除一个你还没有遇到的元素时，这个元素是否会在你的迭代后期出现是不确定的。如果这不是问题，这可能对您有用。Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(sizing params))

Another thing you can do is build up a toRemoveset as you go instead, then set.removeAll(itemsToRemove);only at the end. Or, copy the set before you start, so you can iterate one copy while removing from the other.

你可以做的另一件事是在你进行时建立一个toRemove集合，然后set.removeAll(itemsToRemove);只在最后。或者，在开始之前复制该集合，这样您就可以迭代一个副本，同时从另一个副本中删除。

EDIT: oops, I see Peter Nix had already suggested the toRemoveidea (although with an unnecessarily hand-rolled removeAll).

编辑：哎呀，我看到彼得尼克斯已经提出了toRemove这个想法（尽管有一个不必要的手动removeAll）。

回答by qnoid

Instead of iterating through all the elements in the Set to remove the ones you want, you can actually use Google Collections (not something you can't do it on your own though) and apply a Predicate to maskthe ones you don't need.

与其遍历 Set 中的所有元素以删除您想要的元素，您实际上可以使用 Google Collections（虽然不是您自己无法做到的）并应用 Predicate 来掩盖您不需要的元素.

package com.stackoverflow.q1675037;

import java.util.HashSet;
import java.util.Set;

import org.junit.Assert;
import org.junit.Test;

import com.google.common.base.Predicate;
import com.google.common.collect.Iterables;
import com.google.common.collect.Sets;


public class SetTest
{
public void testFilter(final Set<String> original, final Set<String> toRemove, final Set<String> expected)
{

    Iterable<String> mask = Iterables.filter(original, new Predicate<String>()
    {
        @Override
        public boolean apply(String next) {
        return !toRemove.contains(next);
        }
    });

    HashSet<String> filtered = Sets.newHashSet(mask);

    Assert.assertEquals(original.size() - toRemove.size(), filtered.size());
    Assert.assertEquals(expected, filtered);        
}


@Test
public void testFilterNone()
{
    Set<String> original = new HashSet<String>(){
        {
            this.add("foo");
            this.add("bar");
            this.add("foobar");
        }
    };

    Set<String> toRemove = new HashSet();

    Set<String> expected = new HashSet<String>(){
        {
            this.add("foo");                
            this.add("bar");
            this.add("foobar");
        }
    };

    this.testFilter(original, toRemove, expected);
}

@Test
public void testFilterAll()
{
    Set<String> original = new HashSet<String>(){
        {
            this.add("foo");
            this.add("bar");
            this.add("foobar");
        }
    };

    Set<String> toRemove = new HashSet<String>(){
        {
            this.add("foo");
            this.add("bar");
            this.add("foobar");
        }
    };

    HashSet<String> expected = new HashSet<String>();
    this.testFilter(original, toRemove, expected);
}    

@Test
public void testFilterOne()
{
    Set<String> original = new HashSet<String>(){
        {
            this.add("foo");
            this.add("bar");
            this.add("foobar");
        }
    };

    Set<String> toRemove = new HashSet<String>(){
        {
            this.add("foo");
        }
    };

    Set<String> expected = new HashSet<String>(){
        {
            this.add("bar");
            this.add("foobar");
        }
    };

    this.testFilter(original, toRemove, expected);
}    


@Test
public void testFilterSome()
{
    Set<String> original = new HashSet<String>(){
        {
            this.add("foo");
            this.add("bar");
            this.add("foobar");
        }
    };

   Set<String> toRemove = new HashSet<String>(){
        {
            this.add("bar");
            this.add("foobar");
        }
    };

    Set<String> expected = new HashSet<String>(){
        {
            this.add("foo");
        }
    };

    this.testFilter(original, toRemove, expected);
}    
}

回答by Carl Smotricz

If you have enough memory for one copy of the set, I'll assume you also have enough memory for two copies. The Kafka-esque rules you cite don't seem to forbid that :)

如果你有足够的内存来存放一套副本，我会假设你也有足够的内存来存放两份。你引用的卡夫卡式规则似乎并没有禁止:)

My suggestion, then:

那么我的建议是：

fillSet(set);
fillSet(copy);
for (Object item : copy) {
   if (set.contains(item)) { // ignore if not
     set.removeAll(setOfStuffToRemove())
   }
}

so copy stays intact and just provides the stuff to loop on, while set suffers deletions. Stuff that was removed from set in the meantime will be ignored.

所以 copy 保持完整，只提供循环的东西，而 set 会被删除。同时从集合中删除的东西将被忽略。

回答by joe p

You could try the java.util.concurrent.CopyOnWriteArraySetwhich gives you an iterator that is a snapshot of the set at the time of the iterator creation. Any changes you make to the set (i.e. by calling removeAll()) won't be visible in the iterator, but are visible if you look at the set itself (and removeAll()won't throw).

您可以尝试使用java.util.concurrent.CopyOnWriteArraySet它为您提供一个迭代器，该迭代器是创建迭代器时集合的快照。您对集合所做的任何更改（即通过调用removeAll()）将不会在迭代器中可见，但如果您查看集合本身（并且removeAll()不会抛出），则是可见的。

回答by finnw

It is possible to implement a Setthat allows its elements to be removed whilst iterating over it.

可以实现Set允许在迭代时删除其元素的a 。

I think the standard implementations (HashSet, TreeSet etc.) disallow it because that means they can use more efficient algorithms, but it's not hard to do.

我认为标准实现（HashSet、TreeSet 等）不允许这样做，因为这意味着它们可以使用更高效的算法，但这并不难。

Here's an incomplete example using Google Collections:

这是一个使用 Google Collections 的不完整示例：

import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;

import com.google.common.base.Predicates;
import com.google.common.collect.ForwardingSet;
import com.google.common.collect.Iterators;
import com.google.common.collect.Sets;

public class ConcurrentlyModifiableSet<E>
extends ForwardingSet<E> {
 /** Create a new, empty set */
 public ConcurrentlyModifiableSet() {
  Map<E, Boolean> map = new ConcurrentHashMap<E, Boolean>();
  delegate = Sets.newSetFromMap(map);
 }

 @Override
 public Iterator<E> iterator() {
  return Iterators.filter(delegate.iterator(), Predicates.in(delegate));
 }

 @Override
 protected Set<E> delegate() {
  return this.delegate;
 }

 private Set<E> delegate;
}

Note: The iterator does not support the remove()operation (but the example in the question does not require it.)

注意：迭代器不支持该remove()操作（但问题中的示例不需要它。）

回答by Siri

Copied from the Java API:

从Java API复制：

The List interface provides a special iterator, called a ListIterator, that allows element insertion and replacement,and bidirectional access in addition to the normal operations that the Iterator interface provides. A method is provided to obtain a list iterator that starts at a specified position in the list.

List 接口提供了一个特殊的迭代器，称为 ListIterator， 除了 Iterator 接口提供的正常操作之外，它还允许元素插入和替换以及双向访问。提供了一种方法来获取从列表中的指定位置开始的列表迭代器。

I thought I would point out that the ListIterator which is a special kind of Iterator is built for replacement.

我想我会指出 ListIterator 是一种特殊的 Iterator 是为替换而构建的。