Java 在 TreeSet 上使用迭代器

Using iterator on a TreeSet

提问by aps

SITUATION:I have a TreeSet of custom Objects and I have also used a custom Comparator. I have created an iterator to use on this TreeSet.

情况：我有一个自定义对象的 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
}

QUESTION:Well I want to know that if I add a new element to the TreeSet within the while loop, then will that new element get sorted immediately. In other words, if I add a new element within the while loop and it is less than the one which I am currently holding in c, then in the next iteration will I be getting the same element in c as in the last iteration?(since after sorting, the newly added element will occupy a place somewhere before the current element).

问题：我想知道，如果我在 while 循环中向 TreeSet 添加一个新元素，那么该新元素是否会立即排序。换句话说，如果我在 while 循环中添加一个新元素并且它小于我当前在 c 中保存的元素，那么在下一次迭代中我会在 c 中获得与上次迭代相同的元素吗？（因为排序后，新添加的元素将占据当前元素之前的某个位置）。

采纳答案by Michael Brewer-Davis

If you add an element during your iteration, your next iterator call will likely throw a ConcurrentModificationException. See the fail-fast behavior in TreeSetdocs.

如果您在迭代期间添加一个元素，您的下一次迭代器调用可能会抛出一个ConcurrentModificationException. 请参阅TreeSet文档中的快速失败行为。

To iterate and add elements, you could copy first to another set:

要迭代和添加元素，您可以先复制到另一个集合：

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

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

// continue, using tsWithExtra

or create a separate collection to be merged with tsafter iteration, as Colin suggests.

或者创建一个单独的集合，以便ts在迭代后合并，正如 Colin 所建议的那样。

回答by anubhava

You will get a java.util.ConcurrentModificationExceptionif you add an element into the TreeSet inside while loop.

如果您在 while 循环内的 TreeSet 中添加一个元素，您将获得java.util.ConcurrentModificationException。

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");
}

Output

输出

Exception in thread "main" java.util.ConcurrentModificationException

回答by NILESH SALPE

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

This will come to all collections like List, Map, SetBecause when iterator starts it may be putting some lock on it .

这将适用于所有集合，例如List, Map，Set因为当迭代器启动时，它可能会对其加锁。

if you iterate list using iterator then this exception will come. I think otherwise this loop will be infinite as you are adding element whole iterating.

如果您使用迭代器迭代列表，则会出现此异常。我认为否则这个循环将是无限的，因为您正在添加元素整个迭代。

Consider without iterator:

考虑没有迭代器：

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());
}

this will be fine .

这样就好了。

回答by kriegaex

In order to avoid the ConcurrentModificationExceptionyou might want to check out my UpdateableTreeSet. I have even added a new test caseshowing how to add elements during a loop. To be more exact, you mark new elements for a later, deferred update of the set. This works quite nicely. Basically you do something like

为了避免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();

I guess this is quite exactly what you need. :-)

我想这正是你所需要的。 :-)

回答by Houcheng

To prevent the ConcurrentModificationException while walking. Below is my version to allow high frequency insertion into the TreeSet() and allow concurrently iterate on it. This class use a extra queue to store the inserting object when the TreeSet is being iterating.

防止行走时出现 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;
}
}

回答by KNU

While the question has already been answered, I think the most satisfactory answer lies in javadoc of TreeSetitself

虽然问题已经回答了，但我认为最满意的答案在于TreeSet本身的javadoc

The iterators returned by this class's iterator method are fail-fast: if the set is modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, >generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

此类的迭代器方法返回的迭代器是快速失败的：如果在迭代器创建后的任何时间修改集合，除了通过迭代器自己的 remove 方法以外的任何方式，迭代器都会抛出 ConcurrentModificationException。因此，面对并发修改，迭代器快速而干净地失败，而不是冒着在未来不确定的时间出现任意、非确定性行为的风险。

请注意，无法保证迭代器的快速失败行为，> 一般来说，在存在非同步并发修改的情况下不可能做出任何硬保证。快速失败的迭代器会尽最大努力抛出 ConcurrentModificationException。因此，编写一个依赖此异常来确保其正确性的程序是错误的：迭代器的快速失败行为应该仅用于检测错误。

回答by ragerdl

To avoid the concurrent modification error that's bound to occur when you're doing the insertion, you could also create a temporary copy of the Set, iterate through the copy instead, and modify the original.

为了避免在进行插入时必然发生的并发修改错误，您还可以创建 Set 的临时副本，改为遍历副本，然后修改原始副本。