优先队列改变其内容 [英] Priority queue changes its content

问题描述

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

这是代码

#include #include <向量>#include <实用程序>#include <队列>typedef unsigned int ui;typedef std::pair皮尤伊;typedef std::priority_queue队列;void showPQ(队列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距离;队列Q；//将元素添加到优先级队列，同时显示它们距离.push_back(2500);Q.push(Ppuiui(&(distance[0]), 0));显示PQ(Q);距离.push_back(1000);Q.push(Ppuiui(&(distance[1]), 1));显示PQ(Q);距离.push_back(500);Q.push(Ppuiui(&(distance[2]), 2));显示PQ(Q);//检查距离"中的任何值都没有改变std::cout <<距离[0]＜＜std::endl;std::cout <<距离[1]＜＜std::endl;std::cout <<距离[2]＜＜std::endl;}

及其执行结果

2500 ->01000 ->10 ->00 ->1500 ->20 ->025001000500

为什么会这样?

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

解决方案

您违反了迭代器验证规则.您获取一个指向向量元素的指针，然后将另一个元素添加到向量中.如果重新分配，添加元素将导致所有迭代器、指针和引用无效.

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

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

I have been trying to create a priority queue in which every element is a pair that stores a pointer to an unsigned int and an unsigned int. The problem is that whenever I add a pair to the priority queue, the element that the previously added pair was pointing to, switches its value to 0.

Here is the code

#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;
}

and the result of its execution

2500 -> 0

1000 -> 1
0 -> 0

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

2500
1000
500

Why does this happen?

Note: I am well aware that the priority queue in this code compares the memory addresses instead of the value which they cointain.

解决方案

You are violating the iterator validation rules. You take a pointer to a vector element and then after you do that you add another element to the vector. Adding an element will cause all iterators, pointers and references to become invalid if there is a reallocation.

Since you never reserved a size for the vector at least the first two push_backs will cause a reallocation which means you have a dangling pointer. If you really need to store pointers to elements in the vector then you are going to have to reserve the space in the vector so a reallocation does not happen.

For more on when and what is affected by operations on containers see: Iterator invalidation rules

这篇关于优先队列改变其内容的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！