How to avoid using new operator in C++?

Question

I have a C++ program that creates Huffman codes for all characters in file. It works good, but I want to create nodes without using new operator because I know that you shouldn't use it. I tried using a vector global variable for saving nodes but that doesn't work.

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];
}

Edit: I added more code, I did't really explained what doesn't work. Problem is in generate_code(), it never reaches nullptr. I also tried using Node and not Node* but the same thing happened.

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

The general answer is of course to use smart pointers, like std::shared_ptr<Node>.
That said, using regular pointers is not that bad, especially if you hide all pointers from the outside. I wouldn't agree with "you shouldn't use new", more like "you should realize that you have to make sure not to create a memory leak if you do".

In any case, for something like you do, especially with your vector, you don't need actual pointers at all. Simply store an index for your vector and replace every occurence of Node* by int, somewhat like:

class Node
{
    public:

        // constructors and accessors

    private:

        ValueType value;
        int index_left;
        int index_right;
}

I used a signed integer as index here in order to allow storing -1 for a non-existent reference, similar to a null pointer.
Note that this only works if nothing gets erased from the vector, at least not before everything is destroyed. If flexibility is the key, you need pointers of some sort.

Also note that you should not have a vector as a global variable. Instead, have a wrapping class, of which Node is an inner class, somewhat like this:

class Tree
{
    public:

        class Node
        {
        ...
        };

        // some methods here

    private:
        
        vector<Node> nodes;
}

With such an approach, you can encapsulate your Node class better. Tree should most likely be a friend. Each Node would store a reference to the Tree it belongs to.

Another possibility would be to make the vector a static member for Node, but I would advise against that. If the vector is a static member of Node or a global object, in both cases, you have all trees you create being in one big container, which means you can't free your memory from one of them when you don't need it anymore.
While this would technically not be a memory leak, in practice, it could easily work as one.
On the other hand, if it is stored as a member of a Tree object, the memory is automatically freed as soon as that object is removed.

Answer 2

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

The reason it is discouraged to use new directly is that the semantics of ownership (i.e. who is responsible for the corresponding delete) isn't clear.

The c++ standard library provides the Dynamic memory management utilities for this, the smart pointers in particular.

So I think your create function should look like follows:

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;
}

This way it's clear that the caller takes ownership of the newly created Node instance.