Const iterators

There's just one more complication to consider, before we abandon this list iterator example. Notice that I quietly changed our count_if function template so that it takes Container& instead of const Container&! That's because the begin() and end() member functions we provided are non-const member functions; and that's because they return iterators whose operator* returns non-const references to the elements of the list. We'd like to make our list type (and its iterators) completely const-correct--that is, we'd like you to be able to define and use variables of type const list_of_ints, but prevent you from modifying the elements of a const list.

The standard library generally deals with this issue by giving each standard container two different kinds of iterator: bag::iterator and bag::const_iterator. The non-const member function bag::begin() returns an iterator and the bag::begin() const member function returns a const_iterator. The underscore is all-important! Notice that bag::begin() const does not return a mere const iterator; if the returned object were const, we wouldn't be allowed to ++ it. (Which, in turn, would make it darn difficult to iterate over a const bag!) No, bag::begin() const returns something more subtle: a non-const const_iterator object whose operator* simply happens to yield a const reference to its element.

Maybe an example would help. Let's go ahead and implement const_iterator for our list_of_ints container.

Since most of the code for the const_iterator type is going to be exactly the same as the code for the iterator type, our first instinct might be to cut and paste. But this is C++! When I say "most of this code is going to be exactly the same as this other code," you should be thinking "let's make the common parts into a template." And indeed, that's what we'll do:

    struct list_node {
      int data;
      list_node *next;
    };

    template<bool Const>
    class list_of_ints_iterator {
      friend class list_of_ints;
      friend class list_of_ints_iterator<!Const>;

      using node_pointer = std::conditional_t<Const, const list_node*, list_node*>;
      using reference = std::conditional_t<Const, const int&, int&>;

      node_pointer ptr_;

      explicit list_of_ints_iterator(node_pointer p) : ptr_(p) {}
    public:
      reference operator*() const { return ptr_->data; }
      auto& operator++() { ptr_ = ptr_->next; return *this; }
      auto operator++(int) { auto result = *this; ++*this; return result; }

      // Support comparison between iterator and const_iterator types
      template<bool R>
      bool operator==(const list_of_ints_iterator<R>& rhs) const
        { return ptr_ == rhs.ptr_; }

      template<bool R>
      bool operator!=(const list_of_ints_iterator<R>& rhs) const
        { return ptr_ != rhs.ptr_; }

      // Support implicit conversion of iterator to const_iterator
      // (but not vice versa)
      operator list_of_ints_iterator<true>() const
        { return list_of_ints_iterator<true>{ptr_}; }
    };

    class list_of_ints {
      list_node *head_ = nullptr;
      list_node *tail_ = nullptr;
      // ...
    public:
      using const_iterator = list_of_ints_iterator<true>;
      using iterator = list_of_ints_iterator<false>;

      iterator begin() { return iterator{head_}; }
      iterator end() { return iterator{nullptr}; }
      const_iterator begin() const { return const_iterator{head_}; }
      const_iterator end() const { return const_iterator{nullptr}; }
    };

The preceding code implements fully const-correct iterator types for our list_of_ints.