I tried creating an octree in c . Seems to work fairly well, but when I print the content of the tree it returns an access violation error. Running this in debug will print two different numbers, although the content should not have been changed. Here is the printout:

2
11
32762

From what digging I have done it seems like the cout statement ends up mutating the octree object. I don't see why this should happen. If my approach is faulty, then why does it work in the first .get statement?

Here is my code:

#include <iostream>
typedef unsigned int uint;

template <typename T>
class OcTree {
    struct Node {
        Node* parent;
        uint depth;

        Node* children[8];
        T* data;
        
        Node(Node* parent, uint depth, uint max_depth) : parent{parent}, depth{depth} {
            for (int i=0; i<8; i  ) {
                children[i] = nullptr;
            }
            if (depth == max_depth) {
                data = new T[8];
                for (int i=0; i<8; i  ) {
                    data[i] = T(); //Initialize data to default values
                }
            } else {
                data = nullptr;
            }
        }
        ~Node() {
            delete[] data;
        }
    };

    uint max_depth;
    Node root;

    static uint make_subindex_from_index(uint x, uint y, uint z, uint depth) {
        uint mask = 1 << depth;
        uint x_bit, y_bit, z_bit;
        x_bit = x & mask;
        y_bit = y & mask;
        z_bit = z & mask;
        return compose_subindex(x_bit, y_bit, z_bit);
    }
    static uint compose_subindex(uint x_bit, uint y_bit, uint z_bit) {
        uint out = 0;
        if (x_bit) out  = 4;
        if (y_bit) out  = 2;
        if (z_bit) out  = 1;
        return out;
    }

public:
    OcTree(uint max_depth) : max_depth{max_depth}, root{Node(nullptr, 0, max_depth)} {}

    uint get_range() {
        return (uint)1 << max_depth;
    }

    void insert(uint x, uint y, uint z, T item) {
        Node* current_node = &root;
        uint subindex;
        for (uint d = 0; d < max_depth; d  ) {
            subindex = make_subindex_from_index(x, y, z, d);
            if (current_node->children[subindex] == nullptr) { //If the next node doesn't exist yet
                Node new_node = Node(current_node, d 1, max_depth); //Make it
                current_node->children[subindex] = &new_node;
            }
            current_node = current_node->children[subindex];
        }
        subindex = make_subindex_from_index(x, y, z, max_depth);
        current_node->data[subindex] = item;
    }

    T get(uint x, uint y, uint z) {
        Node* current_node = &root;
        uint subindex;
        for (uint d = 0; d < max_depth; d  ) {
            subindex = make_subindex_from_index(x, y, z, d);
            if (current_node->children[subindex] == nullptr) {
                std::cout << "Item does not exist!";
                throw -1;
            }
            current_node = current_node->children[subindex];
        }
        subindex = make_subindex_from_index(x, y, z, max_depth);
        return current_node->data[subindex];
    }
};
//Temporary for testing purposes
int main() {
    OcTree<int> test_tree = OcTree<int>(1);
    std::cout << test_tree.get_range() << "\n";
    test_tree.insert(0, 1, 2, 11);
    std::cout << test_tree.get(0, 1, 2) << "\n";
    std::cout << test_tree.get(0, 1, 2) << "\n";
}

CodePudding user response：

The specific error is here

           Node new_node = Node(current_node, d 1, max_depth); //Make it
            current_node->children[subindex] = &new_node;

'new_node' is a local variable and it will get destroyed once this function exits. You cannot store its address, its meaningless. UB.

You need

           Node *new_node = new Node(current_node, d 1, max_depth); //Make it
            current_node->children[subindex] = new_node;

Ie allocate it on the heap. Now you will have to deal with delete ing it once you are done with it.

You would be so so much better off if you learned to use

• std::vector for you arrays of things (like children)
• std::shared_ptr or std::unique_ptr instead of raw pointers

these 2 things will take care of a lot of issues for you