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

Question

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

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

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

    vector<Town*> _neighbors;
};

我有一个Map类，它包含一个城镇的二维向量，并且基本上是我的随机图。

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以不同的父母和不同的成本存储相同的城镇(而不是相同的内存地址)(我已经用struct TownWithCost处理了单独的成本)。所以总的来说，每次都要复印。

例如，我可以直接从9到0，总成本为81，但我也可以通过3 (9 -> 3 -> 0)获得总成本为50的0。我想把这两者区分开来。

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

如果你有另一种方式(尽可能友好地对待新手)来做这件事，那就随便说吧。

Answer 1

您传递的是Map的值实例，这个类没有复制构造函数或赋值操作符。当这个类被浅层复制(ala )时，当它们被销毁(多次)时，vector实例将导致崩溃。

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

Answer 2

您还可以使用指向城镇的数组或向量的索引向量。不需要指点。但就我个人而言，我更喜欢使用std:shared_ptr。