Iterator iterator = collection.iterator();
while (iterator.hasNext()) {
Object element = iterator.next();
if (iDontLikeThisElement(element)) {
iterator.remove();
}
}
Не, всё же выглядело. Но никаких других вариантов не было. Позже в пятой джаве появляется цикл foreach, и использование итераторов становится преимущественно неявным:
for (E element : collection) {
if (iDonLikeThisElement(element)) {
collection.remove(element); // облом! ConcurrentModificationException!
}
}
«Ишь чего захотели! Юзайте явные итераторы, дорогие кастомеры, и не выделывайтесь» — наверное что-то такое думали разработчики джава платформы работая над пятеркой.
В шестой джаве появляется пакет конкаренси. Теперь можно cделать так:
Set<String> set = Collections.newSetFromMap(new ConcurrentHashMap<>());
И получить set который не кидается ConcurrentModificationException-ами. Но опять же счастье не совсем полное:
- Oбычно многопоточность нам вовсе не нужна
- Не подерживаются null ни в качестве элементов, ни ключей, ни значений. Да и ладно, честно сказать.
- Порядок элементов не определён и может меняться — вот это гораздо хуже. Т.е. если мы бежим по элементам и ведём некий подсчёт с потерей точности, то нас могут поджидать неприятные сюрпризы и разные результаты на одних и тех же наборах данных, что, скажем, не всегда хорошо. Так же бывают задачи, где желательно сохранить именно изначальный порядок данных. Ну и вот такие штуки тоже имеют место быть:
Вывод aaa |
Вывод aaa |
- В рамках одного треда можно добавлять и удалять элементы в любой момент без всяких эксепшенов. И конечно же за константное время.
- Можно хранить null-ы, если вдруг хочется.
- Элементы обходятся в том порядке в котором были добавлены.
Всё это с легкостью достигается с помощью слегка доработанного двунаправленного списка:
- Удаляя элемент мы не будем обнулять ссылку на следующий, т. е. eсли итератор стоит на данном элементе, то он сможет пройти дальше.
- В конце списка поместим фэйковый элемент, который превращается в настоящий когда в список что-нибудь добавляют. Т.е. даже добравшись до конца списка итератор не упирается в null и может продолжить работу если в коллекции появляется новый элемент. Далее в коде этот фейковый элемент называется placeholder.
Посмотрим на картинку.
- В начале у нас есть элементы A, B, C, D.
- Затем элементы C и D удаляются.
- Добавляется новый элемент E.
Можно заметить, что если на момент удалений у нас был итератор указывавший на элемент С, то двигаясь дальше по ссылкам он доберется до вновь добавленного элемента E. Если же никакого итератора не было, то ничто не мешает сборщику мусора освободить память от удаленных элементов.
Ну и для константного времени доступа нам, очевидно, нужен хэшмап:
import java.util.AbstractSet;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.NoSuchElementException;
public class LinkedSet<E> extends AbstractSet<E> {
private static class LinkedElement<E> {
E value;
boolean exists;
LinkedElement<E> prev;
LinkedElement<E> next;
}
private Map<E, LinkedElement<E>> map = new HashMap<>();
private LinkedElement<E> placeholder = new LinkedElement<>();
private LinkedElement<E> head = placeholder;
@Override
public boolean isEmpty() { return head == placeholder; }
@Override
public int size() { return map.size(); }
@Override
public boolean contains(Object o) { return map.containsKey(o); }
// здесь будут методы для добавления, удаления, итерирования
}
Добавление элемента:
@Override
public boolean add(E e) {
LinkedElement<E> element = map.putIfAbsent(e, placeholder);
if (element != null) {
return false;
}
element = placeholder;
element.exists = true;
element.value = e;
placeholder = new LinkedElement<>();
placeholder.prev = element;
element.next = placeholder;
return true;
}
Удаление:
@Override
public boolean remove(Object o) {
LinkedElement<E> removedElement = map.remove(o);
if (removedElement == null) {
return false;
}
removeElementFromLinkedList(removedElement);
return true;
}
private void removeElementFromLinkedList(LinkedElement<E> element) {
element.exists = false;
element.value = null;
element.next.prev = element.prev;
if (element.prev != null) {
element.prev.next = element.next;
element.prev = null;
} else {
head = element.next;
}
}
Итератор:
@Override
public Iterator<E> iterator() {
return new ElementIterator();
}
private class ElementIterator implements Iterator<E> {
LinkedElement<E> next = head;
LinkedElement<E> current = null;
LinkedElement<E> findNext() {
LinkedElement<E> n = next;
while (!n.exists && n.next != null) {
next = n = n.next;
}
return n;
}
@Override
public boolean hasNext() {
return findNext().exists;
}
@Override
public E next() {
LinkedElement<E> n = findNext();
if (!n.exists) {
throw new NoSuchElementException();
}
current = n;
next = n.next;
return n.value;
}
@Override
public void remove() {
if (current == null) {
throw new IllegalStateException();
}
if (map.remove(current.value, current)) {
removeElementFromLinkedList(current);
} else {
throw new NoSuchElementException();
}
}
}
Теперь можно делать так:
Set<Integer> set = new LinkedSet<>();
// ... put some numbers
set.stream().filter(v -> v % 2 == 0).forEach(set::remove);
Понятно, что аналогично можно сконструировать и LinkedMap. Вот в общем-то и всё, ещё один велосипед готов. Почему подобным образом не доработали библиотечные LinkedHashMap и LinkedHashSet? Кто знает, возможно чтобы джависты завидовали джаваскриптистам.
Комментарии (27)
AndreyRubankov
02.04.2017 11:32+7ConcurrentModificationException к многопоточности никакого отношения не имеет
Имеет прямое отношение (появился задолго до пакета concurrent), но этот эксепшн также можно получить и без многопоточности.
Нету смысла создавать свои коллекции, чтобы избегать этого эксепшена. В примере со стримами, вы не должны модифицировать коллекцию с которой работаете. Если вам нужна новая коллекция — вызовите коллект метод и получите новый сет:
или так, со статическим импортом:Set<Integer> filteredSet = set.stream().filter(v -> v % 2 == 0).collect(Collectors.toSet());Set<Integer> filteredSet = set.stream().filter(v -> v % 2 == 0).collect(toSet());
Если вы не хотите создавать новый сет по причине «экономии памяти», тогда стримы с лямбдами вам и вовсе не стоит использовать. В этом случае используйте for-i цикл или все тот же явный итератор.
ConcurrentModificationException — это не та причина, чтобы создавать еще одинвелосипедфреймворк коллекций.
yannmar
02.04.2017 15:18-1Имеет прямое отношение
Нет, всё таки не имеет. Эта штука происходит при наличии итератора и изменениях производимых в том же потоке, о чём подробно написано во введении. Не, наверное, можно извернуться и получить это в многопоточной среде, прямо скажем, очень очень мало кто такое делал.
Нету смысла создавать свои коллекции,
Конечно есть. Как минимум это очень интересно.
В примере со стримами, вы не должны модифицировать коллекцию с которой работаете.
Почему нет-то? А если мне надо? Ну вот есть у меня большая коллекция по ней надо часто итерировать и иногда в процессе итерирования удалять элементы. Лично у меня и правда была такая коллекция. Почему я это не могу сделать? Разработчики на других языках вот могут. Например, JS разработчикам ничто не мешает итерировать по их джаваскриптовым сетам и мапам и одновременно менять их, а у нас тут какой-то анахронизм, мне обидно вот.
Как ешё бывает, в процессе обхода элемент отдаётся какому-то другому методу и уже он решает что делать. Это довольно удобно когда он может принять решение и сам удалить элемент.
ConcurrentModificationException — это не та причина, чтобы создавать еще один велосипед фреймворк коллекций.
Вы так категоричны, но почему нет? Программист не состоялся как программист если не написал свой фреймворк. Видели, сколько фреймворков уже понаписано? Их просто тьма. Ну и как показано в статье, ничто в общем-то не мешает стандартным LinkedHashSet и LinkedHashMap перестать кидаться такими эксепшенами. У них всё для этого уже есть. И это даже обратную совместимость не нарушит.AndreyRubankov
03.04.2017 01:04+1Не, наверное, можно извернуться и получить это в многопоточной среде, прямо скажем, очень очень мало кто такое делал.
Между Java 1.2 (ConcurrentModificationException) и Java 1.5 (появление пакета канкарренси и цикла foreach) прошло ~6 лет. Все это время обычные ArrayList и HashMap использовали в многопоточной среде. Если выполнялись действия без синхронизации, этот эксепшен говорил про то, что в программе есть ошибка.
В целом и сейчас это говорит про ошибку, но не обязательно ошибку синхронизации.
Почему нет-то? А если мне надо?
Потому, что это идеологически не правильно. Стримы — это функциональный подход, который предполагает неизменяемость данных и отсутствие побочных эффектов. forEach — метод, который позволяет сделать произвольные действия (побочные эффекты), но над Элементом коллекции, а не над коллекцией. Если Вы в этом методе изменяете коллекцию — Вы сами стреляете себе в ногу.
Если нужно — посмотрите в комментариях, как это делается правильно.
JS разработчикам ничто не мешает итерировать по их джаваскриптовым сетам и мапам и одновременно менять их, а у нас тут какой-то анахронизм, мне обидно вот
Стоит отметить, что в js нету многопоточности и такой проблемы не может быть в принципе. К слову, в js это тоже плохая практика, JS девелоперы Вам первые скажут, что Вы не должны изменять коллекцию через forEach =)yannmar
03.04.2017 02:14Между Java 1.2 (ConcurrentModificationException) и Java 1.5 (появление пакета канкарренси и цикла foreach) прошло ~6 лет. Все это время обычные ArrayList и HashMap использовали в многопоточной среде. Если выполнялись действия без синхронизации, этот эксепшен говорил про то, что в программе есть ошибка.
Это теория, на практике всё несколько иначе, как мне кажется. Они, конечно, использовались в многопоточной среде. Вот только чтоб получить ConcurrentModificationException нам нужен итератор, а итератор не thread-safe. Он не thread-safe даже если мы обернули нашу коллекцию в synchronized декоратор. А значит использование итератора в многопоточной среде выглядит как-то так:
В целом и сейчас это говорит про ошибку, но не обязательно ошибку синхронизации.
synchronized (sychronizedSet) { Iterator i = sychronizedSet.iterator(); while (i.hasNext()) { process(i.next()); } }
Тут у нас мьютекс, который не даст никакому другому треду поменять коллекцию, и ConcurrentModificationException не случится, чтоб его добиться это надо использовать wait/notify на synchonizedSet да ещё и при наличии итератора. Всё вместе это маловероятно и маловостребованно. В общем, если у вас есть популярный use-case, я с удовольствием на него взгляну. В однопоточной же среде ConcurrentModificationException получается на раз-два.AndreyRubankov
03.04.2017 08:59+1Я об этом и говорю. До появления канкарренси пакета в 2004 в java были только классические коллекции, у которых нету синхронизации. Написать многопоточное приложение на этих коллекциях требовало синхронизации по какому-то объекту, не обязательно по самой коллекции.
И если кто-то не сделал синхронизацию на нужном объекте, то данный эксепшн показывал, что в системе есть ошибка.
Не забывайте, что java коллекциям уже 19 лет. И тот факт, что публичный API нельзя просто взять и изменить.yannmar
03.04.2017 12:39Не, данный эксепшен совсем не об этом, а если доступ к коллекции в многопоточной среде осуществляется не в thead-safe манере, как вы предлагаете, то там может быть вообще черте что помимо ConcurrentModificationException, а ConcurrentModificationException может и вовсе не быть, ни что в этом случае не гарантирует что значение поля modCount в треде осуществляющем небезопасный доступ актуально, а значит не гарантирует и выбрасывание СoncurrentModificationException.
Чтобы понять роль данного эксепшена имеет смысл попробовать самому написать примитивный ArrayList, с парочкой мутаторов (add, remove по индексу) и итератором. Вы почти сразу наступите на туже проблему что и разработчики java collection framework и почувствуете откуда берется ConcurrentModificationException и какова его настоящая роль. Всё вместе это у вас займет минут 10 примерно.
И тот факт, что публичный API нельзя просто взять и изменить.
При предложенных изменениях обратная совместимость не нарушается, подобным образом публичный API менялся и не раз.
yannmar
03.04.2017 02:36Потому, что это идеологически не правильно.
Вы думаете, есть принципиальная разница между forEach циклом и forEach методом на стримах? Я и там и там могу делегировать обработку элемента какому-то методу, который в своих глубинах решит удалить элемент. Там этот метод в глубине стека вызовов понятия не будет иметь ни о наличии стрима ни о наличии forEach цикла. И тем не менее разработчику этого метода наличие итератора выше по стеку придется принимать во внимание, хотя идеологически правильнее, чтобы логика метода могла разрабатываться без учета наличия итераторов в контексте вызова.
Стоит отметить, что в js нету многопоточности и такой проблемы не может быть в принципе. К слову, в js это тоже плохая практика, JS девелоперы Вам первые скажут, что Вы не должны изменять коллекцию через forEach =)
Ещё раз, в java ConcurrentModificationException отлично случается в одном потоке. Только там и случается. Это самый популярный способ его воспроизвести на который многие наступали. На самом деле в джаваскрипте эта проблема вполне могла бы быть, в реализациях map-ов и set-ов без использования связного списка (как это сделано в HashMap и HashSet) при наличии итератора необходимо запрещать изменения вызовами методов коллекции. Просто в javascript грамотно спроектировали свои коллекции, что помешало сделать разработчикам джава платформы тоже самое разрабатывая LinkedHashMap и LinkedHashSet — совершенно не понятно.
sshikov
02.04.2017 13:25+1>Нету смысла создавать свои коллекции, чтобы избегать этого эксепшена.
Не, ну вообще-то автор дальше детально пояснил, чего он на самом деле хочет. Он хочет параллельно итерироваться и модифицировать коллекцию. Вполне законное желание. Другое дело, что без транзакционности в том или оном виде все равно всех проблем предложенный вариант не решает — но это уже боюсь не лечится совсем, и мы это прекрасно видим на базах данных — универсального решения нет, есть много для разных случаев.AndreyRubankov
02.04.2017 14:04+2Так а в чем проблема использовать для этой задачи итераторы?
Да, код с foreach красивее немного, но суть цикла foreach совсем в другом.
foreach – это механизм для работы с элементами коллекции, а не с самой коллекцией. Использование foreach для модификации коллекции – это уже не правильно. А писать костыли и велосипеды, чтобы «расширить возможности» конструкции языка – и вовсе плохая затея. Этот подход сломает возможность заменить реализацию А на реализацию Б без танцев с бубном и переписывания всего кода, где коллекция модифицировалась в foreach.
ps: вот один из классических подходов работы с итераторами:
for (Iterator<Integer> it = set.iterator(); it.hasNext(); ) { if (it.next() % 2 == 0) { it.remove(); } }
elegorod
02.04.2017 15:20+2collection.removeIf(element -> iDontLikeThisElement(element))
— и велосипеды больше не нужныyannmar
02.04.2017 15:41Кстати хороший поинт. Но бывает, что решение об удалении происходит в глубине цепочки вызовов, и т.е. надо тащить обратно этот флаг, ну и вообще те методы могут хотеть возвращать что-то своё.
yannmar
02.04.2017 15:48Set set2 = set.stream().filter(v -> v % 2 == 0).peek(set::remove).collect(Collectors.toSet());
А если вот так?
eugzol2
03.04.2017 03:33А потом хвост? placeholder это голова? А head хвост тогда?
yannmar
03.04.2017 12:22В этой статье приняты следующие обозначения: итерируем от головы к хвосту (placeholder идет сразу после хвоста) переходя от предыдущего (prev) элемента к следующему (next), добавляются элементы в хвост.
На картинке: голова слева, а хвост — справа.
Но сами понимаете, это названия сути не меняют, если вам удобнее итерировать от хвоста к голове, а добавлять элементы в голову, то просто переименуйте так как вам удобно.eugzol2
03.04.2017 17:12Твой placeholder идет сразу после головы, и элементы добавляются в голову т.е. в placeholder вообще-то.
LinkedSet<Integer> ls = new LinkedSet<>(); ls.add(0); ls.add(1); ls.add(2); ls.add(3); ls.add(4); System.out.println(ls.head.prev); null System.out.println(ls.head.next); LinkedSet$LinkedElement@140e19d System.out.println(ls.placeholder.prev); LinkedSet$LinkedElement@17327b6 System.out.println(ls.placeholder.next); nullyannmar
03.04.2017 17:51Эммм не понял в чём проблема. Я исходил из того что голова в начале т.е. слева, а хвост в конце т.е. справа., добавалем в хвост, итерируем с головы. Все имена и обозночения соответсвуют этой идее кажется.
yannmar
03.04.2017 18:11Вот как-то так
eugzol2
03.04.2017 18:42Концептуально это не правильно всё таки. В смысле на картинке одно, а у тебя в коде другое.
У тебя если пройти по голове нет ссылки на предыдущий! А на следующий есть!System.out.println(ls.head.prev); nullyannmar
03.04.2017 18:52Так ведь нет у хеда предыдущего. Только следующий. Потому ls.head.prev is null.
eugzol2
03.04.2017 17:28И итерируешся ты с хвоста в голову. Так?
yannmar
03.04.2017 17:49Ну мне приятно думать, что я итерирую от головы к хвосту. Но это всего лишь названия, так? Если назвать их наоборот, то получтся что итератор бежит от хвоста к голове
eugzol2
03.04.2017 18:57Нравится не нравится спи моя красавица. (?) А ещё «добро это зло правда это ложь» © этож всего лишь слова:)
Если назвать их наоборот, то получтся что итератор бежит от хвоста к голове
Но он так и бежит в реальности!
punksta
<сарказм>
использовать immutable data structures
</сарказм>