优先队列改变它的内容

Question

我一直在尝试创建一个优先级队列，其中每个元素都是一个对，存储一个指针到一个无符号整数 和一个 无符号整数 。问题是，每当我将一对添加到优先级队列时，先前添加的一对指向的元素会将其值切换为 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;
}

及其执行结果

为什么会这样？

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

Answer 1

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

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

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

Answer 2

你在操作中添加的指针如

distance.push_back(2500);
Q.push(Ppuiui(&(distance[0]), 0));

当您向向量中添加更多保留向量时，它们会悬空。这是因为向量将旧值复制到更新、更大的数组中。

如果你想使用这样的地址，你应该使用 distance.reserve 以确保预先存在足够的 space。

优先队列改变它的内容

Priority queue changes its content

c++

pointers

priority-queue

std-pair