Class iterator

tests/clio/database.cpp:457–508

   }

   struct iterator
   {
      iterator() {}
      const T& operator*() const { return pos->value(); }
      iterator& operator++()
      {
         if (not pos)
            return *this;
         // std::cout << "start: " << **this << "\n";

         auto& right = pos->right();
         if (right)
         {
            pos = right;
            //   std::cout << "    go right to: " << **this << "\n";
            while (auto& left = pos->left())
            {
               pos = left;
               //      std::cout << "        go left to: " << **this << "\n";
            }
         }
         else
         {
            // std::cout << "    go to parent while parent right != me\n";
            while (auto& parent = pos->parent())
            {
               if (parent->right() == pos)
               {
                  pos = parent;
                  //        std::cout << "        go to next parent: " << **this << "\n";
               }
               else
               {
                  //       std::cout << "        go to parent: " << **this << "\n";
                  pos = parent;
                  return *this;
               }
            }
            //    std::cout << "    no more parents!  We are done\n";
            pos = node_cptr();
         }
         return *this;
      }

      friend bool operator==(const iterator& a, const iterator& b) { return a.pos == b.pos; }
      friend bool operator!=(const iterator& a, const iterator& b) { return a.pos != b.pos; }

     private:
      friend class tree_cache;
      iterator(const node_cptr& p) : pos(p) {}
      node_cptr pos;
   };

   iterator lower_bound(const T& v) const { return lower_bound(v, root()); }
   iterator end() const { return iterator(node_cptr()); }