在迭代java期间修改集合

StackOverflow https://stackoverflow.com/questions/497025

  •  20-08-2019
  •  | 
  •  

题

我正在寻求迭代递归方法。

我有一个要迭代的对象列表，然后检查它们的子对象。

递归：

doFunction(Object)
while(iterator.hasNext())
{
   //doStuff
   doFunction(Object.subObjects);
}

我想把它改成这样

doFunction(Object)
iIterator = hashSet.iterator();
while(Iterator.hasNext()
{
   //doStuff
   hashSet.addAll(Object.subObjects);
}

对于糟糕的伪代码感到抱歉，但基本上我想迭代子对象，同时将新对象附加到列表末尾进行检查。

我可以使用列表来做到这一点，然后做类似的事情

while(list.size() > 0)
{
   //doStuff
   list.addAll(Object.subObjects);
}

但我真的不想添加重复的子对象。当然，我可以在添加之前检查 list.contains(each subObject) 是否存在。

但我很想用一套来完成清洁工作。

那么基本上是否有在迭代集合时附加到集合的方法，或者是否有更简单的方法使列表像集合一样而不是手动检查 .contains() ？

如有任何意见，我们将不胜感激。

谢谢

有帮助吗？

解决方案

我会使用两种数据结构 --- 队列 （例如。 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)".

其他提示

我觉得你的问题是固有的，需要通过列表来解决的问题。如果你想想看，你的解决方案集版本是刚刚转换项目到一个列表，然后在该操作。

当然，List.contains（）是相比于Set.contains（）缓慢操作，所以它可能是值得想出的混合动力车如果速度是一个问题：

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

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

此解决方案是快速和概念上也声音 - 设置可以被认为是见识了项目的列表，而列表是项目工作的队列。它需要更多的存储比使用单独列出，但

如果你不使用一个List，迭代器都将只要您修改后定从中读取抛出异常。我会建议使用列表和执行插入限制，然后使用的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();
    }
}

为什么不创建包含整个组对象的一组附加？你可以利用它来进行查找。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top