具有太多堆指针删除的 C++ 未定义行为

Question

我编写了一个程序来创建一个链接列表，当我将列表的大小增加到一定程度并且尝试删除时，我得到了未定义的行为（或者我假设我这样做了，因为程序刚刚停止而没有任何错误）它（通过结束其范围）。代码的基本版本如下：

#include <iostream>
#include <memory>

template<typename T> struct Nodeptr;

template<class T>
struct Node {
    Nodeptr<T> next;
    T data;

    Node(const T& data) : data(data) { } 
};

template<class T>
struct Nodeptr : public std::shared_ptr<Node<T>> {
    Nodeptr() : std::shared_ptr<Node<T>>(nullptr) { }
    Nodeptr(const T& data) : std::shared_ptr<Node<T>>(new Node<T>(data)) { }
};

template<class T>
struct LinkedList {

    Nodeptr<T> head;

    void prepend(const T& data) {
        auto new_head = Nodeptr<T>(data);
        new_head->next = head;
        head = new_head;
    }
};

int main() {

    int iterations = 10000;

    {
        LinkedList<float> ls;
        std::cout << "START\n";
        for(float k = 0.0f; k < iterations; k++) {
            ls.prepend(k);
        }
        std::cout << "COMPLETE\n";
    }

    std::cout << "DONE\n";

    return 0;
}

现在，当代码运行时，会打印 START 和 COMPLETE，而不会打印 DONE。程序提前退出，没有错误（由于某种原因）。当我将变量减少到 5000 而不是 10000 时，它工作得很好并且会打印 DONE。当我删除 LinkedList 声明/测试块周围的大括号（将其取出较小的范围，导致在打印 DONE 之前不会删除它）时，一切正常并打印 DONE 。因此，错误一定是由于删除过程而产生的，特别是因为被删除的内容量很大。然而，没有错误消息告诉我堆中没有更多空间，而且 10000 个浮点数似乎根本无法填满堆。任何帮助，将不胜感激！

---

解决了！它现在直接使用堆指针工作，我更改了 Node 的析构函数以防止对其进行递归调用：

        ~Node() {
            if(!next) return;
            Node* ptr = next;
            Node* temp = nullptr;
            while(ptr) {
                temp = ptr->next;
                ptr->next = nullptr;
                delete ptr;
                ptr = temp;
            }
        }

Answer 1

这是由递归析构函数调用引起的堆栈溢出。

这是智能指针的一个常见问题，在编写任何深度嵌套的数据结构时应该注意。

您需要一个显式析构函数，Node通过从列表尾部开始重置智能指针来迭代删除元素。还要遵循 3/5 规则，并对可能递归地破坏节点的所有其他操作执行相同的操作。

因为这本质上是重写所有对象销毁，但是它首先使用智能指针有点值得怀疑，尽管在防止双重删除（和泄漏）错误方面仍然有一些好处。因此，在这种情况下，通常根本不使用智能指针，而是回退到数据结构节点的原始指针和手动生命周期管理。

std::shared_ptr另外，无论如何也没有必要在这里使用。每个节点只有一个所有者。它应该是std::unique_ptr。std::shared_ptr对性能有非常显着的影响，并且如果形成循环引用（无论有意或无意），还存在可能导致泄漏的问题。

我也不认为Nodeptr单独开设一个班级有任何意义。它似乎只是用作 的别名std::make_shared<Node>，只需使用函数即可实现。尤其是从标准库智能指针继承似乎很可疑。如果有的话我会用组合来代替。