优先级队列更改其内容

Question

我一直在尝试创建一个优先级队列,其中每个元素都是一对存储指向unsigned int和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

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

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

有关容器上操作的时间和内容的更多信息,请参阅:迭代器失效规则