Binary Search Tree

#include <bits/stdc++.h>

template<typename K, typename V>
class Dict;

template<typename T>
struct Node {

    typedef Node<T>* node_ptr;

    Node(const T& value)
        : _data(value)
        , _prnt(NULL)
        , _left(NULL)
        , _rght(NULL)
    {
    }

    static node_ptr minimum(node_ptr node)
    {
        while (node->_left) {
            node = node->_left;
        }
        return node;
    }

    static node_ptr maximum(node_ptr node)
    {
        while (node->_rght) {
            node = node->_rght;
        }
        return node;
    }

    T        _data;
    node_ptr _prnt;
    node_ptr _left;
    node_ptr _rght;
};

template<typename K, typename V>
class dict_iterator
{

public:

    typedef std::bidirectional_iterator_tag iterator_category;
    typedef std::ptrdiff_t                  difference_type;
    typedef std::size_t                     size_type;
    typedef std::pair<K, V>                               value_type;
    typedef value_type*                              pointer;
    typedef value_type&                              reference;
    typedef typename Node<value_type>::node_ptr      node_ptr;
    typedef dict_iterator<K, V>                iterator;

    friend class Dict<K, V>;

public:

    dict_iterator()
        : _this(NULL)
    {
    }

    dict_iterator(node_ptr value)
        : _this(value)
    {
    }

    dict_iterator(const iterator& other)
        : _this(other._this)
    {
    }

    ///////////////////////////////////////////////////
    // Operators
    ///////////////////////////////////////////////////

    // Assignment

    iterator& operator = (const iterator& other)
    {
        _this = other._this;
        return *this;
    }

    iterator& operator += (difference_type size)
    {
        _this += size;
        return *this;
    }

    iterator& operator -= (difference_type size)
    {
        _this -= size;
        return *this;
    }

    // Increment

    iterator& operator ++ ()
    {
        if (_this->_rght) {
            _this = _this->_rght;
            while (_this->_left) {
                _this = _this->_left;
            }
        } else {
            node_ptr temp = _this->_prnt;
            while (_this == temp->_rght) {
                _this = temp;
                temp = temp->_prnt;
            }
            if (_this->_rght != temp) {
                _this->_rght = temp;
            }
        }
        return *this;
    }

    iterator operator ++ (int)
    {
        iterator temp(*this);
        operator++();
        return temp;
    }

    iterator& operator -- ()
    {
        if (_this->_left) {
            _this = _this->_left;
            while (_this->_rght) {
                _this = _this->_rght;
            }
        } else {
            node_ptr temp = _this->_prnt;
            while (_this == temp->_left) {
                _this = temp;
                temp = temp->_prnt;
            }
            _this = temp;
        }
        return *this;
    }

    iterator operator -- (int)
    {
        iterator temp(*this);
        operator--();
        return temp;
    }

    // Binary

    friend iterator operator + (iterator lhs, difference_type size)
    {
        while (size-- > 0) {
            ++lhs;
        }
        return lhs;
    }

    friend iterator operator - (iterator lhs, difference_type size)
    {
        while (size-- > 0) {
            --lhs;
        }
        return lhs;
    }

    // Relational

    inline bool operator == (const iterator& rhs) const
    {
        return _this == rhs._this;
    }

    inline bool operator != (const iterator& rhs) const
    {
        return !operator==(rhs);
    }

    // Dereference

    reference operator * () const
    {
        return _this->_data;
    }

    pointer operator -> () const
    {
        return &(operator*());
    }

private:

    node_ptr _this;

};

template<typename K, typename V>
class Dict {

private:
    typedef Dict<K, V>                      dict;
public:
    typedef std::pair<K, V>                 value_type;
    typedef value_type*                     pointer;
    typedef const value_type*               const_pointer;
    typedef value_type&                     reference;
    typedef const value_type&               const_reference;
    typedef std::size_t                     size_type;
    typedef std::ptrdiff_t                  difference_type;
    typedef Node<value_type>                node;
    typedef node*                           node_ptr;
    typedef node&                           node_reference;
    typedef dict_iterator<K, V>       iterator;
    typedef std::reverse_iterator<iterator> reverse_iterator;

public:

    iterator begin()
    {
        return iterator(_root->minimum());
    }

    iterator end()
    {
        return iterator(NULL);
    }

    reverse_iterator rbegin()
    {
        return reverse_iterator(_root->maximum());
    }

    reverse_iterator rend()
    {
        return reverse_iterator(end());
    }

public:

    Dict()
        : _root(NULL)
        , _size(0)
    {

    }

    Dict& operator = (const Dict& other)
    {

    }

    ~Dict()
    {
    }

    size_type size() const
    {
        return _size;
    }

    iterator find(const K& key)
    {
        if (_size == 0) {
            return end();
        }

        if (_size == 1 && _root->_data.first == key) {
            return iterator(_root);
        }

        assert(_root != NULL);
        node_ptr it = _root;
        while (it) {
            bool hasLeftChild = it->_left;
            bool hasRghtChild = it->_rght;
            bool isKeyLess = key < it->_data.first;
            bool isKeyMore = it->_data.first < key;

            if (hasLeftChild && isKeyLess) {
                it = it->_left;
            } else if (hasRghtChild && isKeyMore) {
                it = it->_rght;
            } else {
                if (!(isKeyLess || isKeyMore)) {
                    // Key found!
                    return iterator(it);
                } else {
                    return end();
                }
            }
        }
        return end();
    }

    inline std::pair<iterator, bool> insert(const K& key, const V& value)
    {
        return insert(std::make_pair(key, value));
    }

    std::pair<iterator, bool> insert(const value_type& value)
    {
        // If tree in empty, give special treatment to root
        if (_size == 0) {
            _root = new node(value);
            ++_size;
            return std::make_pair(iterator(_root), true);
        }

        node_ptr ptr = _root;
        while (ptr) {
            bool hasLeftChild = ptr->_left;
            bool hasRghtChild = ptr->_rght;
            bool isKeyLess = value.first < ptr->_data.first;
            bool isKeyMore = ptr->_data.first < value.first;

            if (hasLeftChild && isKeyLess) {
                ptr = ptr->_left;
            } else if (hasRghtChild && isKeyMore) {
                ptr = ptr->_rght;
            } else {
                if (isKeyLess) {
                    ptr->_left = new node(value);
                    ptr->_left->_prnt = ptr;
                    ptr = ptr->_left;
                } else if (isKeyMore) {
                    ptr->_rght = new node(value);
                    ptr->_rght->_prnt = ptr;
                    ptr = ptr->_rght;
                }
                ++_size;
                return std::make_pair(iterator(ptr), true);
            }
        }
        return std::make_pair(end(), false);
    }

    void erase(iterator it)
    {
        // Return if the iterator doesn't make sense
        if (it == end()) {
            return;
        }

        // If it's the last node, give it special treatment
        if (_size == 1) {
            delete _root;
            _root = NULL;
            --_size;
            return;
        }

        node_ptr ptr = it._this;
        if (!ptr->_left) {
            // No left child, so just have the right child be the new child
            if (ptr->_prnt && ptr->_prnt->_left == ptr) {
                // If he's the left child
                ptr->_prnt->_left = ptr->_rght;
            } else if (ptr->_prnt && ptr->_prnt->_rght == ptr) {
                // If he's the right child
                ptr->_prnt->_rght = ptr->_rght;
            }
            if (ptr->_rght) {
                ptr->_rght->_prnt = ptr->_prnt;
            }
            delete ptr;
        } else if (!ptr->_rght) {
            // No right child, so just have the left child be the new child
            if (ptr->_prnt && ptr->_prnt->_left == ptr) {
                // If he's the left child
                ptr->_prnt->_left = ptr->_left;
            } else if (ptr->_prnt && ptr->_prnt->_rght == ptr) {
                // If he's the right child
                ptr->_prnt->_rght = ptr->_left;
            }
            if (ptr->_left) {
                ptr->_left->_prnt = ptr->_prnt;
            }
            delete ptr;
        } else {
            // It has both children, so take the successor
            node_ptr successor = node::minimum(ptr->_rght);
            // If the successor has right child, make it children of his parent
            successor->_prnt->_left = successor->_rght;
            ptr->_data = successor->_data;
            free(successor);
        }
        --_size;
    }

//    V& operator[](const K& key)
//    {
//        return insert(key, V()).first->second;
//    }
//
//    const V& operator[](const K& key) const
//    {
//        return insert(key, V()).first.second;
//    }

private:

    node_ptr   _root;
    size_type  _size;

};

int main()
{
    Dict<int, int> c;

    int read;
    while (true) {
        std::cin >> read;
        if (read < 0) {
            break;
        }
        if (c.find(read) == c.end()) {
            c.insert(read, read);
        }
    }

    std::cin >> read;
    Dict<int, int>::iterator search = c.find(read);
    if (search == c.end()) {
        c.insert(std::make_pair(read, read));
    } else {
        c.erase(search);
    }

    std::cout << c.size() << '\n';

}