在 C++ 中实现 A* 时可能发生内存泄漏

Question

我编程已经有一段时间了，但我对 C++ 还是比较陌生。我正在尝试实现 A* 算法并设法生成以下代码。该实现产生了预期的结果，即二维网格中从 A 点到 B 点的最短路径，但我怀疑我留下了一些内存泄漏。

我通过重载 new 和 delete 运算符来测试这个，以跟踪堆上分配的字节数，结果表明很多内存从未被释放。然而，我也测试了从未被删除的节点数量，但它表明所有分配的节点也调用了它们的析构函数。请注意，在代码中我只在 Node 上调用 new，因此我很困惑。我对此很困惑，很高兴得到解释。

我尝试过使用智能指针，但最终得到了难以解决的循环引用。

这也是我在 Stack Overflow 上的第一个 post，所以请随时指出我如何改进我的问题。提前致谢。

#include<vector>
#include<array>
#include<cmath>

int mynodes = 0;
int memory_left = 0;

void* operator new(size_t size)
{
    memory_left += size;
    return malloc(size);
}

void operator delete(void* memory, size_t size)
{
    memory_left -= size;
    free(memory);
}

struct Node{
    std::array<int, 2> position;
    Node* parent = nullptr;
    double h, g, f;

    Node(const std::array<int, 2>& pos)
        :position(pos){mynodes++;}


    ~Node(){ mynodes--; }
};


std::vector<std::array<int, 2>> find_children(const std::vector<std::vector<int>>& grid, const std::array<int, 2>& pos){

    std::vector<std::array<int, 2>> children;
    children.reserve(8);

    for(int t = -1; t < 2; t++){
        for(int q = -1; q < 2; q++){
            if(t != 0 || q != 0){
                if(abs(t) == abs(q)) continue;

                std::array<int, 2> cur_pos = {pos[0]+q, pos[1]+t};
                if(cur_pos[0] >= 0 && cur_pos[0] < grid[0].size() && cur_pos[1] >= 0 && cur_pos[1] < grid.size())
                {
                    if(grid[cur_pos[1]][cur_pos[0]] == 0)
                    {
                        children.push_back(cur_pos);
                    }
                }
            }
        }
    }

    return children;
}

bool search_vect(const std::vector<Node*>& set, const std::array<int, 2>& pos)
{
    for(Node* node : set)
    {
        if(node->position[0] == pos[0] && node->position[1] == pos[1]) return true;
    }
    return false;
}

void releaseNodes(std::vector<Node*>& set)
{
    for(auto& node : set)
    {
        delete node;
    }
    set.clear();
}

std::vector<std::array<int, 2>> find_path(const std::vector<std::vector<int>>& grid, std::array<int, 2> start, std::array<int, 2> end){

    Node* cur_node = new Node(start);
    std::vector<Node*> open_vect;
    std::vector<Node*> closed_vect;
    open_vect.push_back(cur_node);

    while(cur_node->position != end){

        double lowest_f = INFINITY;
        size_t idx = 0;
        for(size_t i = 0; i < open_vect.size(); i++)
        {
            if(open_vect[i]->f < lowest_f)
            {
                cur_node = open_vect[i];
                lowest_f = cur_node->f;
                idx = i;
            }
        }
        open_vect.erase(open_vect.begin() + idx);

        std::vector<std::array<int, 2>> children = find_children(grid, cur_node->position);
        closed_vect.push_back(cur_node);

        for(const auto& child_pos : children){
            // if(closed_vect.find(child_pos) != closed_vect.end() || open_vect.find(child_pos) != open_vect.end()) continue;
            if(search_vect(closed_vect, child_pos) || search_vect(open_vect, child_pos))
            {
                continue;
            }

            Node* new_node = new Node(child_pos);
            new_node->g = cur_node->g + 1;
            new_node->h = abs(end[0] - child_pos[0]) + abs(end[1] - child_pos[1]);
            new_node->f = new_node->g + new_node->h;
            new_node->parent = cur_node;

            // double h = sqrt(pow(end[0] - child_pos[0], 2) + pow(end[1] - child_pos[1], 2));

            open_vect.push_back(new_node);

        }
    }

    std::vector<std::array<int, 2>> path;
    while(cur_node != nullptr){
        path.push_back(cur_node->position);
        cur_node = cur_node->parent;
    }

    releaseNodes(open_vect);
    releaseNodes(closed_vect);

    return path;
}


int main()
{
    std::vector<std::vector<int>> grid( 100 , std::vector<int> (100, 0));

    {
        auto path = find_path(grid, {1, 1}, {98, 98});
    }


}

Answer 1

这里是 minimal/easy 摆脱任何显式 new/delete 的方法：

#include<vector>
#include<array>
#include<cmath>

struct Node{
    std::array<int, 2> position;
    Node* parent = nullptr;
    double h{0.};
    double g{0.};
    double f{0.};
    Node(const std::array<int, 2>& pos)
        : position(pos) {}
};


std::vector<std::array<int, 2>> find_children(const std::vector<std::vector<int>>& grid, const std::array<int, 2>& pos){

    std::vector<std::array<int, 2>> children;
    children.reserve(8);

    for(int t = -1; t < 2; t++){
        for(int q = -1; q < 2; q++){
            if(t != 0 || q != 0){
                if(abs(t) == abs(q)) continue;

                std::array<int, 2> cur_pos = {pos[0]+q, pos[1]+t};
                if(cur_pos[0] >= 0 && cur_pos[0] < grid[0].size() && cur_pos[1] >= 0 && cur_pos[1] < grid.size())
                {
                    if(grid[cur_pos[1]][cur_pos[0]] == 0)
                    {
                        children.push_back(cur_pos);
                    }
                }
            }
        }
    }

    return children;
}

bool search_vect(const std::vector<Node*>& set, const std::array<int, 2>& pos)
{
    for(Node* node : set)
    {
        if(node->position[0] == pos[0] && node->position[1] == pos[1]) return true;
    }
    return false;
}

std::vector<std::array<int, 2>> find_path(const std::vector<std::vector<int>>& grid, std::array<int, 2> start, std::array<int, 2> end){

    std::vector<Node> nodes{};
    nodes.emplace_back(start);
    Node* cur_node = &nodes.back();
    std::vector<Node*> open_vect;
    std::vector<Node*> closed_vect;
    open_vect.push_back(cur_node);

    while(cur_node->position != end){

        double lowest_f = INFINITY;
        size_t idx = 0;
        for(size_t i = 0; i < open_vect.size(); i++)
        {
            if(open_vect[i]->f < lowest_f)
            {
                cur_node = open_vect[i];
                lowest_f = cur_node->f;
                idx = i;
            }
        }
        open_vect.erase(open_vect.begin() + idx);

        std::vector<std::array<int, 2>> children = find_children(grid, cur_node->position);
        closed_vect.push_back(cur_node);

        for(const auto& child_pos : children){
            // if(closed_vect.find(child_pos) != closed_vect.end() || open_vect.find(child_pos) != open_vect.end()) continue;
            if(search_vect(closed_vect, child_pos) || search_vect(open_vect, child_pos))
            {
                continue;
            }
            nodes.emplace_back(child_pos);
            Node* new_node = &nodes.back();
            new_node->g = cur_node->g + 1;
            new_node->h = abs(end[0] - child_pos[0]) + abs(end[1] - child_pos[1]);
            new_node->f = new_node->g + new_node->h;
            new_node->parent = cur_node;

            // double h = sqrt(pow(end[0] - child_pos[0], 2) + pow(end[1] - child_pos[1], 2));

            open_vect.push_back(new_node);

        }
    }

    std::vector<std::array<int, 2>> path;
    while(cur_node != nullptr){
        path.push_back(cur_node->position);
        cur_node = cur_node->parent;
    }

    return path;
}


int main()
{
    std::vector<std::vector<int>> grid( 100 , std::vector<int> (100, 0));

    {
        auto path = find_path(grid, {1, 1}, {98, 98});
    }


}

这并不完美，但它很容易证明不引起任何潜在的内存泄漏是多么容易。我没有用节点向量替换指针向量，而是添加了一个额外的节点向量（所有者）。现在指针是非拥有的，不会再发生任何奇怪的事情了。

在 C++ 中实现 A* 时可能发生内存泄漏

Possible memory leak when implementing A* in C++

c++

debugging

memory-leaks

a-star