在Java中迭代集合时如何删除其中的元素

Question

我希望可以在遍历集合时删除多个元素。最初，我认为迭代器足够智能以使下面的简单解决方案起作用。

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

但是这会引发一个 ConcurrentModificationException 异常。

请注意，据我所见，iterator.remove()不能起作用，因为我需要一次删除多个元素。同时假设无法在遍历时识别要删除的元素，但可以编写方法setOfElementsToRemove()。在我的情况下，确定要删除哪些元素需要耗费大量的内存和处理时间。由于内存限制，也无法复制。

setOfElementsToRemove()将生成一些要删除的SomeClass实例的集合，并且fillSet(set)将填充集合中的条目。

在搜索了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()函数将生成一个包括传递给它的值在内的要删除的元素集合。我们需要删除传递的值，以便set为空。

我的问题是是否有更好的方法来做这件事，或者是否有支持这些删除操作的集合操作。

此外，我想发布我的解决方案，因为似乎有这样的需求，我希望为优秀的资源Stack Overflow做出贡献。

- nash

---

“next” 是如何用于确定要删除哪些元素的？这可能有助于提供更好的答案。 - qnoid

通过这个问题以及下方的答案，我们可以学到很多东西。 - fastcodejava

Answer 1

通常在遍历集合时，如果你从集合中移除一个元素，你会得到一个Concurrent Modification Exception，这部分是 Iterator 接口添加 remove() 方法的原因。使用迭代器是修改正在遍历的元素集合的唯一安全方式。

代码大致如下：

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();
    }
}

使用这种方式，您可以安全地从setOfElementsToRemove()中删除生成删除集的所有元素。

编辑

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

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);

- Peter

---

是的，您的第二个答案将会起作用，不过可能会遇到内存问题。谢谢！ - nash

看起来不错，但我会用 set.removeAll(removalSet) 替换你第二个例子中的最后一个循环。 - rob

@rob 是的，当它被指出来时很明显。下次我会更好地校对我的代码。 - Peter

Answer 2

不必遍历Set中的所有元素以删除您想要的元素，实际上您可以使用Google Collections（虽然您可以自己完成）并应用谓词来掩盖您不需要的元素。

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);
}    
}

- qnoid

---

A+ 的努力和质量 :) +1 - nash

可以使用 Sets.difference() 来简化。 - finnw

Answer 3

任何涉及在迭代时从集合中删除元素，但不是通过迭代器进行的解决方案都绝对行不通。除非可能有一个：您可以使用Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(sizing params))。问题在于现在您的迭代器只是弱一致性的，这意味着每次您删除尚未遇到的元素时，不能确定该元素是否会在后面的迭代中出现。如果这不是问题，那么这可能适合您。

另一件事是在迭代过程中建立一个toRemove集合，然后仅在最后set.removeAll(itemsToRemove);。或者，在开始之前复制集合，以便您可以在从另一个集合中删除时迭代一个副本。

编辑：糟糕，我看到Peter Nix已经提出了toRemove的想法（尽管使用了一个不必要的手动编写的removeAll）。

- Kevin Bourrillion

Answer 4

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

- joe p

Answer 5

如果您有足够的内存来存储一份副本，我会假设您也有足够的内存来存储两份副本。您提到的卡夫卡式规则似乎并不禁止这样做 :)

那么我的建议是：

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

因此，复制保持完整，只提供循环的内容，而设置则会受到删除的影响。同时，从集合中删除的内容将被忽略。

- Carl Smotricz

Answer 6

使用Iterator.remove()方法即可解决问题。该方法可以删除遍历中的当前元素。

- Andrzej Doyle

---

这种方法在这种情况下行不通。它只能删除迭代器返回的当前元素，我需要一次删除多个元素。 - nash

然后只需对要删除的每个元素调用remove函数。 - Ben S

除非您想根据条件删除一堆元素（即在找到重复元素时同时删除两个元素），否则这是正确的方法。否则，请使用Peter添加的方法。 - Malaxeur

因为我需要在遍历集合期间的任意时间点上删除任意元素。在我的具体情况下，没有办法在“即时”内知道是否应该删除当前元素。抱歉，我应该澄清并进行说明。 - nash

Answer 7

为什么不使用迭代器的remove方法来删除您想要删除的对象？

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

- Ben S

Answer 8

可以实现一个Set，允许在迭代过程中删除其元素。

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

这里是一个使用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;
}

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

- finnw

Answer 9

你应该调用 Iterator.remove 方法。

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

- Alexander Pogrebnyak

Answer 10

从Java API复制：

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

我想指出，ListIterator是一种特殊类型的迭代器，专门用于替换。

- Siri