The Standard Librarian : Defining Iterators and Const Iterators

Listing 2: A complete implementation of Slist_iterator and a partial implementation of an Slist container

template <class T> struct slist_node {
   T val;
   slist_node* next;
   slist_node(const T& t, slist_node* p) 
      : val(t), next(p) { }
};

template <bool flag, class IsTrue, class IsFalse>
struct choose;

template <class IsTrue, class IsFalse>
struct choose<true, IsTrue, IsFalse> {
   typedef IsTrue type;
};

template <class IsTrue, class IsFalse>
struct choose<false, IsTrue, IsFalse> {
   typedef IsFalse type;
};

template <class T, bool isconst = false> 
struct slist_iterator {
   typedef std::forward_iterator_tag iterator_category;
   typedef T value_type;
   typedef std::ptrdiff_t difference_type;
   typedef typename choose<isconst, const T&, T&>::type
           reference;
   typedef typename choose<isconst, const T*, T*>::type
           pointer;

   typedef typename choose<isconst, const slist_node<T>*,    
                           slist_node<T>*>::type
           nodeptr;

   slist_iterator(nodeptr x = 0) : p(x) { }
   slist_iterator(const slist_iterator<T, false>& i) 
      : p(i.p) { }
   reference operator*() const { return p->val; }
   pointer operator->() const { return &(p->val); }
   slist_iterator& operator++() { 
      p = p->next; 
      return *this; 
   }
   slist_iterator operator++(int) {
      slist_iterator tmp(*this);
      ++*this;
      return tmp;
   }

   friend bool operator==(const slist_iterator& x,
                          const slist_iterator& y) {
      return x.p == y.p;
   }

   friend bool operator!=(const slist_iterator& x,
                          const slist_iterator& y) {
      return x.p != y.p;
   }

   nodeptr p;
};

// This is not a complete container class.  It is just
// enough to illustrate defining and using an iterator/ 
// const iterator pair.
template <class T> struct slist {
   slist_node<T>* head;

   typedef slist_iterator<T>       iterator;
   typedef slist_iterator<T, true> const_iterator;

   iterator begin() { return iterator(head); }
   iterator end()   { return iterator(0); }
   const_iterator begin() const { 
      return const_iterator(head); 
   }
   const_iterator end() const {
      return const_iterator(0); 
   }

   slist() : head(0) { }
   ~slist() {
       while (head) {
          slist_node<T>* next = head->next;
          delete head;
          head = next;
       }
   }

   void push_front(const T& t) {
      head = new slist_node<T>(t, head);
   }

   ...
};
— End of Listing —