Patterns. Iterator (Cursor) pattern. General information

Iterator (Cursor) pattern. General information. Methods of implementation. Structural scheme. Example on C++

Search other websites:

1. Purpose of the Iterator pattern

The Iterator pattern refers to patterns of objects behavior. The second name of the pattern is Cursor. The Iterator pattern is designed to provide access to the elements of object of aggregate structure in such a way that the internal representation of that object is not exposed.

The essence of the Iterator pattern is that for each object of the aggregated structure (array, list, queue, etc.), an appropriate mechanism (functionality) for traversing the elements of this object is developed. The bypass mechanism provided by developing one or more classes.

⇑

2. General information about aggregated data structures and iterators

Each aggregated data structure is implemented by a class (container class) or container. Containers are used to store a collection of objects of any type. They allocate the memory needed to store objects and provide all the necessary functionality to access those objects.

Examples of containers for which it is advisable to use iterators:

a set of bits (bitset);
different kinds of queues: regular queue, deque, priority queue;
stack;
dynamic array;
linear list;
set;
hash table (map, multimap).

Various iterators are used for the above containers that provide traversal, for example:

bidirectional iterator. This kind of iterator is for storing and retrieving values. Moving through the elements of the container occurs in both directions (forward and backward);
direct iterator. Stores and retrieves a value from a container. Moves forward only;
input iterator. Only pulls elements. Moves forward only;
output iterator. Only stores items. Moves forward only;
random access iterator. This iterator is designed to store and retrieve values from a container. An iterator provides random access to elements.

Optionally, the programmer can implement his own (specific) type of iterator, which will traverse (use) the container based on some conditions corresponding to the task at hand.

⇑

3. Ways to implement the Iterator pattern. Generalized structure of the Iterator (Cursor) pattern

In terms of supporting different types of containers and iterators, the Iterator pattern can be implemented in one of four possible ways:

support for a well-defined container and well-defined iterator (Figure 1);
support for several types of containers (polymorphic containers) and a general iterator (Figure 2);
support for a specific container and several (polymorphic) iterators (Figure 3);
support for several types of containers and several iterators (Figure 4).

⇑

3.1. One container and one iterator

3.1.1. Structure. Figure

The simplest use case for the Iterator pattern is when there is one container class and one iterator is implemented for it. In this case, the structure of the pattern looks as shown in Figure 1.

Figure 1. Iterator pattern structure for one aggregate and one iterator (simplest case)

⇑

3.1.2. Implementation in C++. Program text

Below is an implementation of the Iterator pattern for the structure shown in Figure 1. The implementation has the following features:

the container is a dynamic array of elements;
the forward iterator is selected as the iterator.

#include <iostream>
using namespace std;

// Iterator pattern for one aggregate and one iterator
// Class preliminary declaration.
template <class T>
class Aggregate;

// Iterator class
template <class T>
class Iterator
{
private:
  const Aggregate<T>* aggregate;
  long current;

public:
  // Constructor that gets the aggregated object
  Iterator(const Aggregate<T>* _aggregate) :
  aggregate(_aggregate), current(0)
  { }

  // Move (move the cursor) to the beginning of the list
  virtual void First()
  {
    current = 0;
  }

  // Move the cursor to the next item in the list
  virtual void Next()
  {
    current++;
  }

  // Check whether the end of the list is reached.
  // The current cursor position is behind the last item in the list
  virtual bool IsDone() const
  {
    return current >= aggregate->Count();
  }

  // Get a list item at the current cursor position
  virtual T CurrentItem() const
  {
    if (!IsDone())
      return aggregate->GetItem(current);
    else
    {
      // Here is an error, you can throw an exception or perform other actions
      cout << "Error." << endl;
      return 0;
    }
  }
};

// Aggregate class
template <class T>
class Aggregate
{
private:
  // aggregate data (list, array, ...)
  T* data;
  long count;

public:
  // Constructor
  Aggregate(long _count)
  {
    if (_count < 0)
    {
      count = 0;
      data = nullptr;
      return;
    }

    try
    {
      data = new T[_count];
      count = _count;

      for (int i = 0; i < count; i++)
        data[i] = (T)0;
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      count = 0;
      data = nullptr;
    }
  }

  // Copy constructor
  Aggregate(const Aggregate& obj)
  {
    // copy data from obj to the current instance
    count = obj.count;

    // allocate memory for the array as a whole
    try
    {
      data = new T[count];

      for (int i = 0; i < count; i++)
        data[i] = obj.data[i];
    }
    catch (bad_alloc e)
    {
      cout << e.what() << endl;
      count = 0;
    }
  }

  // Method that returns an iterator
  Iterator<T>* CreateIterator() const
  {
    return new Iterator<T>(this);
  }

  // Other methods of class ConcreteAggregate
  long Count() const
  {
    return count;
  }

  T GetItem(long index) const
  {
    if ((index >= 0) && (index < count))
      return data[index];
    return data[0];
  }

  // Method that adds an element to the end of the list
  void Append(T value)
  {
    T* data2 = data;
    data = new T[count + 1];
    for (int i = 0; i < count; i++)
      data[i] = data2[i];
    data[count++] = value;
    delete[] data2;
  }

  // Delete item from the list,
  // index = 0, 1, ..., count-1
  void Remove(long index)
  {
    if ((index >= 0) && (index < count))
    {
      // Delete item from the list
      T* data2 = data;
      data = new T[count - 1];
      for (int i = 0; i < index; i++)
        data[i] = data2[i];

      for (int i = index + 1; i < count; i++)
        data[i - 1] = data2[i];
      count--;
      delete[] data2;
    }
  }

  // Destructor
  ~Aggregate()
  {
    if (count > 0)
      delete[] data;
  }

  // Displaying the contents of the aggregate
  void Print(string text)
  {
    cout << text << endl;
    for (int i = 0; i < count; i++)
      cout << data[i] << " ";
    cout << endl;
  }
};

void main()
{
  // Demonstration of using Iterator pattern
  // 1. Create an aggregate
  Aggregate<double> ag(0);
  ag.Append(2.55);
  ag.Append(3.8);
  ag.Append(-1.557);
  ag.Append(7.32);

  // 2. Display aggregate
  ag.Print("ag:");

  // 3. Create an iterator
  Iterator<double>* it = ag.CreateIterator();

  // 4. Display the first element of the aggregate
  double x = it->CurrentItem();
  cout << "x = " << x << endl;

  // 5. Display all elements of an aggregate in a loop
  cout << "-------------" << endl;
  cout << "Items in ag: ";
  it->First();
  while (!it->IsDone())
  {
    cout << it->CurrentItem() << " ";
    it->Next();
  }

  // 6. Free the memory allocated for it
  delete it;
}

⇑

3.1.3. Implementation in C++. Guaranteed deletion of an iterator

In the previous paragraph 3.1.2, in the client code (main() function), the iterator was obtained using the CreateIterator() method as follows

...

// 3. Create iterator
Iterator<double>* it = ag.CreateIterator();

...

This obliged the client to delete the memory allocated for the it pointer after using it.

...

// 6. Free the memory allocated for it
delete it;

...

The reason for this is a memory leak.

To simplify the client’s work, you need to create an additional class that will replace the iterator and automatically destroy an object of type Iterator<T> when you leave the scope. Below is the code for this class.

template <class T>
class IteratorPtr
{
private:
  // Internal field is an iterator as a pointer
  Iterator<T>* it;

public:
  // Class constructor
  IteratorPtr(Iterator<T>* _it) : it(_it) { }

  // Destructor
  ~IteratorPtr()
  {
    delete it;
  }

  // Overridden operator -> of access by pointer
  Iterator<T>* operator->()
  {
    return it;
  }

  // Overridden operator * of access by pointer
  Iterator<T>& operator*()
  {
    return *it;
  }

private:
  // Prevent copying
  IteratorPtr(const IteratorPtr&); // hide copy constructor

  // Disallow assignment - define operator = in the private section
  IteratorPtr& operator=(const IteratorPtr&)
  {
  }
};

As you can see from the above code, the main methods are operator functions operator->() and operator*(), which override access to an iterator of type Iterator<T> by pointer. In the constructor, memory is allocated for the it pointer. This memory is freed in the destructor. Therefore, the client does not need to deal with additionally freeing memory for the it pointer.

After introducing the IteratorPtr class into the program code from clause 3.1.2, the client code can be like this

...

void main()
{
  // Use IteratorPtr class in client code
  // 1. Create aggregate
  Aggregate<double> ag(0);
  ag.Append(2.55);
  ag.Append(3.8);
  ag.Append(-1.557);
  ag.Append(7.32);

  // 2. Display aggregate
  ag.Print("ag:");

  // 3. Create the instance of IteratorPtr class
  IteratorPtr<double> itPtr(ag.CreateIterator());

  // 4. Print a list of items using itPtr
  cout << "-------------------------" << endl;
  itPtr->First(); // set the first item
  while (!itPtr->IsDone())
  {
    cout << itPtr->CurrentItem() << " ";
    itPtr->Next();
  }
}

⇑

3.2. Polymorphic container and one iterator. Structure. Picture

If you need to use one iterator for aggregates of different implementations, then the structure of the Iterator pattern looks as shown in Figure 2. An abstract class Aggregate is created, which is extended with several concrete aggregates ConcreteAggregate1, ConcreteAggregate2… Each specific aggregate has a unique implementation for storing datasets.

Figure 2. The structure of pattern Iterator. Case with multiple containers and one iterator

⇑

3.3. A container with support for multiple iterators. Picture

Several types of iterators can be implemented for one container. These iterators can implement various ways of traversing the elements of the container (see section 2). In this case, the iterator must be implemented in such a way that the dependency on the specific implementation disappears. Figure 3 shows the structure of the Iterator pattern in which there is no dependence on a specific implementation of the iterator, that is, a polymorphic iterator is implemented. An abstract class Iterator is created, which is inherited by the specialized iterators ConcreteIterator1, ConcreteIterator2, etc.

Figure 3. The structure of Iterator pattern. The case with one container and multiple iterators

⇑

3.4. Polymorphic container and polymorphic iterator. Picture

Figure 4 shows the structure of the Iterator pattern for a single aggregated object (container) with the ability to support multiple aggregated objects and multiple iterators.

Support for multiple aggregate objects is provided by declaring an abstract class Aggregate, which serves as the interface between the client and the concrete aggregate (the ConcreteAgregate class and/or another class). Likewise, the abstract Iterator class is the interface between the client and concrete iterators that implement various ways to traverse an aggregated object. This provides polymorphism for the container and iterator.

Figure 4. The structure of Iterator pattern with support of polymorphic container and polymorphic iterator

⇑

4. The need (advantages) of using iterators for containers

The advantages of using the Iterator pattern include the following:

providing access to the content of aggregated objects without disclosing their internal implementation. It is clear that in the code of the container class, you can additionally implement the necessary functionality for various types of traversal of aggregated objects. However, this approach will significantly complicate the interface of the container class itself. It is more expedient to separate the main operations on the container from the operations of traversing the elements of the container;
providing support for various options for traversing an aggregated object (unidirectional traversal, arbitrary traversal, etc.);
providing a uniform polymorphic interface in order to traverse different types of aggregated objects (list, semantic tree, dynamic array, etc.).

BestProg