Использование итератора в TreeSet

Question

СИТУАЦИЯ: У меня есть TreeSet пользовательских объектов, и я также использовал собственный компаратор. Я создал итератор для использования в этом TreeSet.

TreeSet<Custom> ts=new TreeSet<Custom>();
Iterator<Custom> itr=ts.iterator();
while(itr.hasNext()){
    Custom c=itr.next();
    //Code to add a new element to the TreeSet ts
}

ВОПРОС: Хорошо, я хочу знать, что если я добавлю новый элемент в TreeSet в цикле while, то этот новый элемент будет отсортирован немедленно. Другими словами, если я добавлю новый элемент в цикл while, и он будет меньше, чем тот, который я сейчас держу в c, то на следующей итерации я получу тот же элемент в c, что и на последней итерации? ( поскольку после сортировки вновь добавленный элемент будет занимать место где-то перед текущим элементом).

Answer 1

Если вы добавите элемент во время итерации, ваш следующий вызов итератора, скорее всего, выдаст ConcurrentModificationException. См. Отказоустойчивое поведение в TreeSet документах.

Для итерации и добавления элементов вы можете сначала скопировать в другой набор:

TreeSet<Custom> ts = ...
TreeSet<Custom> tsWithExtra = new TreeSet(ts);

for (Custom c : ts) {
  // possibly add to tsWithExtra
}

// continue, using tsWithExtra

или создайте отдельную коллекцию для объединения с ts после итерации, как предлагает Колин.

Answer 2

Вы получите java.util.ConcurrentModificationException , если добавите элемент в TreeSet внутри цикла while.

Set<String> ts=new TreeSet<String>();
ts.addAll(Arrays.asList(new String[]{"abb", "abd", "abg"}));
Iterator<String> itr=ts.iterator();
while(itr.hasNext()){
    String s = itr.next();
    System.out.println("s: " + s);
    if (s.equals("abd"))
        ts.add("abc");
}

выход

Exception in thread "main" java.util.ConcurrentModificationException

Answer 3

public static void main(String[] args) {
    TreeSet<Integer> ts=new TreeSet<Integer>();
    ts.add(2);
    ts.add(4);
    ts.add(0);

    Iterator<Integer> itr=ts.iterator();
    while(itr.hasNext()){
        Integer c=itr.next();
        System.out.println(c);
        //Code
        ts.add(1);
    }
}


Exception in thread "main" java.util.ConcurrentModificationException

Это относится ко всем коллекциям, таким как List, Map, Set Поскольку при запуске итератора он может быть заблокирован.

если вы итерируете список с помощью итератора, тогдаэто исключение придет.Я думаю, что в противном случае этот цикл будет бесконечным, так как вы добавляете элемент итерации.

Рассмотрим без итератора:

public static void main(String[] args) {
    List<Integer> list=new ArrayList<Integer>();
    list.add(2);
    list.add(4);
    list.add(0);

    for (int i = 0; i < 3; i++) {
        System.out.println(list.get(i));
        list.add(3);
    }
    System.out.println("Size" +list.size());
}

все будет хорошо.

Answer 4

Во избежание ConcurrentModificationException вы можете проверить мои UpdateableTreeSet. Я даже добавил новый контрольный пример , показывающий, как добавлять элементы во время цикла. Точнее, вы помечаете новые элементы для более позднего, отложенного обновления набора. Это работает довольно хорошо. В основном вы делаете что-то вроде

for (MyComparableElement element : myUpdateableTreeSet) {
    if (someCondition) {
        // Add new element (deferred)
        myUpdateableTreeSet.markForUpdate(
            new MyComparableElement("foo", "bar", 1, 2)
        );
    }
}

// Perform bulk update
myUpdateableTreeSet.updateMarked();

Полагаю, это именно то, что вам нужно. :-)

Answer 5

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

Answer 6

Хотя на этот вопрос уже дан ответ, я думаю, что наиболее удовлетворительный ответ лежит в javadoc самого TreeSet *

Итераторы, возвращаемые методом итератора этого класса, работают быстро.: если набор изменяется в любое время после создания итератора, любым способом, кроме как через собственный метод удаления итератора, итератор сгенерирует исключение ConcurrentModificationException.Таким образом, перед лицом одновременной модификации, итератор быстро и чисто дает сбой, вместо того, чтобы рисковать произвольным недетерминированным поведением в неопределенное время в будущем.

Обратите внимание, что быстрое поведение итератора не можетбыть гарантированным, поскольку,> вообще говоря, невозможно сделать какие-либо жесткие гарантии при наличии несинхронизированной параллельной модификации.Отказоустойчивые итераторы создают исключительную ситуацию ConcurrentModificationException.Следовательно, было бы неправильно писать программу, которая зависела от этого исключения в отношении его корректности: поведение итераторов при быстром отказе следует использовать только для обнаружения ошибок.

Answer 7

Для предотвращения исключения ConcurrentModificationException при ходьбе. Ниже моя версия, чтобы разрешить высокочастотную вставку в TreeSet () и одновременно выполнять итерации. Этот класс использует дополнительную очередь для хранения вставляемого объекта во время итерации TreeSet.

public class UpdatableTransactionSet {
TreeSet <DepKey> transactions = new TreeSet <DepKey> ();
LinkedList <DepKey> queue = new LinkedList <DepKey> ();
boolean busy=false;
/**
 * directly call it
 * @param e
 */
void add(DepKey e) {
    boolean bb = getLock();
    if(bb) {
        transactions.add(e);
        freeLock();
    } else {
        synchronized(queue) {
            queue.add(e);
        }
    }
}
/**
 * must getLock() and freeLock() while call this getIterator function
 * @return
 */
Iterator<DepKey> getIterator() {
    return null;
}

synchronized boolean getLock() {
    if(busy) return false;
    busy = true;
    return true;
}
synchronized void freeLock() {
    synchronized(queue) {
        for(DepKey e:queue) {
            transactions.add(e);
        }
    }       
    busy = false;
}
}