Putting it all together

Putting together everything we've learned in this chapter, we can now write code like the following example. In this example, we're implementing our own list_of_ints with our own iterator class (including a const-correct const_iterator version); and we're enabling it to work with the standard library by providing the five all-important member typedefs.

    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*>;
      node_pointer ptr_;

      explicit list_of_ints_iterator(node_pointer p) : ptr_(p) {}
    public:
      // Member typedefs required by std::iterator_traits
      using difference_type = std::ptrdiff_t;
      using value_type = int;
      using pointer = std::conditional_t<Const, const int*, int*>;
      using reference = std::conditional_t<Const, const int&, int&>;
      using iterator_category = std::forward_iterator_tag;

      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;
      int size_ = 0;
    public:
      using const_iterator = list_of_ints_iterator<true>;
      using iterator = list_of_ints_iterator<false>;

      // Begin and end member functions
      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}; }

      // Other member operations
      int size() const { return size_; }
      void push_back(int value) {
        list_node *new_tail = new list_node{value, nullptr};
        if (tail_) {
          tail_->next = new_tail;
        } else {
          head_ = new_tail;
        }
        tail_ = new_tail;
        size_ += 1;
      }
      ~list_of_ints() {
        for (list_node *next, *p = head_; p != nullptr; p = next) {
          next = p->next;
          delete p;
        }
      }
    };

Then, to show that we understand how the standard library implements generic algorithms, we'll implement the function templates distance and count_if exactly as the C++17 standard library would implement them.

    template<typename Iterator>
    auto distance(Iterator begin, Iterator end)
    {
      using Traits = std::iterator_traits<Iterator>;
      if constexpr (std::is_base_of_v<std::random_access_iterator_tag,
        typename Traits::iterator_category>) {
          return (end - begin);
        } else {
         auto result = typename Traits::difference_type{};
         for (auto it = begin; it != end; ++it) {
           ++result;
         }
         return result;
      }
    }

    template<typename Iterator, typename Predicate>
    auto count_if(Iterator begin, Iterator end, Predicate pred) 
    {
      using Traits = std::iterator_traits<Iterator>;
      auto sum = typename Traits::difference_type{};
      for (auto it = begin; it != end; ++it) {
        if (pred(*it)) {
          ++sum;
        }
      }
      return sum;
    }

    void test()
    {
       list_of_ints lst;
       lst.push_back(1);
       lst.push_back(2);
       lst.push_back(3);
       int s = count_if(lst.begin(), lst.end(), [](int i){
          return i >= 2;
       });
       assert(s == 2);
       int d = distance(lst.begin(), lst.end());
       assert(d == 3);
    }

In the next chapter we'll stop implementing so many of our own function templates from scratch, and start marching through the function templates provided by the Standard Template Library. But before we leave this deep discussion of iterators, there's one more thing I'd like to talk about.