erase() [2/2]

template<typename T, typename Compare = less<T>, typename Allocator = allocator_slab<char>>

iterator fl::RedBlackTree< T, Compare, Allocator >::erase ( const_iterator pos )

inline

Definition at line 577 of file rbtree.h.

                                       {
        if (pos.node_ == nullptr) return end();
        
        Node* nodeToDelete = const_cast<Node*>(pos.node_);
        Node* successor = nullptr;
        
        if (nodeToDelete->right != nullptr) {
            successor = minimum(nodeToDelete->right);
        } else {
            Node* current = nodeToDelete;
            Node* parent = current->parent;
            while (parent != nullptr && current == parent->right) {
                current = parent;
                parent = parent->parent;
            }
            successor = parent;
        }
        
        Node* y = nodeToDelete;
        Node* x = nullptr;
        Node* xParent = nullptr;
        Color originalColor = y->color;
        
        if (nodeToDelete->left == nullptr) {
            x = nodeToDelete->right;
            xParent = nodeToDelete->parent;
            transplant(nodeToDelete, nodeToDelete->right);
        } else if (nodeToDelete->right == nullptr) {
            x = nodeToDelete->left;
            xParent = nodeToDelete->parent;
            transplant(nodeToDelete, nodeToDelete->left);
        } else {
            y = minimum(nodeToDelete->right);
            originalColor = y->color;
            x = y->right;
            if (y->parent == nodeToDelete) {
                xParent = y;
                if (x) x->parent = y;
            } else {
                xParent = y->parent;
                transplant(y, y->right);
                y->right = nodeToDelete->right;
                y->right->parent = y;
            }
            
            transplant(nodeToDelete, y);
            y->left = nodeToDelete->left;
            y->left->parent = y;
            y->color = nodeToDelete->color;
        }
        
        alloc_.destroy(nodeToDelete);
        alloc_.deallocate(nodeToDelete, 1);
        --size_;
        
        if (originalColor == BLACK) {
            deleteFixup(x, xParent);
        }
        
        return iterator(successor, this);
    }

Referenced by fl::RedBlackTree< value_type, PairCompare, Allocator >::erase().

Here is the caller graph for this function: