Index: uspace/lib/cpp/include/internal/rbtree.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree.hpp	(revision f8bbaa083cba7c3130b4f8c68cf7327222ae3a88)
+++ uspace/lib/cpp/include/internal/rbtree.hpp	(revision 009d78b559c76cf12125cbadc742c32b06331b07)
@@ -61,4 +61,8 @@
             using node_type = rbtree_node<value_type>;
 
+            // TODO: make find/bounds etc templated with key type
+            //       for transparent comparators and leave their management for the
+            //       outer containers
+
             rbtree(const key_compare& kcmp = key_compare{})
                 : root_{nullptr}, size_{}, key_compare_{},
@@ -66,5 +70,10 @@
             { /* DUMMY BODY */ }
 
-            rbtree(const rbtree& other); // TODO:
+            rbtree(const rbtree& other)
+                : rbtree{other.key_compare_}
+            {
+                for (const auto& x: other)
+                    insert(x);
+            }
 
             rbtree(rbtree&& other)
@@ -172,4 +181,10 @@
             {
                 auto ret = Policy::emplace(*this, forward<Args>(args)...);
+                if (!ret.second)
+                    return ret;
+                ++size_;
+
+                repair_after_insert_(ret.first.node());
+                update_root_(ret.first.node());
 
                 return ret;
@@ -181,4 +196,5 @@
                 if (!ret.second)
                     return ret;
+                ++size_;
 
                 repair_after_insert_(ret.first.node());
@@ -193,4 +209,5 @@
                 if (!ret.second)
                     return ret;
+                ++size_;
 
                 repair_after_insert_(ret.first.node());
@@ -202,16 +219,17 @@
             size_type erase(const key_type& key)
             {
-                auto ret = Policy::erase(*this, key);
-                if (ret == 0)
-                    return ret;
-                // TODO: problem - we don't have a node ptr
-                //       solution: return a pair<size_type, node_type*>
-
-                return ret;
+                return Policy::erase(*this, key);
             }
 
             iterator erase(const_iterator it)
             {
-                // TODO: implement
+                if (it == cend())
+                    return end();
+
+                auto node = const_cast<node_type*>(it.node());
+                ++it;
+
+                delete_node(node);
+                return iterator{const_cast<node_type*>(it.node()), it.end()};
             }
 
@@ -296,6 +314,14 @@
             bool is_eq_to(const rbtree& other) const
             {
-                // TODO: implement
-                return false;
+                if (size_ != other.size())
+                    return false;
+
+                auto it1 = begin();
+                auto it2 = other.begin();
+
+                while (keys_equal(*it1++, *it2++))
+                { /* DUMMY BODY */ }
+
+                return (it1 == end()) && (it2 == other.end());
             }
 
@@ -308,4 +334,9 @@
             {
                 return key_compare_(key, key_extractor_(val));
+            }
+
+            bool keys_equal(const key_type& k1, const key_type& k2) const
+            {
+                return !key_compare_(k1, k2) && !key_compare_(k2, k1);
             }
 
@@ -327,4 +358,44 @@
             }
 
+            void delete_node(node_type* node)
+            {
+                if (!node)
+                    return;
+
+                --size_;
+
+                if (node->left && node->right)
+                {
+                    node->swap(node->successor());
+
+                    // Node now has at most one child.
+                    delete_node(node);
+
+                    return;
+                }
+
+                auto child = node->right ? node->right : node->left;
+                if (!child)
+                {
+                    // Simply remove the node.
+                    node->unlink();
+
+                    delete node;
+                }
+                else
+                {
+                    // Replace with the child.
+                    child->parent = node->parent;
+                    if (node->is_left_child())
+                        child->parent->left = child;
+                    else if (node->is_left_child())
+                        child->parent->right = child;
+
+                    // Repair if needed.
+                    repair_after_erase_(node, child);
+                    update_root_(child);
+                }
+            }
+
         private:
             node_type* root_;
@@ -340,8 +411,8 @@
                     if (key_compare_(key, key_extractor_(current->value)))
                         current = current->left;
-                    else if (key == key_extractor_(current->value))
+                    else if (key_compare_(key_extractor_(current->value), key))
+                        current = current->right;
+                    else
                         return current;
-                    else
-                        current = current->right;
                 }
 
@@ -380,5 +451,5 @@
             }
 
-            void repair_after_erase_(node_type* node)
+            void repair_after_erase_(node_type* node, node_type* child)
             {
                 // TODO: implement