Listing 2: The Non-Const Iterator Class

/**
 * The non-const linked hash iterator.
 */
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
struct _linked_hash_iterator {
   typedef linked_hash<Key,Data,HashFcn,EqualKey,Alloc> _Hash_Map;
   typedef _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc> iterator;
   typedef _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>
		 const_iterator;
   typedef _linked_hash_node<Key, Data, HashFcn, EqualKey, Alloc> _Node;

   typedef forward_iterator_tag iterator_category;
   typedef pair<Key, Data> value_type;
   typedef ptrdiff_t difference_type;
   typedef size_t size_type;
   typedef value_type& reference;
   typedef value_type* pointer;

   // A pointer to the node referenced by this iterator
   _Node* _current;

   // Constructor
   _linked_hash_iterator(_Node* __n) 
      : _current(__n) {}

   // Default constructor, creates an iterator with a NULL node.
   // Equivalent to calling linked_hash::end()
   _linked_hash_iterator() : _current(NULL) {}

   // Returns a reference to the underlying data value from the node.
   reference operator*() const { return _current->_val; }

   // Returns a pointer to the underlying data value from the node.
   pointer operator->() const { return &(operator*()); }

   // Increment operators.  Implemented separately below.
   iterator& operator++();
   iterator operator++(int);

   // Comparison operators.
   bool operator==(const iterator& __it) const
   { return _current == __it._current; }
   bool operator!=(const iterator& __it) const
   { return _current != __it._current; }
};

// Post-increment operator for non-const iterators
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
inline _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>&
_linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++() {
   typename _Node::_List::iterator __i = _current->_li;
   _current = *(++__i);
   return *this;
}

// Pre-increment operator for non-const iterators
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
inline _linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>
_linked_hash_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++(int) {
   iterator __tmp = *this;
   ++*this;
   return __tmp;
}

// Post-increment operator for const iterators
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
inline _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>&
_linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++() {
   typename _Node::_List::iterator __i = _current->_li;
   _current = *(++__i);
   return *this;
}

// Pre-increment operator for const iterators
template <class Key, class Data, class HashFcn, class EqualKey, class Alloc>
inline _linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>
_linked_hash_const_iterator<Key, Data, HashFcn, EqualKey, Alloc>::operator++(int) {
   iterator __tmp = *this;
   ++*this;
   return __tmp;
}
