2

如果我有一个 STL priority_queue 结构，其中优先级基于结构的某些属性，并且我更改了其中一个结构的属性，这样新的顺序就会不同，优先级队列会知道自己求助吗？还是我必须将其从队列中删除并再次推入？我在某处读到，在调用 push() 和 pop() 时排序已完成，但我想确定一下。

4

3 回答 3

1

priority_queue push()和成员函数是根据和库函数pop()的行为定义的，其中底层容器的全部内容作为范围传入。push_heap()pop_heap()

这些功能要求范围（除了 a 上容器中的最后一项push_heap()，因为这是要添加的项）“应为有效堆”。如果您修改包含的元素以使容器不再是有效堆，那么您将获得未定义的行为。

因此，如果您需要以这种方式修改一个元素，您需要通过删除它、修改它，然后将其添加回来来完成它。或者，您可以将内容弄乱，然后调用make_heap()以重建堆。

请参见 C++11 23.6.4.3“priority_queue 成员”、25.4.6.1“push_heap”和 25.4.6.2“pop_heap”。

于 2013-05-29T06:14:03.497 回答
1

没有办法做你描述的事情。

将项目推送到优先级队列有三种方法：

  1. push()（这意味着移动或复制项目，而不是参考）
  2. 在构造队列时传递另一个容器或迭代器范围（这也涉及制作副本或移动，然后在副本上形成堆；不保留对原件的引用）
  3. emplace()（这意味着在队列中创建一个新项目，但无法获得对它的引用）

访问元素的唯一方法是通过top()函数，它返回一个常量引用。

因此，在推送项目时无法保留对项目的引用，或获取对队列中已存在项目的非 const 引用。因此，无法直接修改队列项。

理论上，进行会影响排序顺序的修改的唯一方法是队列中的项目是否包含指向外部对象的指针，并且排序顺序是否取决于这些外部对象的内容。在这种情况下，您显然可以修改这些外部对象，而队列项目仍然指向它们。然后排序顺序将变得无效——优先级队列不会更新它，因为它甚至不知道修改。

于 2013-05-29T06:04:10.127 回答
0

它肯定不会以正确的方式重新排序，至少不能保证。priority_queue 的 push() 和 pop() 只是调用底层堆结构的 std::push_heap() 和 std::pop_heap() 。

的效果

push(const value_type& x)

是

c.push_back(x);
push_heap(c.begin(), c.end(), comp);

根据 C++03 标准 (23.2.3.2.2)，其中c是队列的底层容器，而comp是排序函数。

push_heap的一项要求是

范围 [first, last - 1] 应为有效堆。

根据 C++03 标准的 25.3.6.1。

如果修改priority_queue 的现有结构，这会破坏堆结构，并且必须使用make_heap 重新制作它才能再次成为有效的堆结构。

priority_queue 也无法知道您是否使用外部引用/指针修改了元素，因为调用其方法之一不会通知它。

您应该删除该元素并再次添加它以实现您想要的。您还可以使用完全不同的容器，在其中您可以更灵活地选择要删除和再次添加的元素，例如 std::map。

于 2013-05-29T06:27:15.857 回答