0xC0000005: Access violation reading location 0xCDCDCDCD

Question

I have been having an issue with a Binary Search Tree that I am making for a larger project.

There is a node:

template <class Key, class Value>
struct Node
{
public:
    Key key;
    vector<Value> value;
    Node* leftNode;
    Node* rightNode;

    Node(Key k, Value v)
    {
        key = k;
        value.push_back(v);
    }
};

These nodes are being stored into the BST.

The error occurs in the Insertion function of the BST:

template <class Key, class Value>
void BinarySearchTree<Key, Value>::insert(const Key &key, const Value &value)
{
    insert(root, key, value);
}


template <class Key, class Value>
void BinarySearchTree<Key, Value>::insert(Node<Key, Value> *&node, const Key &key, const Value &value)
{
    if (node == nullptr)
        node = new Node<Key, Value>(key, value);

    // Error occurs here.
    else if (node->key == key)
        node->value.push_back(value);

    else if (key < node->key)
        insert(node->leftNode, key, value);
    else
        insert(node->rightNode, key, value);
}

The first node is inserted into the tree without issue, however the second Insertion call throws the error.

Any help in putting me on the right track would be greatly appreciated.

See https://stackoverflow.com/questions/127386/in-visual-studio-c-what-are-the-memory-allocation-representations — rustyx, Jul 16 '18 at 14:42
Have you tried running your code with a memory tool like Valgrind or clang Memory/Address Sanitizer? — idmean, Jul 16 '18 at 14:45
You might want to initialize leftNode and rightNode to nullptr. — AlexG, Jul 16 '18 at 14:45
If you are making a large project it is better not to reinvent a wheel. — Nikita Kniazev, Jul 16 '18 at 14:49
If this is for a larger project, and not an academic exercise, you may want to use `std::map`. — Ben Jones, Jul 16 '18 at 14:50
This is a problem with an uninitialised pointer, the value of 0xCDCDCDCD is the give away. I would add `leftNode = rightNode = nullptr;` to your constructor. — john, Jul 16 '18 at 14:54

score 3 · Accepted Answer · answered Jul 16 '18 at 14:55

3

Your insert code seems to assume that Node::leftNode and Node::rightNode are initialised to nullptr but your constructor doesn't ensure that. Try this

Node(Key k, Value v)
{
    key = k;
    value.push_back(v);
    leftNode = rightNode = nullptr;
}

answered Jul 16 '18 at 14:55

john

85,011
4
57
81

This seems to have done the trick. Thank you. I can't believe that I overlooked that – MattS Jul 16 '18 at 14:58
A good reason to compile with all warnings turned on - most compilers could catch this! – Ben Jones Jul 16 '18 at 14:59
1

BTW: heap memory is initialized with `0xCDCDCDCD` in debug builds in Visual Studio. Deleted memory is initialized with `0xDDDDDDDD`. – Jabberwocky Jul 16 '18 at 15:09

Caleth · Answer 2 · 2018-07-16T15:09:04.003

Your code isn't initialising leftNode or rightNode. Raw pointer values are not value-initialised if there is no member initialiser for them. std::unique_ptrs are default constructed equal to nullptr

There also doesn't seem to be any cleanup of Nodes

template <class Key, class Value>
struct Node
{
public:
    Key key;
    std::vector<Value> value;
    std::unique_ptr<Node> leftNode;
    std::unique_ptr<Node> rightNode;

    Node(Key k, Value v)
     : key(k), value({v})
    { }
};

0xC0000005: Access violation reading location 0xCDCDCDCD

2 Answers2