c++ - 递归内存 "tree": properly freeing memory

Question

刚从我的第一门 CS 类(class)中走出来，我想更多地练习递归内存分配，所以我决定制作一个名为“递归地牢”的小游戏。它只是允许用户在每次玩家进入空 (NULL) 房间时递归生成一个新“房间”，从而在无限地牢中漫游。

然后保存新房间，可以通过...访问

1. 沿着进入房间时使用的完全相同的路径走
2. 如果您离开房间，请原路返回同一房间

*该程序不使用循环(至少，我认为它不使用)。我不熟悉循环的概念以及如何使用它。

我遇到的问题是当我尝试清理所有递归分配的内存(“房间”)时，我收到经典错误“段错误:核心已转储”。

下面是我的结构“房间”:

    struct room
    {//begin struct

        room* backward;
        room* left;
        room* forward;
        room* right;

        string desc;
  
        room() { //begin
    
            backward = NULL;
            left = NULL;
            forward = NULL;
            right = NULL;
    
        /*End*/}
 
    /*End struct*/};

每个“房间”都有与其相连的其他房间(左/右/前/后)。用户从一个空房间指针“起点”开始，并可以朝上述任何方向前进。尝试进入空 (NULL) 房间时，系统会随机生成一个新房间供用户进入。

一旦玩家对探索感到满意，我就会尝试在结束程序之前使用存储所有房间的数组来清理分配的内存。相反，它会导致段错误。这是代码:

    void ClearAllocatedMemory(room* aRoom, room** roomArray, int& raIndex) {

        for(short i=0; i<raIndex; i++) {//begin for
    
            delete roomArray[i];
    
        /*End for*/}
    
        delete[] roomArray;

    /*End func*/}

这是创建我的数组并定义其第一个(第 0 个)索引的代码:

    room** roomArray;
    int raIndex = 0;

    room* startingpoint = new room();
    roomArray[0] = startingpoint;

下面是将新房间添加到 roomArray 索引的代码:

    room* GenRoom(room** roomArray, int& raIndex) {

        room* newroom = new room();
    
        newroom->desc = GenRoomDesc( rand()%12 + 1 );
    
        raIndex++;
    
        roomArray[raIndex] = newroom;

        return newroom;


    }

Answer 1

即使双删除没问题，你的算法也不会工作。如果您有两个相互连接的房间，它们将递归地尝试相互删除，从而导致堆栈溢出。 IE。你不能用简单的递归来删除循环。

您有一个设计问题 - 谁拥有每个房间？如果这是用一种垃圾收集语言编写的，你就不会在意，房间会因为它们自己的存在而相互拥有。在 C++ 中，您必须关心并且设计应该反射(reflect)这一点。

shared_ptr和 std::weak_ptr在这种情况下会很困惑。即使您可以建立树状层次结构并因此使用 unique_ptr ，它可能仅仅由于深层树的嵌套析构函数而导致堆栈溢出。

最好和最简单的解决方案是创建单个 std::vector<Room>那是所有房间的明确所有者。然后邻居可以使用这个 vector 的索引。需要注意的是，取消分配 vector 中心的房间会使较高的索引无效。这可以通过与最后一个元素交换并仅修复它们的连接来解决。它还将从中间 O(1) 开始删除。

如果 map 真的是动态的，就像你的情况一样，我可以为 std::list<Room> 争论- 对邻居使用迭代器或指针 - 或 std::vector<std::unique_ptr<Room>> - 使用原始的非拥有指针。

这些仅限邻居的解决方案只是一个警告 - 当玩家循环探索房间时，您没有工具来确定该房间是否已经存在。例如。往上 2 次，向右 2 次，向下 2 次，向左 2 次应该让玩家回到初始房间。您可能需要考虑实际使用 2D 网格(稍后再担心内存/性能问题)。