Подтвердить что ты не робот

Удаление элементов из коллекции в java при итерации по ней

Я хочу, чтобы удалить несколько элементов из набора, когда я повторяю его. Первоначально я надеялся, что итераторы были достаточно умны, чтобы наивное решение ниже работало.

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

Но это вызывает a ConcurrentModificationException.

Обратите внимание, что iterator.remove() не работает, насколько я могу видеть, потому что мне нужно одновременно удалить несколько вещей. Также предположим, что невозможно определить, какие элементы удалить "на лету", но можно написать метод setOfElementsToRemove(). В моем конкретном случае для определения того, что нужно удалить во время итерации, потребуется много памяти и времени обработки. Создание копий также невозможно из-за ограничений памяти.

setOfElementsToRemove() создаст некоторый набор экземпляров SomeClass, которые я хочу удалить, и fillSet(set) заполнит набор элементами.

После поиска Qaru я не смог найти хорошее решение этой проблемы, но через несколько часов я понял, что следующее будет выполнять эту работу.

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 будет пустым.

Мой вопрос в том, есть ли у кого лучший способ сделать это или есть ли операции сбора, которые поддерживают этот вид абзацев.

Кроме того, я думал, что отправлю свое решение, потому что, похоже, есть необходимость, и я хотел внести отличный ресурс, который является переполнением стека.

4b9b3361

ОТВЕТЫ

Ответ 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);

Ответ 2

Вместо того, чтобы повторять все элементы в наборе, чтобы удалить те, которые вы хотите, вы можете использовать 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);
}    
}

Ответ 3

Любое решение, которое включает удаление из набора, который вы выполняете, пока вы его итерации, но не через итератор, абсолютно не работает. За исключением, возможно, одного: вы можете использовать Collections.newSetFromMap(new ConcurrentHashMap<SomeClass, Boolean>(sizing params)). Уловка заключается в том, что теперь ваш итератор только слабо согласован, а это означает, что каждый раз, когда вы удаляете элемент, который вы еще не встречали, он undefined будет ли этот элемент появляться позже на вашей итерации или нет. Если это не проблема, это может сработать для вас.

Еще одна вещь, которую вы можете сделать, - это создать toRemove, как вы идете, а затем set.removeAll(itemsToRemove); только в конце. Или скопируйте набор перед запуском, чтобы вы могли перебирать один экземпляр, удаляя его из другого.

EDIT: я вижу, что Питер Никс уже предложил идею toRemove (хотя и с ненужным ручным removeAll).

Ответ 4

Вы можете попробовать java.util.concurrent.CopyOnWriteArraySet, который дает вам итератор, который является моментальным снимком набора во время создания итератора. Любые изменения, внесенные в набор (т.е. Вызов removeAll()), не будут отображаться в итераторе, но будут видны, если вы посмотрите на сам набор (и removeAll() не будет бросать).

Ответ 5

Здесь есть простой ответ: используйте метод Iterator.remove().

Ответ 6

Если у вас достаточно памяти для одной копии набора, я предполагаю, что у вас также достаточно памяти для двух копий. Правила Кафки-эска, которые вы цитируете, не запрещают:)

Мое предложение:

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

поэтому копия остается неповрежденной и просто предоставляет материал для циклического включения, а набор - для удаления. Материал, который был удален из набора, будет игнорироваться.

Ответ 7

Почему бы вам не использовать метод удаления итератора для объектов, которые вы хотите удалить?

Итераторы были введены главным образом потому, что счетчики не могли обрабатывать удаление при перечислении.

Ответ 8

Вы должны вызвать метод Iterator.remove.

Также обратите внимание, что в большинстве коллекций java.util метод remove генерирует исключение, если содержимое коллекции изменилось. Итак, если код многопоточный, используйте дополнительную осторожность или используйте параллельные коллекции.

Ответ 9

Можно реализовать Set, который позволяет удалять его элементы во время итерации по нему.

Я думаю, что стандартные реализации (HashSet, TreeSet и т.д.) запрещают это, потому что это означает, что они могут использовать более эффективные алгоритмы, но это не сложно.

Вот неполный пример использования Google Коллекций:

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() (но пример в вопросе не требует этого.)

Ответ 10

Скопировано из Java API:

Интерфейс List предоставляет специальный итератор, называемый ListIterator, , который позволяет вставлять и заменять элементы, и двунаправленный доступ в дополнение к обычным операциям, которые Итератор интерфейс обеспечивает. Предоставляется метод для получения итератора списка который начинается в указанной позиции в списке.

Я думал, что хочу указать, что ListIterator, который является особым типом Iterator, создан для замены.