0

I'm trying to create a binary node iterator where you can iterate through the nodes in ascending order, but when I try to iterate through it, the program crashes and I get a double free detected error. Here is my iterator class.

#include <memory>
#include <map>
#include <iostream>
#include <cstddef>

template <class T>
    class BinaryNode
    {
    public:
        T       data;
        BinaryNode* left;
        BinaryNode* right;
        BinaryNode* parent;
        BinaryNode(T data) : data(data), left(NULL), right(NULL), parent(NULL)
        {
        }
        BinaryNode(T data, BinaryNode* parent) : data(data), left(NULL), right(NULL), parent(parent)
        {
        }
    };
    template <class T, class Compare, class Node=BinaryNode<T>, class Alloc=std::allocator<Node> >
    class BinaryTreeIterator
    {
    public:
        typedef T    value_type;
        typedef T& reference;
        typedef T* pointer;

        typedef Alloc               allocator_type;
        typedef Compare             key_compare;
        BinaryTreeIterator(Node* curr, Node* first, Node* last, size_t sz) : curr(curr), first(first), last(last), sz(sz), comp(key_compare()), alloc(allocator_type())
        {
            this->end = this->alloc.allocate(1);
            this->alloc.construct(this->end, Node(std::make_pair(sz, typename value_type::second_type())));
        }
        ~BinaryTreeIterator()
        {
            this->alloc.destroy(this->end);
            this->alloc.deallocate(this->end, 1);
        }
        reference operator*() const
        {
            if (this->curr == NULL)
                return (this->end->data);
            else
                return (this->curr->data);
        }
        pointer operator->() const
        {
            if (this->curr == NULL)
                return (&this->end->data);
            else
                return (&this->curr->data);
        }
        BinaryTreeIterator& operator++()
        {
            Node* tmp = this->curr;
            if (this->curr == NULL)
            {
                this->curr = this->first;
            }
            else if (tmp->right == NULL)
            {
                tmp = tmp->parent;
                while (tmp != NULL && this->comp(tmp->data.first, this->curr->data.first))
                    tmp = tmp->parent;
                this->curr = tmp;
            }
            else
            {
                tmp = tmp->right;
                while (tmp->left != NULL)
                {
                    tmp = tmp->left;
                }
                this->curr = tmp;
            }
            return (*this);
        }
        BinaryTreeIterator operator++(int)
        {
            BinaryTreeIterator tmp = *this;
            ++*this;
            return (tmp);
        }
        Node* curr;
        Node* first;
        Node* last;
        Node* end;
        size_t sz;
        key_compare comp;
        allocator_type alloc;
    };

typedef std::pair<const int, int> pair;
typedef BinaryNode<pair> Node;
int main()
{
    std::allocator<Node> alloc;
    Node* root = alloc.allocate(1);
    alloc.construct(root, Node(std::make_pair(5, 5)));
    root->right = alloc.allocate(1);
    alloc.construct(root->right, Node(std::make_pair(6, 5), root));
    root->left = alloc.allocate(1);
    alloc.construct(root->left, Node(std::make_pair(4, 5), root));
    BinaryTreeIterator<pair, std::less<int> > bst(root->left, root->left, root->right, 5);
    std::cout << bst->first << std::endl;
    bst++;
    std::cout << bst->first << std::endl;
    bst++;
    std::cout << bst->first << std::endl;
}

I'm using pairs as data for the node instead of just an int. When I remove whats inside the destructor everything works fine, so I'm guessing the destructor is called twice? How ever, the program does crash before printing the last bst->first. Is there something wrong with my logic when iterating through the nodes?

Sami
  • 75
  • 1
  • 9
  • You violated the Rule of Three. You create a copy of `BinaryTreeIterator` here: `BinaryTreeIterator tmp = *this;` and that object must be destroyed too (which you see as "calling destructor twice"). – Yksisarvinen Jun 18 '22 at 22:52
  • Why is there even any allocation/deallocation related stuff in iterator? That's not what anyone would expect from an iterator class. – Yksisarvinen Jun 18 '22 at 22:52
  • Oh I dint even think about that, nice catch, how is a postfix operator overload usually implemented? – Sami Jun 18 '22 at 22:57
  • Good wisdom on that side-question here: [What are the basic rules and idioms for operator overloading?](https://stackoverflow.com/questions/4421706) – user4581301 Jun 18 '22 at 23:01
  • Postfix increment is usually implemented exactly like you did. It is expected to make a copy, increment with prefix and return that copy (see [this answer](https://stackoverflow.com/a/4421719/7976805)). But your copying is wrong, because the default copy constructor is not enough in this case (and if you have a custom destructor, implicit copy constructor is almost always wrong, that's the point of Rule of Three). Or I'd rather say that allocating and deallocating stuff in iterator is wrong, if it wasn't here, default destructor and default copy constructor would be just fine. – Yksisarvinen Jun 18 '22 at 23:02

0 Answers0