迭代 PriorityQueue 时如何进行更新

Question

我需要根据ID更新PriorityQueue中的一些固定优先级元素。我认为这是一个很常见的场景，下面是一个示例片段（Android 2.2）：

for (Entry e : mEntries) {
    if (e.getId().equals(someId)) {
        e.setData(newData);
    }
}

我随后使条目 "immutable"（没有设置器方法），以便通过 setData() 创建并返回新的 Entry 实例。我将我的方法修改为以下内容：

for (Entry e : mEntries) {
    if (e.getId().equals(someId)) {
        Entry newEntry = e.setData(newData);
        mEntries.remove(e);
        mEntries.add(newEntry);
     }
}

代码似乎运行良好，但有人指出在迭代队列时修改它是一个坏主意：这可能会抛出ConcurrentModificationException异常，我需要将要删除的元素添加到ArrayList中并稍后删除它。他没有解释原因，而且对我来说看起来是很大的开销，但我在互联网上找不到任何具体的解释。

（此帖类似，但优先级可以改变，这不是我的情况）

有人能澄清一下我的代码有什么问题，我应该如何更改，最重要的是为什么？

谢谢， Rippel

---

PS：一些实现细节...

PriorityQueue<Entry> mEntries = new PriorityQueue<Entry>(1, Entry.EntryComparator());

使用：

public static class EntryComparator implements Comparator<Entry> {
    public int compare(Entry my, Entry their) {
        if (my.mPriority < their.mPriority) {
            return 1;
        }
        else if (my.mPriority > their.mPriority) {
            return -1;
        }
        return 0;
    }
}

- rippeltippel

---

创建一个栈，然后在完成后将要添加的元素放入其中。 - Matt

Answer 1

以下是Java 6实现的PriorityQueue代码：

private class Itr implements Iterator<E> {
  /**
   * The modCount value that the iterator believes that the backing
   * Queue should have.  If this expectation is violated, the iterator
   * has detected concurrent modification.
   */
  private int expectedModCount = modCount;

  public E next() {
    if(expectedModCount != modCount) {
      throw new ConcurrentModificationException();
    }


  }

}

现在，为什么会有这段代码呢？如果你查看ConcurrentModificationException的Javadoc，你会发现如果在迭代完成之前对基础集合进行修改，则迭代器的行为是未定义的。因此，许多集合实现了这种modCount机制。 修复代码 您需要确保不会在循环过程中修改代码。如果您的代码是单线程的（正如它看起来一样），那么您可以像同事建议的那样将其复制到列表中以备后用。此外，文档中使用Iterator.remove()方法可防止ConcurrentModificationExceptions。例如：

List<Entry> toAdd = new ArrayList<Entry>();
Iterator it = mEntries.iterator();
while(it.hasNext()) {
  Entry e = it.next();

  if(e.getId().equals(someId)) {
    Entry newEntry = e.setData(newData);
    it.remove();
    toAdd.add(newEntry);
  }
}
mEntries.addAll(toAdd);

- user545680

---

很好的解释和解决方案 :) - berlindev

Answer 2

稍微更好的实现方式是

List<Entry> toAdd = new ArrayList<Entry>();
for (Iterator<Entry> it= mEntries.iterator();it.hasNext();) {
    Entry e = it.next();
    if (e.getId().equals(someId)) {
        Entry newEntry = e.setData(newData);
        it.remove();
        toAdd.add(newEntry);
     }
}
mEntries.addAll(toAdd);

这个使用迭代器的删除，然后进行批量添加

- ratchet freak

Answer 3

PriorityQueue的Javadoc明确指出：

“请注意，此实现未同步。如果任何线程结构性地修改列表，则不应同时访问PriorityQueue实例的多个线程。相反，请使用线程安全的PriorityBlockingQueue类。”

这似乎是您的情况。

- G B

Answer 4

你代码中的问题已经被解释了——实现迭代器，能够一致地遍历具有交叉修改的集合是一项相当困难的任务。你需要指定如何处理已删除的项目（是否会通过迭代器看到？），添加的项目，修改的项目...即使你可以一致地完成它，它也将是相当复杂和低效的实现——而且，大多数情况下并不是很有用，因为“在没有修改的情况下进行迭代”的用例更为常见。因此，Java 架构师选择在迭代时拒绝修改，Java 集合 API 中的大多数集合都遵循这一点，并在检测到此类修改时抛出 ConcurrentModificationException 异常。

至于你的代码——对我来说，你不应该使项目不可变。不可变性是一件好事，但不应过度使用。如果你在这里使用的 Entry 对象是某种域对象，并且你真的希望它们是不可变的——你可以创建某种临时数据持有者（MutableEntry）对象，在算法内部使用它，并在返回之前将数据复制到 Entry 中。从我的角度来看，这将是最好的解决方案。

- BegemoT