C++ vector增删操作导致指针失效，霍夫曼树生成出现循环引用如何解决？

核心问题 #

你遇到的指针异常问题本质是两个错误共同导致的：

• 你在vector中存储的是Node实体对象而非指针，每次pop_back、push_back操作要么会销毁原有对象，要么会触发vector内存扩容导致原有元素地址变更，你之前保存的子节点指针全部变成野指针/悬垂指针。
• 你取地址的leftNode、rightNode都是循环内的栈临时变量，当前循环结束后就会被系统回收，merge方法存储的指针直接指向无效内存，后续访问会读到垃圾值，才会出现自引用、循环引用的异常。
• 额外的内存泄漏问题：*(new Node())的写法会先在堆上申请节点内存，然后拷贝赋值给栈上的临时对象，堆上的原始节点直接丢失，永远无法被释放。

修复方案 #

直接把vector的存储类型从实体改为堆节点指针，指针本身的拷贝不会影响指向的堆内存地址，完全不受vector增删、扩容操作的影响：

1. 修改generateTree方法 #

void Huffman::generateTree() {
    // 存储Node指针而非实体
    std::vector<Node*> nodes;
    for (auto& itr : freq) {
        // 直接存堆上节点的指针
        nodes.push_back(new Node(itr.first, itr.second));
    }
    while (nodes.size() > 1) {
        Node::sort(&nodes);
        // 直接取指针，无需拷贝实体
        Node* leftNode = nodes.back();
        nodes.pop_back();
        Node* rightNode = nodes.back();
        nodes.pop_back();
        // 新节点也开在堆上
        Node* newAnode = new Node();
        newAnode->merge(leftNode, rightNode);
        nodes.push_back(newAnode);
    }
    root = nodes.back();
    displayTree();
}

2. 对应修改Node排序逻辑 #

因为vector现在存储的是指针，排序方法的参数也要同步调整：

bool Node::sortMethod::operator()(const Node* nodeA, const Node* nodeB) {
    return nodeA->getFrequency() > nodeB->getFrequency();
}
void Node::sort(std::vector<Node*>* nodes) {
    std::sort(nodes->begin(), nodes->end(), sortMethod());
}

额外注意事项 #

• 霍夫曼树使用结束后，要手动实现析构函数，递归遍历整棵树delete所有堆上的节点，避免内存泄漏。
• 如果使用C++11及更高版本，更推荐用std::unique_ptr<Node>代替裸指针，自动管理内存生命周期，无需手动释放，也能避免内存泄漏问题。
• 不要将栈上创建的Node节点指针存入vector或挂载到树上，栈节点的生命周期和函数绑定，函数执行结束就会被回收，必然导致野指针问题。

内容的提问来源于stack exchange，提问作者user16161541