15

std::priority_queue::top返回一个常数值。但是，我想从优先级队列中删除顶部元素，并能够在其他地方对其进行修改。

priority_queue<SomeClass, vector<SomeClass>, SomeClassCompare > pQueue;
...
SomeClass *toBeModified = &(pQueue.top());
pQueue.pop();
toBeModified->setMember(3); // I would like to do this

有没有办法可以从优先级队列中获取顶部元素（并从队列中删除）并根据需要修改它？

4

2 回答 2

17

标准容器和容器适配器具有值语义。当您将元素推入队列时，会创建一个副本。当您从队列中删除一个对象时，该对象将被销毁。

即使top()会返回对 non- 的引用const，当您从队列中删除元素时，该引用也会变得悬空，并且取消引用它会导致未定义的行为。

这就是说，为您std::priority_queue返回一个引用，以防止您（有意或无意地）弄乱其内部排序 - 这与关联容器的键（例如and is ）const的原因几乎相同。std::mapstd::setconst

相反，您可以做的是构造由返回的值的副本top()，修改该副本，删除原始副本，然后将副本推送到队列中：

SomeClass obj = pQueue.top();
pQueue.pop();
obj.setMember(42);
pQueue.push(std::move(obj)); // You can move obj into the queue if you no more need it

另一方面，如果您需要引用语义，则必须将指针推入队列（可能是智能指针，具体取决于您的用例）并提供适当的自定义排序标准，该标准将根据对象的属性对这些指针进行排序他们指向。

在这种情况下，请注意不要在运行时修改这些属性以使其排序不同。这将被视为“弄乱了容器的内部排序”，并将导致未定义的行为。

于 2013-05-25T23:20:57.997 回答
1

我不认为价值语义在这里起任何作用。所有其他容器具有相同的值语义，并且几乎所有容器都提供front()可变引用。

priority_queue不允许修改元素有一个确切的原因top()：这是因为特定元素位于顶部，因为根据其当前值，它已被相应地限定。优先级队列中的元素始终根据为队列配置的比较标准进行排序（默认为运算符 <）。通过更改元素，您可能会破坏此条件并导致所有使用排序前提条件的操作都会导致未定义的行为。

简而言之，priority_queue不允许修改包含的元素的原因与 for 的setand 键的情况完全相同map。

我知道您可能有一些专用的比较方法，您使用包含要比较的值的字段，并且您将修改对象的任何内容，除了这个字段。这样您就不会违反排序顺序的要求。你可以做两件事：

  1. 将应修改的班级部分设为mutable. 通过这种方式，您可以获取元素top()并修改可变内容，即使这是 const。

  2. 通过派生来创建您自己的优先级队列类std::priority_queue。它有一个名为c（虽然在受保护部分中）的字段，其中包含对底层容器的引用 - 而底层容器总是有一个方法可以访问与in 中front()相同的元素。但是，为了您自己的安全，您应该设置关键字段，以便在构建过程中设置并且永远不会更改 - 只是为了将风险降至最低。top()priority_queueconst

啊，这个问题也不能通过使用指针来解决——指向的对象将是完全相同的常量。这些“引用语义”也对你没有任何帮助，因为如果你想要一个专门的比较方法，它必须查看对象的内容，这样你就会遇到完全相同的问题。如果您仅依靠比较指针值，这将对您有所帮助，但我宁愿怀疑这可能是 99% 情况的解决方案。

于 2015-10-01T10:28:22.827 回答