c++ - 在 while 循环内的变量中分配新内存

Question

我有一个 Town 类，它代表我图中的节点，如下所示:

class Town
{
public:
    Town();
public:
    Town* _parent;

    int _name;
    int _row;
    int _column;
    State _state;

    vector<Town*> _neighbors;
};

我有一个 Map 类，它包含城镇的二维 vector ，几乎可以构成我的随机图。

class Map
{
public:
    Map(const int elements, const int size, const int seed);
public: 
    vector <vector<Town> > _map;
    vector <Town*> _towns;
    vector <vector<int> > _adjacency;
    vector <vector<double> > _mDistance;
    vector <Line> _edges;

    const int _elements;
    const int _size;

    Town* _start;
    Town* _exit;
};

然后我的 AI 类接收一个 Map 对象并根据算法解决它，现在我正在实现 Astar。

class AI
{
private:
    struct TownWithCost
    {
        Town town;
        double cost;
    };

    struct OrderByTotalCost
    {
        bool operator()(TownWithCost lfs, TownWithCost rhs)
        {
            return lfs.cost > rhs.cost;
        }
    };
public:
    AI(Map map);
private:
    bool AStar(Town* town);

    double GetTotalCost(Town town);

public:
    bool _success;
private:
    Map _map;
};

这是我的 Astar 实现:

bool AI::AStar(Town* town)
{
    AI::OrderByTotalCost comparator;
    vector<TownWithCost> priorityQueue;

    TownWithCost currentTown = { *town, 0 };
    Town temp = currentTown.town;

    priorityQueue.push_back(currentTown);

    SetEnvironment(temp, State::visited);

    while (!priorityQueue.empty())
    {
        currentTown = priorityQueue.front();
        Town temp = currentTown.town;

        priorityQueue.erase(priorityQueue.begin());

        SetEnvironment(temp, State::visited);
        PrintEnvironment();

        if (temp._name == _map._exit->_name)
        {
            return true;
        }

        vector <Town*> neighbors = town->_neighbors;

        for each (Town* neighbor in neighbors)
        {
            Town tempNeighbor = *neighbor;

            if (tempNeighbor._state == State::town)
            {
                tempNeighbor._parent = &temp;
                TownWithCost neighborWithCost = { tempNeighbor, GetTotalCost(tempNeighbor) };

                priorityQueue.push_back(neighborWithCost);
            }
        }
        make_heap(priorityQueue.begin(), priorityQueue.end(), comparator);
    }
    return false;
}

正如您可能注意到的那样，我还没有实现查看 priorityQueue 以查看我是否已经在其中有一个 Town 并比较成本以查看哪个我想保留一个，但我计划在解决当前问题后实现它。

我的问题是，我不想在 priorityQueue 中有指针。我正在尝试制作将复制一个城镇的临时变量，它的成本来自某条路径。

假设我从 9 镇开始。

9 有邻居 0、7、8、3 特别是priorityQueue 在第一个循环中看起来像这样:

然后我得到 3 作为我的 currentTown，我正在检查它的邻居。

当我第二次到达 Town temp = currentTown.town; 行时，priorityQueue 中每个元素的父元素都被设置为 3 。现在我明白了为什么会这样，但我不明白的是如何防止这种情况发生。

我基本上需要的是 priorityQueue 来存储具有不同 parent 和不同成本的相同城镇(不同的内存地址)(我已经用结构 TownWithCost 处理了单独的成本)。所以总而言之，每次都要复印。

例如，我可以从 9 直接到达 0，总成本为 81，但我也可以通过 3 到达 0 (9 -> 3 -> 0)，总成本为 50。我希望能够区分这两者。

我如何在我的 priorityQueue 中区分它们以及如何避免重置父级，或者换句话说，我如何将另一部分内存分配给 Town temp每次循环运行时，我每次都可以有不同的温度？

如果您有其他方法(尽可能对新手友好)，请随时说出来。

Answer 1

您正在传递 Map 的值实例，并且此类没有复制构造函数或赋值运算符。当此类被浅拷贝(ala memcpy)时，vector 实例在被销毁(多次)时会导致崩溃。

尝试使用指针或引用。也会工作得更快。