std::priority_queue::pop是否会使其他堆元素迭代器失效？

核心结论 #

只要迭代器未指向被pop()移除的堆顶元素，该迭代器在操作后仍然有效，指向的元素值也不会改变。

底层逻辑解释 #

std::priority_queue 默认依赖 std::vector 作为底层存储（也可指定 std::deque），它的pop()操作流程是：

1. 交换堆顶元素（容器首元素）与容器末尾元素
2. 调用底层容器的pop_back()移除原堆顶元素
3. 对剩余元素执行堆调整（下滤），重构堆结构

对于标准底层容器（vector/deque）来说，pop_back()只会使指向被移除元素的迭代器失效，其他元素的迭代器不受影响。堆调整过程仅改变元素的位置，但不会触发容器的内存重分配或元素销毁，因此原有指向非堆顶元素的迭代器依然能正确指向对应的元素。

对应你的示例 #

小顶堆初始包含{1,2,3,4}，迭代器it指向值为2的元素：

• pop()会移除堆顶的1，剩余元素（2、3、4）会被重新调整为合法的小顶堆，但2这个元素并未被销毁或移除。
• 因此it仍然有效，*it的值还是2。

例外情况 #

• 若迭代器原本指向堆顶元素，pop()后该迭代器会失效，因为对应的元素已被移除。
• 若使用了非标准的自定义底层容器，且其pop_back()会导致其他迭代器失效，那迭代器有效性需参照该容器的规则（这种情况非常罕见）。

内容的提问来源于stack exchange，提问作者wowonline