On beyond pointers

In the absence of any abstraction, how does one normally identify an element of an array, an element of a linked list, or an element of a tree? The most straightforward way would be to use a pointer to the element's address in memory. Here are some examples of pointers to elements of various data structures:

To iterate over an array, all we need is that pointer; we can handle all the elements in the array by starting with a pointer to the first element and simply incrementing that pointer until it reaches the last element. In C:

    for (node *p = lst.head_; p != nullptr; p = p->next) {
      if (pred(p->data)) {
        sum += 1;
      }
   }

But in order to efficiently iterate over a linked list, we need more than just a raw pointer; incrementing a pointer of type node* is highly unlikely to produce a pointer to the next node in the list! In that case, we need something that acts like a pointer--in particular, we should be able to dereference it to retrieve or modify the pointed-to element--but has special, container-specific behavior associated with the abstract concept of incrementing.

In C++, given that we have operator overloading built into the language, when I say "associate special behavior with the concept of incrementing", you should be thinking "let's overload the ++ operator." And indeed, that's what we'll do:

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

    class list_of_ints_iterator {
      list_node *ptr_;

      friend class list_of_ints;
      explicit list_of_ints_iterator(list_node *p) : ptr_(p) {}
    public:
      int& operator*() const { return ptr_->data; }
      list_of_ints_iterator& operator++() { ptr_ = ptr_->next; return *this; }
      list_of_ints_iterator operator++(int) { auto it = *this; ++*this; return it; }
      bool operator==(const list_of_ints_iterator& rhs) const
        { return ptr_ == rhs.ptr_; }
      bool operator!=(const list_of_ints_iterator& rhs) const
        { return ptr_ != rhs.ptr_; }
    };

    class list_of_ints {
      list_node *head_ = nullptr;
      list_node *tail_ = nullptr;
      // ...
    public:
      using iterator = list_of_ints_iterator;
      iterator begin() { return iterator{head_}; }
      iterator end() { return iterator{nullptr}; }
    }; 

    template<class Container, class Predicate>
    int count_if(Container& ctr, Predicate pred)
    {
      int sum = 0;
      for (auto it = ctr.begin(); it != ctr.end(); ++it) {
        if (pred(*it)) {
            sum += 1;
        }
      }
      return sum;
   }

Notice that we also overload the unary * operator (for dereferencing) and the == and != operators; our count_if template requires all of these operations be valid for the loop control variable it. (Well, okay, technically our count_if doesn't require the == operation; but if you're going to overload one of the comparison operators, you should overload the other as well.)