英文:
std::priority_queue::pop iterators invalidating
问题
使用 priority_queue::pop() 函数会使其他堆元素的迭代器失效吗？例如，我有一个包含元素 {1, 2, 3, 4} 的最小堆，并且有一个指向值为 2 的元素的迭代器 it。在对这个堆应用 pop 后，*it 是否仍然有效？
英文:
Does using priority_queue::pop() function invalidate other heap elements iterators?
For example, I have minheap with elements {1, 2, 3, 4} and iterator it pointing to element with value 2. Will be *it valid after applying pop to this heap?
答案1
得分: 3
短答案是不行的（至少在通常情况下是这样的--请参见下文）。
在优先队列上执行pop等同于：
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
...其中c是对底层容器的引用。
pop_heap本身只是将元素重新排列到底层集合中--交换容器中的第一个和最后一个元素，然后将第一个到倒数第二个元素重新组成一个堆。
默认情况下，底层容器将是std::vector，在这种情况下，pop_back会使任何引用刚刚移除的元素的迭代器无效，并且可能会使超过末尾的迭代器无效。
您可能会合理使用作为priority_queue底层容器的唯一其他标准容器是std::deque，它的工作方式几乎相同--pop_back会使对该元素的迭代器无效，以及超过末尾的迭代器。（注意：我并不是说有很好的理由使用deque而不是vector，只是您可以这样做，而且不一定会有很大的问题）。
如果您非常想要，可以设计一些自己的容器，并在其上实例化一个priority_queue，在这种情况下，priority_queue上的pop仍然会在底层容器上执行pop_back，具有其可能具有的任何影响。虽然我可以很容易地想象到这种情况类似于一个带有互斥锁（或类似）的vector，以允许在线程之间共享，但我认为在一个容器上实例化priority_queue的情况与vector或deque的迭代器无效规则明显不同的容器相对较不常见。
参考
-
[priqueue.members]/6
void pop();Effects: As if by:
pop_heap(c.begin(), c.end(), comp); c.pop_back(); -
[deque.modifiers]/4
Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements.
-
[vector.modifiers]/3
Effects: Invalidates iterators and references at or after the point of the erase.
英文:
The short answer is no (at least in the usual case--see more below).
pop on a priority queue is equivalent to:
pop_heap(c.begin(), c.end(), comp);
c.pop_back();
...where c is a reference to the underlying container.
pop_heap itself only rearranges elements into the underlying collection--swaps the first and last elements in the container, then makes the first through last-1 elements back into a heap.
By default the underlying container will be std::vector, in which case the pop_back invalidates any iterators that refer to the element just removed, and potentially any past-the-end iterators.
The only other standard container you might reasonably use as the underlying container for a priority_queue would be a std::deque, which works pretty much the same way--pop_back will invalidate iterators to that element, and one-past-the-end iterators. (Note: I'm not saying there's a good reason to use a deque instead of a vector, just that you could do it, and it wouldn't necessarily be a huge problem).
If you wanted to badly enough, you could design some container of your own, and instantiate a priority_queue over that, in which case pop on the priority_queue would still do a pop_back on the underlying container, with whatever effects that happened to have. Although I can pretty easily see this being something like a vector plus a mutex (or similar) to allow sharing between threads, I think it would be fairly unusual to instantiate a priority_queue over a container with significantly different iterator invalidation rules than a vector or deque.
References
-
[priqueue.members]/6
>
void pop();<p>
> Effects: As if by:pop_heap(c.begin(), c.end(), comp); c.pop_back(); -
[deque.modifiers]/4
> Effects: An erase operation that erases the last element of a deque invalidates only the past-the-end iterator and all iterators and references to the erased elements.
-
[vector.modifiers]/3
> Effects: Invalidates iterators and references at or after the point of the erase.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论