Priority queue changes its content

问题:

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.

回答1:

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

回答2:

The pointers you add in operations such as

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

are left dangling when you add more to the vector that the vector has in reserve. This is because the vector copies the old values into a newer, larger array.

If you want to use addresses like this, you should use distance.reserve to ensure enough space exists before hand.