Index: uspace/lib/cpp/include/impl/map.hpp
===================================================================
--- uspace/lib/cpp/include/impl/map.hpp	(revision 5608106c60f61777212f26773b0e9578436cb37c)
+++ uspace/lib/cpp/include/impl/map.hpp	(revision 21d97e85380f9ea131a025873e8863f6b9d26060)
@@ -63,9 +63,11 @@
             using difference_type = ptrdiff_t;
 
+            using node_type = aux::rbtree_single_node<value_type>;
+
             using iterator             = aux::rbtree_iterator<
-                value_type, reference, pointer, size_type
+                value_type, reference, pointer, size_type, node_type
             >;
             using const_iterator       = aux::rbtree_const_iterator<
-                value_type, const_reference, const_pointer, size_type
+                value_type, const_reference, const_pointer, size_type, node_type
             >;
 
@@ -338,5 +340,7 @@
             template<class T>
             pair<iterator, bool> insert(
-                enable_if_t<is_constructible_v<value_type, T&&>, T&&> val)
+                T&& val,
+                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
+            )
             {
                 return emplace(forward<T>(val));
@@ -356,5 +360,6 @@
             iterator insert(
                 const_iterator hint,
-                enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
+                T&& val,
+                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
             )
             {
@@ -422,5 +427,5 @@
                 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
                 {
-                    parent->value = value_type{key, forward<T>(val)};
+                    parent->value.second = forward<T>(val);
 
                     return make_pair(iterator{parent, false}, false);
@@ -441,5 +446,5 @@
                 if (parent && tree_.keys_equal(tree_.get_key(parent->value), key))
                 {
-                    parent->value = value_type{move(key), forward<T>(val)};
+                    parent->value.second = forward<T>(val);
 
                     return make_pair(iterator{parent, false}, false);
@@ -521,5 +526,6 @@
             template<class K>
             iterator find(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -529,5 +535,6 @@
             template<class K>
             const_iterator find(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -542,5 +549,6 @@
             template<class K>
             size_type count(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -560,5 +568,6 @@
             template<class K>
             iterator lower_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -568,5 +577,6 @@
             template<class K>
             const_iterator lower_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -586,5 +596,6 @@
             template<class K>
             iterator upper_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -594,5 +605,6 @@
             template<class K>
             const_iterator upper_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -612,5 +624,6 @@
             template<class K>
             pair<iterator, iterator> equal_range(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -620,5 +633,6 @@
             template<class K>
             pair<const_iterator, const_iterator> equal_range(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -631,8 +645,6 @@
                 key_compare, allocator_type, size_type,
                 iterator, const_iterator,
-                aux::rbtree_single_policy
+                aux::rbtree_single_policy, node_type
             >;
-
-            using node_type = typename tree_type::node_type;
 
             tree_type tree_;
@@ -714,4 +726,6 @@
             using difference_type = ptrdiff_t;
 
+            using node_type = aux::rbtree_multi_node<value_type>;
+
             class value_compare
             {
@@ -737,8 +751,8 @@
 
             using iterator             = aux::rbtree_iterator<
-                value_type, reference, pointer, size_type
+                value_type, reference, pointer, size_type, node_type
             >;
             using const_iterator       = aux::rbtree_const_iterator<
-                value_type, const_reference, const_pointer, size_type
+                value_type, const_reference, const_pointer, size_type, node_type
             >;
 
@@ -937,5 +951,6 @@
             template<class T>
             iterator insert(
-                enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
+                T&& val,
+                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
             )
             {
@@ -956,5 +971,6 @@
             iterator insert(
                 const_iterator hint,
-                enable_if_t<is_constructible_v<value_type, T&&>, T&&> val
+                T&& val,
+                enable_if_t<is_constructible_v<value_type, T&&>>* = nullptr
             )
             {
@@ -1029,5 +1045,6 @@
             template<class K>
             iterator find(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -1037,5 +1054,6 @@
             template<class K>
             const_iterator find(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -1050,5 +1068,6 @@
             template<class K>
             size_type count(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -1068,5 +1087,6 @@
             template<class K>
             iterator lower_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -1076,5 +1096,6 @@
             template<class K>
             const_iterator lower_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -1094,5 +1115,6 @@
             template<class K>
             iterator upper_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -1102,5 +1124,6 @@
             template<class K>
             const_iterator upper_bound(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -1120,5 +1143,6 @@
             template<class K>
             pair<iterator, iterator> equal_range(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             )
             {
@@ -1128,5 +1152,6 @@
             template<class K>
             pair<const_iterator, const_iterator> equal_range(
-                enable_if_t<aux::is_transparent_v<key_compare>, const K&> key
+                const K& key,
+                enable_if_t<aux::is_transparent_v<key_compare>, K>* = nullptr
             ) const
             {
@@ -1139,5 +1164,5 @@
                 key_compare, allocator_type, size_type,
                 iterator, const_iterator,
-                aux::rbtree_multi_policy
+                aux::rbtree_multi_policy, node_type
             >;
 
Index: uspace/lib/cpp/include/internal/rbtree.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree.hpp	(revision 5608106c60f61777212f26773b0e9578436cb37c)
+++ uspace/lib/cpp/include/internal/rbtree.hpp	(revision 21d97e85380f9ea131a025873e8863f6b9d26060)
@@ -353,4 +353,8 @@
                 if (!node)
                     return nullptr;
+
+                --size_;
+
+                auto succ = node->successor();
                 if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
                 {
@@ -359,23 +363,20 @@
                      * we popped one node from a list of nodes
                      * with equivalent keys and we can delete it
-                     * and return the original as it is still
-                     * in place.
+                     * and return the successor which was the next
+                     * in the list.
                      */
                     delete tmp;
 
-                    return node;
-                }
-
-                --size_;
-
-                if (node == root_)
-                {
+                    update_root_(succ); // Incase the first in list was root.
+                    return succ;
+                }
+                else if (node == root_)
+                { // Only executed if root_ is unique.
+                    root_ = nullptr;
                     delete node;
-                    root_ = nullptr;
 
                     return nullptr;
                 }
 
-                auto succ = node->successor();
                 if (node->left() && node->right())
                 {
@@ -407,4 +408,7 @@
                     else if (node->is_right_child())
                         child->parent()->right(child);
+                    node->parent(nullptr);
+                    node->left(nullptr);
+                    node->right(nullptr);
 
                     // Repair if needed.
Index: uspace/lib/cpp/include/internal/rbtree_iterators.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision 5608106c60f61777212f26773b0e9578436cb37c)
+++ uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision 21d97e85380f9ea131a025873e8863f6b9d26060)
@@ -78,4 +78,7 @@
             rbtree_iterator& operator++()
             {
+                if (end_)
+                    return *this;
+
                 if (current_)
                 {
@@ -102,5 +105,5 @@
                 if (end_)
                 {
-                    try_undo_end_();
+                    end_ = false;
 
                     return *this;
@@ -145,17 +148,4 @@
             node_type* current_;
             bool end_;
-
-            void try_undo_end_()
-            {
-                if (!current_)
-                    return;
-
-                /**
-                 * We can do this if we are past end().
-                 * This means we are the largest.
-                 */
-                if (current_->find_largest() == current_)
-                    end_ = false;
-            }
     };
 
@@ -224,4 +214,7 @@
             rbtree_const_iterator& operator++()
             {
+                if (end_)
+                    return *this;
+
                 if (current_)
                 {
@@ -248,5 +241,5 @@
                 if (end_)
                 {
-                    try_undo_end_();
+                    end_ = false;
 
                     return *this;
@@ -286,17 +279,4 @@
             const node_type* current_;
             bool end_;
-
-            void try_undo_end_()
-            {
-                if (!current_)
-                    return;
-
-                /**
-                 * We can do this if we are past end().
-                 * This means we are the largest.
-                 */
-                if (current_->find_largest() == current_)
-                    end_ = false;
-            }
     };
 
Index: uspace/lib/cpp/include/internal/rbtree_node.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_node.hpp	(revision 5608106c60f61777212f26773b0e9578436cb37c)
+++ uspace/lib/cpp/include/internal/rbtree_node.hpp	(revision 21d97e85380f9ea131a025873e8863f6b9d26060)
@@ -46,5 +46,5 @@
         {
             if (node && node->parent())
-                return node->parent->parent();
+                return node->parent()->parent();
             else
                 return nullptr;
@@ -55,8 +55,8 @@
             if (node && node->parent())
             {
-                if (node == node->parent->left())
-                    return node->parent->right();
-                else
-                    return node->parent->left();
+                if (node == node->parent()->left())
+                    return node->parent()->right();
+                else
+                    return node->parent()->left();
             }
             else
@@ -573,5 +573,26 @@
             const rbtree_multi_node* predecessor() const
             {
-                return utils::predecessor(this);
+                if (this != first_)
+                {
+                    auto tmp = first_;
+                    while (tmp->next_ != this)
+                        tmp = tmp->next_;
+
+                    return tmp;
+                }
+                else
+                {
+                    auto tmp = utils::predecessor(this);
+
+                    /**
+                     * If tmp was duplicate, we got a pointer
+                     * to the first node in the list. So we need
+                     * to move to the end.
+                     */
+                    while (tmp->next_ != nullptr)
+                        tmp = tmp->next_;
+
+                    return tmp;
+                }
             }
 
@@ -591,13 +612,49 @@
             }
 
-            rbtree_multi_node<T>* get_node_for_deletion()
-            {
+            rbtree_multi_node* get_node_for_deletion()
+            {
+                /**
+                 * To make sure we delete nodes in
+                 * the order of their insertion
+                 * (not required, but sensical), we
+                 * update then list and return this
+                 * for deletion.
+                 */
                 if (next_)
                 {
-                    auto tmp = next_;
-                    while (tmp && tmp->next_ != this)
+                    // Make next the new this.
+                    next_->first_ = next_;
+                    if (is_left_child())
+                        parent_->left_ = next_;
+                    else if (is_right_child())
+                        parent_->right_ = next_;
+
+                    if (left_)
+                        left_->parent_ = next_;
+                    if (right_)
+                        right_->parent_ = next_;
+
+                    /**
+                     * Update the first_ pointer
+                     * of the rest of the list.
+                     */
+                    auto tmp = next_->next_;
+                    while (tmp)
+                    {
+                        tmp->first_ = next_;
                         tmp = tmp->next_;
-
-                    return tmp; // This will get deleted.
+                    }
+
+                    /**
+                     * Otherwise destructor could
+                     * destroy them.
+                     */
+                    parent_ = nullptr;
+                    left_ = nullptr;
+                    right_ = nullptr;
+                    next_ = nullptr;
+                    first_ = nullptr;
+
+                    return this; // This will get deleted.
                 }
                 else
@@ -608,7 +665,7 @@
             {
                 if (is_left_child())
-                    parent->left_ = nullptr;
+                    parent_->left_ = nullptr;
                 else if (is_right_child())
-                    parent->right_ = nullptr;
+                    parent_->right_ = nullptr;
             }
 
Index: uspace/lib/cpp/include/internal/rbtree_policies.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 5608106c60f61777212f26773b0e9578436cb37c)
+++ uspace/lib/cpp/include/internal/rbtree_policies.hpp	(revision 21d97e85380f9ea131a025873e8863f6b9d26060)
@@ -277,5 +277,5 @@
 
             size_type res{};
-            while (tree.keys_equal(tree.get_key(*it), key))
+            while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
             {
                 ++res;
@@ -291,5 +291,7 @@
             auto it = lower_bound_const(tree, key);
 
-            return typename Tree::iterator{it.node(), it.end()};
+            return typename Tree::iterator{
+                const_cast<typename Tree::node_type*>(it.node()), it.end()
+            };
         }
 
@@ -328,5 +330,7 @@
             auto it = upper_bound_const(tree, key);
 
-            return typename Tree::iterator{it.node(), it.end()};
+            return typename Tree::iterator{
+                const_cast<typename Tree::node_type*>(it.node()), it.end()
+            };
         }