1

我有下面的代码试图转储存储在 C++ 中的 priority_queue 中的值：

priority_queue<Point, vector<Point>, myCmp> pq;
int i;
for (i = 0; i < 10; i++) {
    Point p(i,i);
    pq.push(p);
}
const Point& p0 = pq.top();
while(!pq.empty()) {
    cout<<p0.x<<p0.y<<endl;
    pq.pop();
}//I'm getting output like "00 11 22 33 ... 99"

正如代码中的注释所说，每次队列弹出一个值时，我的引用变量 p0 都会不断变化。这对我来说没有意义，因为我认为 p0 应该始终是对 (0,0) 对象的引用，即开始时队列的前面。我知道我可以使用

Point p0 = pq.top()

获取前端元素的副本并避免该问题。但是，有人可以解释使用引用的问题吗？

PS 我对 C++ 队列做了同样的事情，但没有观察到这个问题。

4

2 回答 2

1

在您更改priority_queue（例如通过弹出）后，所有引用都会被删除。所以这是未定义的（？）行为

怎么了：

您将获得对顶部元素的引用。它存储为底层的第一个元素std::vector，因此您只需链接到vector. 当popping您vector使用已删除的前一个顶部元素重新排列到新状态时。新的顶部元素应该在vector. 所以，如果vector在同一个地方引用指向新的顶部

添加：

一些参考资料：

make_pop: § 23.6.4.3/4

无效弹出（）；
4 效果：
pop_heap(c.begin(), c.end(), comp);
c.pop_back();

§ 25.4.6.2/2

效果：将位置 first 中的值与位置 last - 1 中的值交换，并使
[first,last - 1) 成为堆。

我没有找到与pop_backforvector完全相同的信息erase(end() - 1)（仅适用于字符串），但这似乎是真的。

§ 23.3.6.5/3

迭代器擦除（const_iterator 位置）；
迭代器擦除（首先是 const_iterator，最后是 const_iterator）；效果：在擦除点或擦除点之后使
迭代器和引用无效

因此，依赖该引用将指向新的顶部似乎是有效的，pop因为即使重新分配似乎也是不可能的。但是无论如何使用它都不是一个好主意。

*所有参考 N3242

于 2013-07-26T20:14:51.100 回答
1

实际上，我将在评论中给出更深入的答案。

所以当你得到一个引用时，你实际上只是得到了一个指向前面元素的指针。std::vector 是底层容器，因此您拥有的代码（在功能上）与您拥有的代码更相似：

vector<Point> pq;
int i;
for (i = 0; i < 10; i++) {
    Point p(i,i);
    pq.push_back(p);
}
Point* p = &pq[0];

while(!pq.empty()) 
{
    cout<<p->x<<p->y<<endl;
    pq.erase(pq.begin(),pq.begin()+1);
}//I'm getting output like "00 11 22 33 ... 99"

现在，在您开始弄乱这些值之后，无法保证 p* 指向向量的第一个成员。确实，如果我添加一个 pq.resize(100); 在 p 分配之后，虽然 pq[0] 仍然等于 (0,0)，但 p 指向外部随机未保留内存（读取输出垃圾或出现 seg-fault）。由于纯粹的机会，您现在正在获得正确的价值！这就是为什么你总是需要在弹出之前复制或移动。

于 2013-07-26T20:27:14.947 回答