如何避免在 C++ 中使用 new 运算符？

Question

我有一个 C++ 程序，可以为文件中的所有字符创建霍夫曼代码。它运行良好，但我想在不使用 new 运算符的情况下创建节点，因为我知道您不应该使用它。我尝试使用向量全局变量来保存节点，但这不起作用。

std::vector<Node> nodes;

Node* create_node(unsigned char value, unsigned long long counter, Node* left, Node* right) {

    Node temp;
    temp.m_value = value;
    temp.m_counter = counter;
    temp.m_left = left;
    temp.m_right = right;

    nodes.push_back(temp);
    return &nodes[nodes.size() - 1];
}

编辑：我添加了更多代码，我没有真正解释什么不起作用。问题在于generate_code()，它永远不会到达 nullptr。我也尝试使用 Node 而不是 Node* 但同样的事情发生了。

void generate_code(Node* current, std::string code, std::map<unsigned char, std::string>& char_codes) {

    if (current == nullptr) {
        return;
    }

    if (!current->m_left && !current->m_right) {
        char_codes[current->m_value] = code;
    }

    generate_code(current->m_left, code + "0", char_codes);
    generate_code(current->m_right, code + "1", char_codes);
}


void huffman(std::ifstream& file) {

    std::unordered_map<unsigned char, ull> char_frequency;
    load_data(file, char_frequency);

    std::priority_queue<Node*, std::vector<Node*>, Comparator> queue;

    for (auto& node : char_frequency) {
        queue.push(create_node(node.first, node.second, nullptr, nullptr));
    }

    while (queue.size() != 1) {

        Node* left = queue.top();
        queue.pop();
        Node* right = queue.top();
        queue.pop();

        auto counter = left->m_counter + right->m_counter;
        queue.push(create_node('\0', counter, left, right));
    }
    
    std::map<unsigned char, std::string> char_codes;
    Node* root = queue.top();
    generate_code(root, "", char_codes);

    for (auto& i : char_codes) {
        std::cout << +i.first << ": " << i.second << "\n";
    }
}

Answer 1

一般的答案当然是使用智能指针，例如std::shared_ptr<Node>.
也就是说，使用常规指针并没有那么糟糕，尤其是当您从外部隐藏所有指针时。我不同意“你不应该使用new”，更像是“你应该意识到如果你这样做，你必须确保不会造成内存泄漏”。

无论如何，对于像你这样的事情，尤其是你的向量，你根本不需要实际的指针。只需为您的向量存储一个索引并替换每次出现的Node*by int，有点像：

class Node
{
    public:

        // constructors and accessors

    private:

        ValueType value;
        int index_left;
        int index_right;
}

我在这里使用了一个有符号整数作为索引，以便为不存在的引用存储 -1，类似于空指针。
请注意，这仅在没有从向量中擦除的情况下才有效，至少在所有内容都被销毁之前不会。如果灵活性是关键，则您需要某种指针。

另请注意，您不应将向量作为全局变量。相反，有一个包装类，其中Node是一个内部类，有点像这样：

class Tree
{
    public:

        class Node
        {
        ...
        };

        // some methods here

    private:
        
        vector<Node> nodes;
}

使用这种方法，您可以Node更好地封装您的类。Tree应该很可能是一个friend. 每个都Node将存储Tree对其所属的引用。

另一种可能性是使向量成为 的静态成员Node，但我建议不要这样做。如果向量是静态成员Node或全局对象，在这两种情况下，您创建的所有树都位于一个大容器中，这意味着当您不再需要它时，您无法从其中之一释放内存.
虽然这在技术上不会是内存泄漏，但在实践中，它可以很容易地作为一个。
另一方面，如果它被存储为Tree对象的成员，则该对象一被删除，内存就会自动释放。