c++ - 优先队列改变它的内容

Question

我一直在尝试创建一个优先级队列，其中每个元素都是一个对，它存储一个指向一个unsigned int的指针和一个无符号整数。问题是，每当我将一对添加到优先级队列时，先前添加的一对指向的元素会将其值切换为 0。

这是代码

#include <iostream>
#include <vector>
#include <utility>
#include <queue>

typedef unsigned int ui;
typedef std::pair<ui*, ui> Ppuiui;
typedef std::priority_queue<Ppuiui> Queue;

void showPQ(Queue Q)
{
    while(!Q.empty())
    {
        std::cout << *(Q.top().first) << " -> " << Q.top().second << std::endl;
        Q.pop();
    }
    std::cout << std::endl;
}

int main(void)
{
    std::vector<ui> distance;
    Queue Q;

    //Adding elements to the priority queue while showing them
    distance.push_back(2500);
    Q.push(Ppuiui(&(distance[0]), 0));
    showPQ(Q);

    distance.push_back(1000);
    Q.push(Ppuiui(&(distance[1]), 1));
    showPQ(Q);

    distance.push_back(500);
    Q.push(Ppuiui(&(distance[2]), 2));
    showPQ(Q);

    //Checking that none of the values has changed in 'distance'
    std::cout << distance[0] << std::endl;
    std::cout << distance[1] << std::endl;
    std::cout << distance[2] << std::endl;
}

及其执行结果

2500 -> 0

1000 -> 1
0 -> 0

0 -> 1
500 -> 2
0 -> 0

2500
1000
500

为什么会这样？

注意:我很清楚这段代码中的优先级队列比较内存地址而不是它们所包含的值。

Answer 1

您违反了迭代器验证规则。您获取指向 vector 元素的指针，然后在执行此操作后将另一个元素添加到 vector 。如果重新分配，添加元素将导致所有迭代器、指针和引用变为无效。

由于您从未为 vector 保留大小，至少前两个 push_back 将导致重新分配，这意味着您有一个悬空指针。如果您确实需要在 vector 中存储指向元素的指针，那么您将不得不在 vector 中保留空间，这样就不会发生重新分配。

有关容器操作影响的时间和内容的更多信息，请参阅:Iterator invalidation rules