Iterators

As you may have noticed in some of the examples for arrays and vectors, we add numbers to the iterators. Iterators are like pointers, but they also provide a common interface for STL containers. The operations on these iterators are strictly based on the type of iterators, which is dependent on the container. Iterators for vectors and arrays are the most flexible in terms of functionality. We can access any element from the container directly, based on its position, using operator[] because of the contiguous nature of the data. This iterator is also known as a random access iterator. However, for forward_list, there is no direct way to traverse back, or even go from one node to its preceding node, without starting from the beginning. Hence, the only arithmetic operator allowed for this is increment. This iterator is also known as a forward iterator.

There are other utility functions that we can use, such as advance, next, and prev, depending on the type of iterators. next and prev take an iterator and a distance value, and then return the iterator pointing to the element that is at the given distance from the given iterator. This works as expected provided that the given iterator supports the operation. For example, if we try to use the prev function with a forward iterator, it will throw a compilation error, since this iterator is a forward iterator and can only move forward. The time taken by these functions depends on the type of iterators used. All of them are constant time functions for random access iterators, since addition and subtraction are constant-time operations. For the rest of the iterators, all of them are linear to the distance that needs to be traversed forward or backward. We shall use these iterators in the following exercise.

Exercise 4: Exploring Different Types of Iterators

Let's say that we have a list of the winners of the Singapore F1 Grand Prix from the last few years. With the help of vector iterators, we'll discover how we can retrieve useful information from this data. After that, we'll try to do the same thing with forward_list, and see how it differs from vector iterators:

1. Let's first include the headers:

   #include <iostream>
   #include <forward_list>
   #include <vector>
   int main()
   {

2. Let's write a vector with a list of winners:

   std::vector<std::string> vec = {"Lewis Hamilton", "Lewis Hamilton", "Nico Roseberg", "Sebastian Vettel", "Lewis Hamilton", "Sebastian Vettel", "Sebastian Vettel", "Sebastian Vettel", "Fernando Alonso"};
   auto it = vec.begin();       // Constant time
   std::cout << "Latest winner is: " << *it << std::endl;
   it += 8;                    // Constant time
   std::cout << "Winner before 8 years was: " << *it << std::endl;
   advance(it, -3);            // Constant time
   std::cout << "Winner before 3 years of that was: " << *it << std::endl;

3. Let's try the same with the forward_list iterators and see how they differ from vector iterators:

   std::forward_list<std::string> fwd(vec.begin(), vec.end());
   auto it1 = fwd.begin();
   std::cout << "Latest winner is: " << *it << std::endl;
   advance(it1, 5);   // Time taken is proportional to the number of elements
   std::cout << "Winner before 5 years was: " << *it << std::endl;
   // Going back will result in compile time error as forward_list only allows us to move towards the end.
   // advance(it1, -2);      // Compiler error
   }

4. Running this exercise should produce the following output:

   Latest winner is : Lewis Hamilton
   Winner before 8 years was : Fernando Alonso
   Winner before 3 years of that was : Sebastian Vettel
   Latest winner is : Sebastian Vettel
   Winner before 5 years was : Sebastian Vettel

5. Now, let's see what happens if we add a number to this iterator by putting the following line inside the main function at the end:

   it1 += 2;

   We'll get an error message similar to this:

   no match for 'operator+=' (operand types are std::_Fwd_list_iterator<int>' and 'int')

The various iterators we have explored in this exercise are quite useful for easily fetching any data from your dataset.

As we have seen, std::array is a thin wrapper over a C-style array, and std::forward_list is nothing but a thin wrapper over a singly linked list. It provides a simple and less error-prone interface without compromising on performance or memory.

Apart from that, since we can access any element immediately in the vector, the addition and subtraction operations on the vector iterator are O(1). On the other hand, forward_list only supports access to an element by traversing to it. Hence, its iterators' addition operation is O(n), where n is the number of steps we are advancing.

In the following exercise, we shall make a custom container that works in a similar way to std::forward_list, but with some improvements. We shall define many functions that are equivalent to forward_list functions. It should also help you understand how these functions work under the hood.

Exercise 5: Building a Basic Custom Container

In this exercise, we're going to implement an std::forward_list equivalent container with some improvements. We'll start with a basic implementation called singly_ll, and gradually keep on improving:

1. Let's add the required headers and then start with the basic implementation of singly_ll with a single node:

   #include <iostream>
   #include <algorithm>
   struct singly_ll_node
   {
       int data;
       singly_ll_node* next;
   };

2. Now, we'll implement the actual singly_ll class, which wraps the node around for better interfacing:

   class singly_ll
   {
   public:
       using node = singly_ll_node;
       using node_ptr = node*;
   private:
       node_ptr head;

3. Now, let's add push_front and pop_front, just like in forward_list:

   public:
   void push_front(int val)
   {
       auto new_node = new node{val, NULL};
       if(head != NULL)
           new_node->next = head;
       head = new_node;
   }
   void pop_front()
   {
       auto first = head;
       if(head)
       {
           head = head->next;
           delete first;
       }
       else
           throw "Empty ";
   }

4. Let's now implement a basic iterator for our singly_ll class, with constructors and accessors:

   struct singly_ll_iterator
   {
   private:
       node_ptr ptr;
   public:
       singly_ll_iterator(node_ptr p) : ptr(p)
       {
   }
   int& operator*()
   {
       return ptr->data;
   }
   node_ptr get()
   {
       return ptr;
   }

5. Let's add the operator++ functions for pre- and post-increments:

   singly_ll_iterator& operator++()     // pre-increment
   {
           ptr = ptr->next;
           return *this;
   }
   singly_ll_iterator operator++(int)    // post-increment
   {
       singly_ll_iterator result = *this;
   ++(*this);
   return result;
   }

6. Let's add equality operations as friend functions:

       friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right)
       {
           return left.ptr == right.ptr;
       }
       friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right)
       {
           return left.ptr != right.ptr;
       }
   };

7. Let's jump back to our linked list class. Now that we've got our iterator class, let's implement the begin and end functions to ease the traversal. We'll also add const versions for both:

   singly_ll_iterator begin()
   {
       return singly_ll_iterator(head);
   }
   singly_ll_iterator end()
   {
       return singly_ll_iterator(NULL);
   }
   singly_ll_iterator begin() const
   {
       return singly_ll_iterator(head);
   }
   singly_ll_iterator end() const
   {
       return singly_ll_iterator(NULL);
   }

8. Let's implement a default constructor, a copy constructor for deep copying, and a constructor with initializer_list:

   singly_ll() = default;
   singly_ll(const singly_ll& other) : head(NULL)
   {
       if(other.head)
           {
               head = new node;
               auto cur = head;
               auto it = other.begin();
               while(true)
               {
                   cur->data = *it;
                   auto tmp = it;
                   ++tmp;
                   if(tmp == other.end())
                       break;
                   cur->next = new node;
                   cur = cur->next;
                   it = tmp;
               }
           }
   }
   singly_ll(const std::initializer_list<int>& ilist) : head(NULL)
   {
       for(auto it = std::rbegin(ilist); it != std::rend(ilist); it++)
               push_front(*it);
   }
   };

9. Let's write a main function to use the preceding functions:

   int main()
   {
       singly_ll sll = {1, 2, 3};
       sll.push_front(0);
       std::cout << "First list: ";
       for(auto i: sll)
           std::cout << i << " ";
       std::cout << std::endl;
       
       auto sll2 = sll;
       sll2.push_front(-1);
       std::cout << "Second list after copying from first list and inserting -1 in front: ";
       for(auto i: sll2)
           std::cout << i << ' ';  // Prints -1 0 1 2 3
       std::cout << std::endl;
       std::cout << "First list after copying - deep copy: ";
   for(auto i: sll)
           std::cout << i << ' ';  // Prints 0 1 2 3
       std::cout << std::endl;
   }

10. Running this exercise should produce the following output:

    First list: 0 1 2 3
    Second list after copying from first list and inserting -1 in front: -1 0 1 2 3 
    First list after copying - deep copy: 0 1 2 3

As we can see in the preceding example, we are able to initialize our list using std::initializer_list. We can call the push, pop_front, and back functions. As we can see, sll2.pop_back only removed the element from sll2, and not sll. sll is still intact with all five elements. Hence, we can perform a deep copy as well.

Activity 1: Implementing a Song Playlist

In this activity, we'll look at some applications for which a doubly-linked list is not enough or not convenient. We will build a tweaked version that fits the application. We often encounter cases where we have to customize default implementations, such as when looping songs in a music player or in games where multiple players take a turn one by one in a circle.

These applications have one common property – we traverse the elements of the sequence in a circular fashion. Thus, the node after the last node will be the first node while traversing the list. This is called a circular linked list.

We'll take the use case of a music player. It should have following functions supported:

1. Create a playlist using multiple songs.
2. Add songs to the playlist.
3. Remove a song from the playlist.
4. Play songs in a loop (for this activity, we will print all the songs once).

   Note

   You can refer to Exercise 5, Building a Basic Custom Container where we built a container from scratch supporting similar functions.

Here are the steps to solve the problem:

1. First, design a basic structure that supports circular data representation.
2. After that, implement the insert and erase functions in the structure to support various operations.
3. We have to write a custom iterator. This is a bit tricky. The important thing is to make sure that we are able to traverse the container using a range-based approach for a loop. Hence, begin() and end() should return different addresses, although the structure is circular.
4. After building the container, build a wrapper over it, which will store different songs in the playlist and perform relevant operations, such as next, previous, print all, insert, and remove.

   Note

   The solution to this activity can be found on page 476.

std::forward_list has several limitations. std::list presents a much more flexible implementation of lists and helps overcome some of the shortcomings of forward_list.