Index: uspace/lib/cpp/include/internal/hash_table_iterators.hpp
===================================================================
--- uspace/lib/cpp/include/internal/hash_table_iterators.hpp	(revision 009d78b559c76cf12125cbadc742c32b06331b07)
+++ uspace/lib/cpp/include/internal/hash_table_iterators.hpp	(revision d6bb78b5536af3100d6e7b8a562aeb4737ef4118)
@@ -30,4 +30,5 @@
 #define LIBCPP_INTERNAL_HASH_TABLE_ITERATORS
 
+#include <internal/iterator.hpp>
 #include <internal/list.hpp>
 #include <internal/hash_table_bucket.hpp>
@@ -36,36 +37,36 @@
 namespace std::aux
 {
-    template<class Value, class ConstReference, class ConstPointer, class Size>
-    class hash_table_const_iterator
+    template<class Value, class Reference, class Pointer, class Size>
+    class hash_table_iterator
     {
         public:
             using value_type      = Value;
             using size_type       = Size;
-            using const_reference = ConstReference;
-            using const_pointer   = ConstPointer;
+            using reference       = Reference;
+            using pointer         = Pointer;
             using difference_type = ptrdiff_t;
 
             using iterator_category = forward_iterator_tag;
 
-            hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
-                                      size_type idx = size_type{}, size_type max_idx = size_type{},
-                                      const list_node<value_type>* current = nullptr)
+            hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
+                                size_type idx = size_type{}, size_type max_idx = size_type{},
+                                list_node<value_type>* current = nullptr)
                 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
             { /* DUMMY BODY */ }
 
-            hash_table_const_iterator(const hash_table_const_iterator&) = default;
-            hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default;
-
-            const_reference operator*() const
+            hash_table_iterator(const hash_table_iterator&) = default;
+            hash_table_iterator& operator=(const hash_table_iterator&) = default;
+
+            reference operator*()
             {
                 return current_->value;
             }
 
-            const_pointer operator->() const
+            pointer operator->()
             {
                 return &current_->value;
             }
 
-            hash_table_const_iterator& operator++()
+            hash_table_iterator& operator++()
             {
                 current_ = current_->next;
@@ -89,5 +90,5 @@
             }
 
-            hash_table_const_iterator operator++(int)
+            hash_table_iterator operator++(int)
             {
                 auto tmp = *this;
@@ -99,5 +100,5 @@
             list_node<value_type>* node()
             {
-                return const_cast<list_node<value_type>*>(current_);
+                return current_;
             }
 
@@ -113,56 +114,79 @@
 
         private:
-            const hash_table_bucket<value_type, size_type>* table_;
+            hash_table_bucket<value_type, size_type>* table_;
             size_type idx_;
             size_type max_idx_;
-            const list_node<value_type>* current_;
+            list_node<value_type>* current_;
+
+            template<class V, class CR, class CP, class S>
+            friend class hash_table_const_iterator;
     };
 
-    template<class Value, class ConstRef, class ConstPtr, class Size>
-    bool operator==(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,
-                    const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class ConstRef, class ConstPtr, class Size>
-    bool operator!=(const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& lhs,
-                    const hash_table_const_iterator<Value, ConstRef, ConstPtr, Size>& rhs)
-    {
-        return !(lhs == rhs);
-    }
-
-    template<class Value, class Reference, class Pointer, class Size>
-    class hash_table_iterator
-    {
+    template<class Value, class Ref, class Ptr, class Size>
+    bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
+                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class Ref, class Ptr, class Size>
+    bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
+                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class ConstReference, class ConstPointer, class Size>
+    class hash_table_const_iterator
+    {
+        using non_const_iterator_type = hash_table_iterator<
+            Value, get_non_const_ref_t<ConstReference>,
+            get_non_const_ptr<ConstPointer>, Size
+        >;
+
         public:
             using value_type      = Value;
             using size_type       = Size;
-            using reference       = Reference;
-            using pointer         = Pointer;
+            using const_reference = ConstReference;
+            using const_pointer   = ConstPointer;
             using difference_type = ptrdiff_t;
 
             using iterator_category = forward_iterator_tag;
 
-            hash_table_iterator(hash_table_bucket<value_type, size_type>* table = nullptr,
-                                size_type idx = size_type{}, size_type max_idx = size_type{},
-                                list_node<value_type>* current = nullptr)
+            hash_table_const_iterator(const hash_table_bucket<value_type, size_type>* table = nullptr,
+                                      size_type idx = size_type{}, size_type max_idx = size_type{},
+                                      const list_node<value_type>* current = nullptr)
                 : table_{table}, idx_{idx}, max_idx_{max_idx}, current_{current}
             { /* DUMMY BODY */ }
 
-            hash_table_iterator(const hash_table_iterator&) = default;
-            hash_table_iterator& operator=(const hash_table_iterator&) = default;
-
-            reference operator*()
+            hash_table_const_iterator(const hash_table_const_iterator&) = default;
+            hash_table_const_iterator& operator=(const hash_table_const_iterator&) = default;
+
+            hash_table_const_iterator(const non_const_iterator_type& other)
+                : table_{other.table_}, idx_{other.idx_}, max_idx_{other.max_idx_},
+                  current_{other.current_}
+            { /* DUMMY BODY */ }
+
+            hash_table_const_iterator& operator=(const non_const_iterator_type& other)
+            {
+                table_ = other.table_;
+                idx_ = other.idx_;
+                max_idx_ = other.max_idx_;
+                current_ = other.current_;
+
+                return *this;
+            }
+
+            const_reference operator*() const
             {
                 return current_->value;
             }
 
-            pointer operator->()
+            const_pointer operator->() const
             {
                 return &current_->value;
             }
 
-            hash_table_iterator& operator++()
+            hash_table_const_iterator& operator++()
             {
                 current_ = current_->next;
@@ -186,5 +210,5 @@
             }
 
-            hash_table_iterator operator++(int)
+            hash_table_const_iterator operator++(int)
             {
                 auto tmp = *this;
@@ -196,5 +220,5 @@
             list_node<value_type>* node()
             {
-                return current_;
+                return const_cast<list_node<value_type>*>(current_);
             }
 
@@ -209,31 +233,127 @@
             }
 
-            template<class ConstRef, class ConstPtr>
-            operator hash_table_const_iterator<
-                Value, ConstRef, ConstPtr, Size
-            >() const
-            {
-                return hash_table_const_iterator<value_type, ConstRef, ConstPtr, size_type>{
-                    table_, idx_, max_idx_, current_
-                };
-            }
-
         private:
-            hash_table_bucket<value_type, size_type>* table_;
+            const hash_table_bucket<value_type, size_type>* table_;
             size_type idx_;
             size_type max_idx_;
+            const list_node<value_type>* current_;
+    };
+
+    template<class Value, class CRef, class CPtr, class Size>
+    bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
+                    const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class CRef, class CPtr, class Size>
+    bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
+                    const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size>
+    bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
+                    const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class Ref, class Ptr, class CRef, class CPtr, class Size>
+    bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
+                    const hash_table_const_iterator<Value, CRef, CPtr, Size>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size>
+    bool operator==(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
+                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class CRef, class CPtr, class Ref, class Ptr, class Size>
+    bool operator!=(const hash_table_const_iterator<Value, CRef, CPtr, Size>& lhs,
+                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class Reference, class Pointer>
+    class hash_table_local_iterator
+    {
+        public:
+            using value_type      = Value;
+            using reference       = Reference;
+            using pointer         = Pointer;
+            using difference_type = ptrdiff_t;
+
+            using iterator_category = forward_iterator_tag;
+
+            hash_table_local_iterator(list_node<value_type>* head = nullptr,
+                                      list_node<value_type>* current = nullptr)
+                : head_{head}, current_{current}
+            { /* DUMMY BODY */ }
+
+            hash_table_local_iterator(const hash_table_local_iterator&) = default;
+            hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default;
+
+            reference operator*()
+            {
+                return current_->value;
+            }
+
+            pointer operator->()
+            {
+                return &current_->value;
+            }
+
+            hash_table_local_iterator& operator++()
+            {
+                current_ = current_->next;
+                if (current_ == head_)
+                    current_ = nullptr;
+
+                return *this;
+            }
+
+            hash_table_local_iterator operator++(int)
+            {
+                auto tmp = *this;
+                ++(*this);
+
+                return tmp;
+            }
+
+            list_node<value_type>* node()
+            {
+                return current_;
+            }
+
+            const list_node<value_type>* node() const
+            {
+                return current_;
+            }
+
+        private:
+            list_node<value_type>* head_;
             list_node<value_type>* current_;
+
+            template<class V, class CR, class CP>
+            friend class hash_table_const_local_iterator;
     };
 
-    template<class Value, class Ref, class Ptr, class Size>
-    bool operator==(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
-                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class Ref, class Ptr, class Size>
-    bool operator!=(const hash_table_iterator<Value, Ref, Ptr, Size>& lhs,
-                    const hash_table_iterator<Value, Ref, Ptr, Size>& rhs)
+    template<class Value, class Ref, class Ptr>
+    bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
+                    const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class Ref, class Ptr>
+    bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
+                    const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
     {
         return !(lhs == rhs);
@@ -243,4 +363,9 @@
     class hash_table_const_local_iterator
     {
+        using non_const_iterator_type = hash_table_local_iterator<
+            Value, get_non_const_ref_t<ConstReference>,
+            get_non_const_ptr_t<ConstPointer>
+        >;
+
         public:
             using value_type      = Value;
@@ -260,4 +385,16 @@
             hash_table_const_local_iterator& operator=(const hash_table_const_local_iterator&) = default;
 
+            hash_table_const_local_iterator(const non_const_iterator_type& other)
+                : head_{other.head_}, current_{other.current_}
+            { /* DUMMY BODY */ }
+
+            hash_table_const_local_iterator& operator=(const non_const_iterator_type& other)
+            {
+                head_ = other.head_;
+                current_ = other.current_;
+
+                return *this;
+            }
+
             const_reference operator*() const
             {
@@ -303,91 +440,34 @@
     };
 
-    template<class Value, class ConstRef, class ConstPtr>
-    bool operator==(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,
-                    const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)
-    {
-        return lhs.node() == rhs.node();
-    }
-
-    template<class Value, class ConstRef, class ConstPtr>
-    bool operator!=(const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& lhs,
-                    const hash_table_const_local_iterator<Value, ConstRef, ConstPtr>& rhs)
-    {
-        return !(lhs == rhs);
-    }
-
-    template<class Value, class Reference, class Pointer>
-    class hash_table_local_iterator
-    {
-        public:
-            using value_type      = Value;
-            using reference       = Reference;
-            using pointer         = Pointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = forward_iterator_tag;
-
-            hash_table_local_iterator(list_node<value_type>* head = nullptr,
-                                      list_node<value_type>* current = nullptr)
-                : head_{head}, current_{current}
-            { /* DUMMY BODY */ }
-
-            hash_table_local_iterator(const hash_table_local_iterator&) = default;
-            hash_table_local_iterator& operator=(const hash_table_local_iterator&) = default;
-
-            reference operator*()
-            {
-                return current_->value;
-            }
-
-            pointer operator->()
-            {
-                return &current_->value;
-            }
-
-            hash_table_local_iterator& operator++()
-            {
-                current_ = current_->next;
-                if (current_ == head_)
-                    current_ = nullptr;
-
-                return *this;
-            }
-
-            hash_table_local_iterator operator++(int)
-            {
-                auto tmp = *this;
-                ++(*this);
-
-                return tmp;
-            }
-
-            list_node<value_type>* node()
-            {
-                return current_;
-            }
-
-            const list_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-            template<class ConstRef, class ConstPtr>
-            operator hash_table_const_local_iterator<
-                Value, ConstRef, ConstPtr
-            >() const
-            {
-                return hash_table_const_local_iterator<
-                    value_type, ConstRef, ConstPtr
-                >{head_, current_};
-            }
-
-        private:
-            list_node<value_type>* head_;
-            list_node<value_type>* current_;
-    };
-
-    template<class Value, class Ref, class Ptr>
+    template<class Value, class CRef, class CPtr>
+    bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
+                    const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class CRef, class CPtr>
+    bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
+                    const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class Ref, class Ptr, class CRef, class CPtr>
     bool operator==(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
+                    const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
+    {
+        return lhs.node() == rhs.node();
+    }
+
+    template<class Value, class Ref, class Ptr, class CRef, class CPtr>
+    bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
+                    const hash_table_const_local_iterator<Value, CRef, CPtr>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Value, class CRef, class CPtr, class Ref, class Ptr>
+    bool operator==(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
                     const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
     {
@@ -395,6 +475,6 @@
     }
 
-    template<class Value, class Ref, class Ptr>
-    bool operator!=(const hash_table_local_iterator<Value, Ref, Ptr>& lhs,
+    template<class Value, class CRef, class CPtr, class Ref, class Ptr>
+    bool operator!=(const hash_table_const_local_iterator<Value, CRef, CPtr>& lhs,
                     const hash_table_local_iterator<Value, Ref, Ptr>& rhs)
     {
Index: uspace/lib/cpp/include/internal/iterator.hpp
===================================================================
--- uspace/lib/cpp/include/internal/iterator.hpp	(revision d6bb78b5536af3100d6e7b8a562aeb4737ef4118)
+++ uspace/lib/cpp/include/internal/iterator.hpp	(revision d6bb78b5536af3100d6e7b8a562aeb4737ef4118)
@@ -0,0 +1,69 @@
+/*
+ * Copyright (c) 2018 Jaroslav Jindrak
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ * - Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in the
+ *   documentation and/or other materials provided with the distribution.
+ * - The name of the author may not be used to endorse or promote products
+ *   derived from this software without specific prior written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
+ * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
+ * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
+ * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef LIBCPP_INTERNAL_ITERATOR
+#define LIBCPP_INTERNAL_ITERATOR
+
+#include <internal/aux.hpp>
+
+namespace std::aux
+{
+    /**
+     * Used for our custom iterators where we know
+     * that their references/const_references and
+     * pointers/const_pointers differ only in constness.
+     */
+
+    template<class T>
+    struct get_non_const_ref
+        : type_is<T>
+    { /* DUMMY BODY */ };
+
+    template<class T>
+    struct get_non_const_ref<const T&>
+        : type_is<T&>
+    { /* DUMMY BODY */ };
+
+    template<class T>
+    using get_non_const_ref_t = typename get_non_const_ref<T>::type;
+
+    template<class T>
+    struct get_non_const_ptr
+        : type_is<T>
+    { /* DUMMY BODY */ };
+
+    template<class T>
+    struct get_non_const_ptr<const T*>
+        : type_is<T*>
+    { /* DUMMY BODY */ };
+
+    template<class T>
+    using get_non_const_ptr_t = typename get_non_const_ptr<T>::type;
+}
+
+#endif
Index: uspace/lib/cpp/include/internal/rbtree_iterators.hpp
===================================================================
--- uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision 009d78b559c76cf12125cbadc742c32b06331b07)
+++ uspace/lib/cpp/include/internal/rbtree_iterators.hpp	(revision d6bb78b5536af3100d6e7b8a562aeb4737ef4118)
@@ -30,4 +30,5 @@
 #define LIBCPP_INTERNAL_RBTREE_ITERATORS
 
+#include <internal/iterator.hpp>
 #include <internal/rbtree_node.hpp>
 #include <iterator>
@@ -44,7 +45,178 @@
      */
 
+    template<class Value, class Reference, class Pointer, class Size>
+    class rbtree_iterator
+    {
+        public:
+            using value_type      = Value;
+            using size_type       = Size;
+            using reference       = Reference;
+            using pointer         = Pointer;
+            using difference_type = ptrdiff_t;
+
+            using iterator_category = bidirectional_iterator_tag;
+
+            rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
+                : current_{current}, end_{end}
+            { /* DUMMY BODY */ }
+
+            rbtree_iterator(const rbtree_iterator&) = default;
+            rbtree_iterator& operator=(const rbtree_iterator&) = default;
+
+            reference operator*() const
+            {
+                return current_->value;
+            }
+
+            pointer operator->() const
+            {
+                return &current_->value;
+            }
+
+            rbtree_iterator& operator++()
+            {
+                if (current_)
+                {
+                    auto bckp = current_;
+                    if (current_->right)
+                        current_ = current_->right->find_smallest();
+                    else
+                    {
+                        while (!current_->is_left_child())
+                        {
+                            current_ = current_->parent;
+
+                            if (!current_ || !current_->parent)
+                            {
+                                /**
+                                 * We've gone back to root without
+                                 * being a left child, which means we
+                                 * were the last node.
+                                 */
+                                end_ = true;
+                                current_ = bckp;
+
+                                return *this;
+                            }
+                        }
+
+                        /**
+                         * Now we are a left child,
+                         * so the next node we have to visit
+                         * is our parent.
+                         */
+                        current_ = current_->parent;
+                    }
+                }
+
+                return *this;
+            }
+
+            rbtree_iterator operator++(int)
+            {
+                auto tmp = *this;
+                ++(*this);
+
+                return tmp;
+            }
+
+            rbtree_iterator& operator--()
+            {
+                if (end_)
+                {
+                    try_undo_end_();
+
+                    return *this;
+                }
+
+                if (current_)
+                {
+                    if (current_->left)
+                        current_ = current_->left->find_largest();
+                    else if (current_->parent)
+                    {
+                        while (current_->is_left_child())
+                            current_ = current_->parent;
+
+                        /**
+                         * We know parent exists here
+                         * because we went up from the
+                         * left and stopped being left
+                         * child (if at any point we happened
+                         * to become root then this branch
+                         * wouldn't happen).
+                         */
+                        current_ = current_->parent;
+                    }
+                    else // We are root without a left child.
+                        end_ = true;
+                }
+
+                return *this;
+            }
+
+            rbtree_iterator operator--(int)
+            {
+                auto tmp = *this;
+                --(*this);
+
+                return tmp;
+            }
+
+            const rbtree_node<value_type>* node() const
+            {
+                return current_;
+            }
+
+            rbtree_node<value_type>* node()
+            {
+                return current_;
+            }
+
+            bool end() const
+            {
+                return end_;
+            }
+
+        private:
+            rbtree_node<value_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;
+            }
+    };
+
+    template<class Val, class Ref, class Ptr, class Sz>
+    bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    {
+        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
+    }
+
+    template<class Val, class Ref, class Ptr, class Sz>
+    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
+                    const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
     template<class Value, class ConstReference, class ConstPointer, class Size>
     class rbtree_const_iterator
     {
+        using non_const_iterator_type = rbtree_iterator<
+            Value, get_non_const_ref_t<ConstReference>,
+            get_non_const_ptr_t<ConstPointer>, Size
+        >;
+
         public:
             using value_type      = Value;
@@ -62,4 +234,16 @@
             rbtree_const_iterator(const rbtree_const_iterator&) = default;
             rbtree_const_iterator& operator=(const rbtree_const_iterator&) = default;
+
+            rbtree_const_iterator(const non_const_iterator_type& other)
+                : current_{other.node()}, end_{other.end()}
+            { /* DUMMY BODY */ }
+
+            rbtree_const_iterator& operator=(const non_const_iterator_type& other)
+            {
+                current_ = other.node();
+                end_ = other.end();
+
+                return *this;
+            }
 
             const_reference operator*() const
@@ -205,158 +389,20 @@
     }
 
-    template<class Value, class Reference, class Pointer, class Size>
-    class rbtree_iterator
-    {
-        public:
-            using value_type      = Value;
-            using size_type       = Size;
-            using reference       = Reference;
-            using pointer         = Pointer;
-            using difference_type = ptrdiff_t;
-
-            using iterator_category = bidirectional_iterator_tag;
-
-            rbtree_iterator(rbtree_node<value_type>* current = nullptr, bool end = true)
-                : current_{current}, end_{end}
-            { /* DUMMY BODY */ }
-
-            rbtree_iterator(const rbtree_iterator&) = default;
-            rbtree_iterator& operator=(const rbtree_iterator&) = default;
-
-            reference operator*() const
-            {
-                return current_->value;
-            }
-
-            pointer operator->() const
-            {
-                return &current_->value;
-            }
-
-            rbtree_iterator& operator++()
-            {
-                if (current_)
-                {
-                    auto bckp = current_;
-                    if (current_->right)
-                        current_ = current_->right->find_smallest();
-                    else
-                    {
-                        while (!current_->is_left_child())
-                        {
-                            current_ = current_->parent;
-
-                            if (!current_ || !current_->parent)
-                            {
-                                /**
-                                 * We've gone back to root without
-                                 * being a left child, which means we
-                                 * were the last node.
-                                 */
-                                end_ = true;
-                                current_ = bckp;
-
-                                return *this;
-                            }
-                        }
-
-                        /**
-                         * Now we are a left child,
-                         * so the next node we have to visit
-                         * is our parent.
-                         */
-                        current_ = current_->parent;
-                    }
-                }
-
-                return *this;
-            }
-
-            rbtree_iterator operator++(int)
-            {
-                auto tmp = *this;
-                ++(*this);
-
-                return tmp;
-            }
-
-            rbtree_iterator& operator--()
-            {
-                if (end_)
-                {
-                    try_undo_end_();
-
-                    return *this;
-                }
-
-                if (current_)
-                {
-                    if (current_->left)
-                        current_ = current_->left->find_largest();
-                    else if (current_->parent)
-                    {
-                        while (current_->is_left_child())
-                            current_ = current_->parent;
-
-                        /**
-                         * We know parent exists here
-                         * because we went up from the
-                         * left and stopped being left
-                         * child (if at any point we happened
-                         * to become root then this branch
-                         * wouldn't happen).
-                         */
-                        current_ = current_->parent;
-                    }
-                    else // We are root without a left child.
-                        end_ = true;
-                }
-
-                return *this;
-            }
-
-            rbtree_iterator operator--(int)
-            {
-                auto tmp = *this;
-                --(*this);
-
-                return tmp;
-            }
-
-            const rbtree_node<value_type>* node() const
-            {
-                return current_;
-            }
-
-            rbtree_node<value_type>* node()
-            {
-                return current_;
-            }
-
-            bool end() const
-            {
-                return end_;
-            }
-
-        private:
-            rbtree_node<value_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;
-            }
-    };
-
-    template<class Val, class Ref, class Ptr, class Sz>
+    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
     bool operator==(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    {
+        return (lhs.node() == rhs.node()) && (lhs.end() == rhs.end());
+    }
+
+    template<class Val, class Ref, class Ptr, class CRef, class CPtr, class Sz>
+    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
+                    const rbtree_const_iterator<Val, CRef, CPtr, Sz>& rhs)
+    {
+        return !(lhs == rhs);
+    }
+
+    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
+    bool operator==(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     {
@@ -364,6 +410,6 @@
     }
 
-    template<class Val, class Ref, class Ptr, class Sz>
-    bool operator!=(const rbtree_iterator<Val, Ref, Ptr, Sz>& lhs,
+    template<class Val, class CRef, class CPtr, class Ref, class Ptr, class Sz>
+    bool operator!=(const rbtree_const_iterator<Val, CRef, CPtr, Sz>& lhs,
                     const rbtree_iterator<Val, Ref, Ptr, Sz>& rhs)
     {