Value that pointer points at goes out of scope and pointer breaks

Question

The code goes like this. It's a BFS, and I want it to go backwards, so I try to have a connection between steps using a pointer.

sx, sy are our starting points. tx, ty are our destiny points. act[][] is a Boolean table to ensure that I won't go into the same place twice.

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout<<"\n";
    cout<< "x" << " " << a.first << "\n";
    cout<< "y" << " " << a.second << "\n";
    cout<< "x lasta" << " " << a.last->first << "\n";
    cout<< "y lasta" << " " << a.last->second << "\n";
}

queue<trip> Q;
trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
while(!Q.empty())
{
    //cout << "WOW" << "\n";
    trip temp = Q.front(); Q.pop();
    if(temp.last != nullptr)
        write(temp);

    int corx = temp.first;  int cory = temp.second;

    if(corx == tx && cory == ty)
    {
        // We found our destiny
    }

    if(act[corx][cory] == false)
    {
        act[corx][cory] = true;

        // Up
        if(cory - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
            cout << corx - 1 << " " << TEMPUUS.last -> first; // corx - 1 here is equal to
            //TEMPUUS.last -> first - 1 and that is what I want
        }

        // Down
        if(cory + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx + 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // Left
        if(corx - 1 >= 0)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory - 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }

        // Right
        if(corx + 1 <= 2000)
        {
            trip TEMPUUS; TEMPUUS.first = corx; TEMPUUS.second = cory + 1; TEMPUUS.last = &temp; Q.push(TEMPUUS);
        }
    }
}

So what's the problem? The problem is that when I push a trip variable to the queue its coordinates are different from its predecessor's. However, as we go into the next iteration of the queue, the temp variable goes out of scope and the "last" pointer now points at itself.

There is a code sample:

#include <iostream>
#include <fstream>
#include <queue>
using namespace std;

struct trip
{
    int first;
    int second;
    trip* last;
};

void write(trip a)
{
    cout << "\n";
    cout <<  "x" << " " << a.first << "\n";
    cout <<  "y" << " " << a.second << "\n";
    cout <<  "x lasta" << " " << a.last->first << "\n";
    cout <<  "y lasta" << " " << a.last->second << "\n";
}

void bfs(int sx, int sy, int tx, int ty)
{
    queue<trip> Q;
    trip P; P.first = sx; P.second = sy; P.last = nullptr; Q.push(P);
    int test = 0;
    while(!Q.empty())
    {
        trip temp = Q.front(); Q.pop();
        if(temp.last != nullptr)
            write(temp);
        int corx = temp.first;
        int cory = temp.second;

        if(act[corx][cory] == false)
        {
            act[corx][cory] = true;

            // Up
            if(cory - 1 >= 0)
            {
                trip TEMPUUS; TEMPUUS.first = corx - 1; TEMPUUS.second = cory; TEMPUUS.last = &temp; Q.push(TEMPUUS);
                cout << corx - 1 << " " << TEMPUUS.last -> first;
            }
        }
        test++;
        if(test > 5)
            return;
    }
}

int main()
{
    int sx, sy, tx, ty;
    cin >> sx >> sy >> tx >> ty;
    sx += 1000; sy += 1000; tx += 1000; ty += 1000;
    bfs(sx, sy, tx, ty);
    return 0;
}

Answer 1

The temp structure is allocated on the stack and when the block in which it was defined is exited, that memory is freed again. This means that the queued trip has now an invalid last reference.

That same memory gets reused in the next iteration of the loop, making the above mentioned last reference valid again. But now the assignment to temp.first affects that memory. In short, all non-null last members reference the same memory location.

To solve this, work with heap allocated memory (using new, class, ...etc).

You should also take care of freeing the used memory. As in your case the links with last form a tree, this can be quite a burden. I would suggest leaving the memory management to shared smart pointers.

Not your question, but:

• There is an obvious error in your code. While the comment and if condition indicate an "up" movement, you make a Trip with a decreased x-coordinate instead of decreased y-coordinate.
• Why using namespace std; is considered bad practice
• Don't put multiple statements on the same line; certainly not when it needs scrolling to the right (one of your multi-statement lines is more than 110 characters long). Luckily using constructors removes the "need" for some of those.

Here is the replacement for struct trip and the write function:

class Trip
{
public:
    int first;
    int second;
    std::shared_ptr<Trip> last;

    Trip(int first, int second, std::shared_ptr<Trip> last) : 
            first(first), second(second), last(last)
    {
    }

    void write()
    {
        std::cout<<"\n";
        std::cout<< "x" << " " << this->first << "\n";
        std::cout<< "y" << " " << this->second << "\n";
        if (this->last) {
            std::cout<< "x lasta" << " " << this->last->first << "\n";
            std::cout<< "y lasta" << " " << this->last->second << "\n";
        }
    }
};

Now your bfs function can look like this:

void bfs(int sx, int sy, int tx, int ty)
{
    std::queue<std::shared_ptr<Trip>> Q;
    std::shared_ptr<Trip> start(new Trip(sx, sy, nullptr));
    Q.push(start);
    while (!Q.empty())
    {
        std::shared_ptr<Trip> current = Q.front();
        Q.pop();
        current->write();
        int corx = current->first;
        int cory = current->second;
        if (!act[corx][cory])
        {
            act[corx][cory] = true;
            //up
            if (cory - 1 >= 0)
            {
                std::shared_ptr<Trip> neighbor(new Trip(corx, cory - 1, current));
                Q.push(neighbor);
            }
        }
    }
}