Изменение набора во время итерации java

Я бы использовал две структуры данных --- очередь (например, ArrayDeque) для хранения объектов, подобъекты которых нужно посетить, и набор (например, HashSet) для хранения всех посещенных объектов без дублирования.

Set visited = new HashSet();   // all visited objects
Queue next = new ArrayDeque(); // objects whose subobjects are to be visited

// NOTE: At all times, the objects in "next" are contained in "visited"

// add the first object
visited.add(obj);

Object nextObject = obj;

while (nextObject != null)
{
    // do stuff to nextObject

    for (Object o : nextObject.subobjects)
    {
        boolean fresh = visited.add(o);

        if (fresh)
        {
            next.add(o);
        }
    }

    nextObject = next.poll(); // removes the next object to visit, null if empty
}

// Now, "visited" contains all the visited objects

ПРИМЕЧАНИЯ:

• ArrayDeque — это очередь с эффективным использованием пространства. Он реализован как циклический массив, что означает, что вы используете меньше места, чем List, который продолжает расти при добавлении элементов.
• «boolean fresh = visited.add(o)» объединяет «boolean fresh = !visited.contains(o)» и «if (fresh) visited.add(o)».

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

Конечно, List.contains() — медленная операция по сравнению с Set.contains(), поэтому, возможно, стоит придумать гибрид, если важна скорость:

while(list.size() > 0)
{
   //doStuff

   for each subObject
   {
      if (!set.contains(subObject))
      {
         list.add(subObject);
         set.add(subObject)
      }
   }
}

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

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

    HashSet nextObjects = new HashSet();
    HashSet currentObjects = new HashSet(firstObject.subObjects);

    while(currentObjects.size() > 0)
    {
        Iterator iter = currentObjects.iterator();
        while(iter.hasNext())
        {
            //doStuff
            nextObjects.add(subobjects);
        }
        currentObjects = nextObjects;
        nextObjects = new HashSet();
    }

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

Используйте более одного набора и делайте это в «раундах»:

/* very pseudo-code */
doFunction(Object o) {
    Set processed = new HashSet();
    Set toProcess = new HashSet();
    Set processNext = new HashSet();

    toProcess.add(o);

    while (toProcess.size() > 0) {
        for(it = toProcess.iterator(); it.hasNext();) {
            Object o = it.next();
            doStuff(o);
            processNext.addAll(o.subObjects);
        }
        processed.addAll(toProcess);
        toProcess = processNext;
        toProcess.removeAll(processed);
        processNext = new HashSet();
    }
}

Почему бы не создать дополнительный набор, содержащий весь набор объектов? Вы можете использовать это для поиска.