代码之家 › 专栏 › 技术社区 › nash

在迭代时从Java集合中移除项

set collections java

nash · 技术社区 · 15 年前

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

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

但这会导致 ConcurrentModificationException .

请注意,迭代器.remove()在我看来不会起作用,因为我需要一次删除多个内容。另外,假设不可能确定要“即时”删除哪些元素,但可以编写方法 setOfElementsToRemove() . 在我的特定情况下,迭代时确定要删除的内容需要占用大量的内存和处理时间。由于内存限制,复制也是不可能的。

设置元素存储移动() 将生成一些要删除的someclass实例集,以及 fillSet(set) 将用条目填充集合。

在搜索了堆栈溢出之后,我找不到解决这个问题的好方法,但是几个小时后,我意识到下面的内容可以解决这个问题。

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 将空。

我的问题是,是否有人有更好的方法来实现这一点,或者是否有收集操作支持这种删除。

另外,我认为我会发布我的解决方案,因为这似乎是一个需要,我想贡献优秀的资源,即堆栈溢出。

10 回复 | 直到 9 年前

Peter 15 年前

通常,当您在循环访问集合时从集合中移除元素时,您将得到 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);

qnoid 15 年前

你可以使用google集合(而不是你自己无法做到的)并将谓词应用于面具那些你不需要的。

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

Kevin Bourrillion Gergely 15 年前

任何涉及在迭代时从正在迭代的集合中移除的解决方案(但不是通过迭代器)都绝对不起作用。除了一个:你可以使用 Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>( sizing params )) . 关键是现在你的迭代器 弱一致的 ,也就是说,每次删除尚未遇到的元素时,都无法确定该元素是否将在稍后的迭代中显示。如果这不是问题,这可能对你有用。

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

编辑:哎呀,我看彼得·尼克斯已经建议 托雷夫 想法(尽管用不必要的手摇 removeAll )

coderz 10 年前

你可以试试 java.util.concurrent.CopyOnWriteArraySet 它给您一个迭代器,它是迭代器创建时集合的快照。对设置所做的任何更改(即通过调用 removeAll() )在迭代器中不可见,但在查看集合本身时可见(和 移除所有() 不会扔的。

Andrzej Doyle 15 年前

有一个简单的答案-使用迭代器.remove()方法。

Carl Smotricz 15 年前

如果您有足够的内存来存储一个副本,我假设您也有足够的内存来存储两个副本。你引用的卡夫卡式规则似乎并不禁止这一点。)

我的建议是:

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

所以copy保持不变,只提供循环使用的内容,而set则会被删除。同时从集合中删除的内容将被忽略。

Ben S 15 年前

为什么不使用 iterator's remove method 在要删除的对象上?

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

Alexander Pogrebnyak 15 年前

你应该打电话 Iterator.remove 方法。

还要注意,大多数情况下 java.util 收藏 remove 如果集合的内容已更改,方法将生成异常。因此,如果代码是多线程的,请格外小心,或者使用并发集合。

finnw 15 年前

可以实现 Set 它允许在遍历元素的同时删除元素。

我认为标准实现(hashset、treeset等)不允许这样做,因为这意味着它们可以使用更有效的算法,但并不难做到。

下面是一个使用谷歌收藏的不完整示例:

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() 操作(但问题中的示例不需要它。)

Floern themue 9 年前

抄袭 Java API :

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

我想我会指出,listirator是一种特殊的迭代器,它是为替换而构建的。