C++二叉树迭代器使用std::allocator触发double free错误排查

实现升序遍历的二叉树迭代器时，程序运行抛出Free() double free detected when trying to free memory using std::allocator错误，移除迭代器析构中的内存释放逻辑后程序可正常运行，崩溃发生在打印最后一个节点值之前。
附复现代码：

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

崩溃是两个问题叠加导致的：

• 浅拷贝引发double free
  后自增运算符operator++(int)返回值是迭代器对象类型，返回时会调用编译器默认生成的拷贝构造函数，该函数仅做浅拷贝：临时对象tmp和原迭代器bst的end指针会指向同一块堆内存。临时对象在bst++;语句执行结束后就会析构，释放end指向的内存，后续临时对象再次析构、或者原迭代器bst析构时，会重复释放同一块内存，直接触发double free错误。这个崩溃点刚好出现在第二次bst++执行后、第三次打印之前，和观察到的崩溃时机完全吻合。
• 中序遍历后继逻辑错误
  右子树为空时向上回溯父节点的判断条件写反了：现有逻辑是当父节点key小于当前节点key时继续向上跳，会直接跳过正确的后继节点走到NULL。正确逻辑应该是一直向上找，直到找到第一个key大于当前节点的父节点才停止。

• 修正迭代器的内存所有权设计：迭代器不应该持有end节点的所有权，参考STL实现规范，end节点应该由二叉树容器本身持有，迭代器仅保存节点指针，不需要在迭代器析构函数中释放end节点内存，从根源避免浅拷贝导致的重复释放问题。如果暂时不实现容器层，可以先给迭代器实现深拷贝逻辑、或者用引用计数管理end节点内存，临时验证功能。
• 修正父节点回溯的判断条件，把循环判断从this->comp(tmp->data.first, this->curr->data.first)改为tmp != NULL && !this->comp(this->curr->data.first, tmp->data.first)，即只要父节点key不大于当前节点key，就继续向上回溯。

内容的提问来源于stack exchange，提问作者Sami