[求助]如果有人肯帮忙看看，那真是麻烦大家了，写了一个红黑树，可是有点问题。

[linux40]

目前只测试了 inesert 和 erase 操作。 insert 操作完全正确（至少连续的 insert 操作，中间没有 erase ，没有任何问题）， erase 操作（测试的是连续的删除操作，从 begin 开始删）会出现两种错误：

• 一种是 double free ，这种情况时，上一个的上一个删除的会是最大的元素。会出现最大的元素的原因是为了实现 c++的 end 而有一个 end of tree 结点 eot ， eot 的 parent ， eot->p 指向红黑树的 root ， eot 的 left ， eot->l 指向最大的元素， eot 的 right ， eot->r 指向最小的元素。
• 第二种是死循环，死循环会出现在当删除的结点 node 的 left 和 right 都不等于 eot 的时候，寻找排在 node 后面的结点的那一步，假设 node->r == r ， while (r->l != eot)会一直执行。不过出现死循环时， node 的 value ， node->v 是一个未定义的值，可能也是之前 free 过的。

把 erase fix 注释掉后完全正常，并且与标准库的比较过。 测试的代码：

    std::random_device rd;
    std::mt19937 gen(rd());
    std::uniform_int_distribution<int> dis(1, 50000);
    int arr[10000];
    for (int i = 0; i != 10000; ++i)
        arr[i] = dis(gen);
    glglT::multiset<int> g(arr, arr + 10000);
    auto git = g.begin();
    for (std::size_t i = 0; i != 5000; ++i)
        git = g.erase(git);

erase 的写法，真正 erase 的函数由于没有 fix 的话，是完全正常的，所以暂时不贴。

    iterator erase(const_iterator itr)
    {//erase 不移动值，只移动结点本身
        this->erase((itr++).curr);
        return static_cast<iterator>(itr);
    }

erase fix，之前判断了删除的node的颜色是黑色，才调用。

    void erase_fix(rebind_ptr p, bool is_left)
    {//表示删除的结点是其 parent 的左边还是右边， p 的 left 和 right 赋值正确了的，最大最小结点即 eot->l 和 eot->r 也赋值正确
        for (rebind_ptr black_p = is_left ? p->l : p->r; p != eot;) {
            if (black_p->is_red) {
                black_p->is_red = false;
                return;
            }
            rebind_ptr b = is_left ? p->r : p->l;
            if (b->is_red) {
                if (is_left) {
                    this->left_rotate(p, b);
                    b = p->r;
                } else {
                    this->right_rotate(p, b);
                    b = p->l;
                }
            }
            rebind_ptr c = is_left ? b->r : b->l;
            if (!c->is_red) {
                if (is_left ? !b->l->is_red : !b->r->is_red) {
                    b->is_red = true;
                    black_p = p;
                    p = p->p;
                    is_left = black_p == p->l;
                    continue;
                }
                is_left ? this->right_rotate(b, b->l) : this->left_rotate(b, b->r);
                b->is_red = true;
                c = b;
                b = b->p;
                b->is_red = false;
            }
            is_left ? this->left_rotate(p, b) : this->right_rotate(p, b);
            c->is_red = false;
            glglT::swap(p->is_red, b->is_red);
            break;
        }   eot->p->is_red = false;
    }

需要别的信息的话，我会在添加的。

[linux40]

顶一下？( ；∀；)

[linux40]

呃，知道了，有个地方忘改颜色了，我调试了两天呀( ；∀；)

[lsmgeb89]

写的时候就要逐步测试，最后 random 测的话，查起来很累。