如何避免在 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('[=11=]', 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”，更像是“你应该意识到，如果你这样做，你必须确保不会造成内存泄漏”。

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

class Node
{
    public:

        // constructors and accessors

    private:

        ValueType value;
        int index_left;
        int index_right;
}

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

另请注意，您不应将矢量作为 global variable。相反，有一个包装 class，其中 Node 是一个内部 class，有点像这样：

class Tree
{
    public:

        class Node
        {
        ...
        };

        // some methods here

    private:
        
        vector<Node> nodes;
}

通过这种方法，您可以更好地封装您的 Node class。 Tree 很可能是 friend。每个 Node 都会存储对它所属的 Tree 的引用。

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

Answer 2

but I want to create nodes without using new operator because I know that you shouldn't use it.

不鼓励直接使用 new 的原因是所有权语义（即谁负责相应的 delete）不明确。

C++ 标准库为此提供了 Dynamic memory management 实用程序，尤其是智能指针。

所以我认为您的创建函数应该如下所示：

std::unique_ptr<Node> create_node(unsigned char value, unsigned long long counter, Node* left, Node* right) {

    std::unique_ptr<Node> temp = std::make_unique<Node>();
    temp->m_value = value;
    temp->m_counter = counter;
    temp->m_left = left;
    temp->m_right = right;

    return temp;
}

这样很明显，调用者获得了新创建的 Node 实例的所有权。

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

How to avoid using new operator in C++?

c++

new-operator