Introduction
This article aims at explaining the Iterator pattern and having a rudimentary implementation of the Iterator pattern in C++ and C#. This article is meant for beginners
and does not use any language built-in features for iterations.
Background
Having a collection of objects is a very common thing in software development. If we have a collection of objects then we might also find ourselves in need to traverse this collection.
Most languages provide traversal techniques over basic collection types. C++ and C# also contain some special container types capable of holding a collection of values
(example: vectors in C++, List
s, and ArrayList
s in C#). These specialized containers also come with the possibility of getting iterated.
C# container classes and C++ STL container classes are the best examples of how the iterator pattern is implemented.
Note: We will not be using any of these techniques in this article.
If we want the underlying working mechanism of these iterator objects then we will perhaps need to understand the Iterator pattern first. The idea behind the Iterator pattern
is that we decouple the actual collection object from the traversal logic. This will make the collection object lighter as it does not have to deal with all the
iteration related functionalities and from the user's point of view, there is a clear separation between the collection and how the collection is being iterated.
Also, the user will not have to worry about keeping track of the number of items traversed, remaining, and whether to check for boundary conditions as all this is already
being done in the iterator object (as these things will depend on the underlying structure and implementation of the collection object).
GoF defines the Iterator pattern as "Provide a way to access the elements of an aggregate object sequentially without exposing its underlying representation". To
visualize the GoF design (slightly modified as per our implementation):
Using the code
Before jumping on to the implementation, let us try to see what each class in this diagram represents:
IIterator
: This is an interface that defines the methods for accessing and traversing elements.MyIterator
: This is ConcreteIterator, this will implement the Iterator interface and keep track of the current position in the traversal of the aggregate object.IAggregate
: This is an interface that defines methods for creating an Iterator object.MyAggregate
: This is the ConcreteAggregate object, i.e., the real collection lies inside this. This class implements the IAggregate
creation interface.
Creating the Iterator Interface
So now let us try to implement this pattern by implementing one class at a time. Let us start by writing the IIterator
interface. This interface should provide
the methods for accessing and traversing the elements of the collection object.
C# implementation of the IIterator
interface IIterator
{
string FirstItem { get;}
string NextItem{ get;}
string CurrentItem{ get;}
bool IsDone { get;}
}
C++ implementation of IIterator
:
class IIterator
{
public:
virtual std::string FirstItem() = 0;
virtual std::string NextItem() = 0;
virtual std::string CurrentItem() = 0;
virtual bool IsDone() = 0;
};
Creating the interface for an Aggregate (Collection) Object
Once we have the IIterator
ready, let's have the interface IAggregate
. This will simply contain the method to create the iterator.
C# implementation of IAggregate
:
interface IAggregate
{
IIterator GetIterator();
string this[int itemIndex]{set;get;}
int Count{get;}
}
C++ implementation of IAggregate
:
class IAggregate
{
public:
virtual IIterator* GetIterator() = 0;
virtual std::string& operator[](int itemIndex) = 0;
virtual int Count() = 0;
};
Writing the Concrete Aggregate (Collection) Object
Now that we have both the interfaces ready, we can now define the concrete class that will hold a collection of objects. Let's have a simple class that will hold
a collection of string values. We will use our iterator to get hold of these string values.
C# implementation of MyAggregate
:
class MyAggregate : IAggregate
{
List<string> values_ = null;
public MyAggregate()
{
values_ = new List<string>();
}
#region IAggregate Members
public IIterator GetIterator()
{
return new MyIterator(this);
}
#endregion
public string this[int itemIndex]
{
get
{
if (itemIndex < values_.Count)
{
return values_[itemIndex];
}
else
{
return string.Empty;
}
}
set
{
values_.Add(value);
}
}
public int Count
{
get
{
return values_.Count;
}
}
}</string>
C++ implementation of MyAggregate
:
class MyAggregate : public IAggregate
{
std::vector<std::string> values_;
public:
MyAggregate(void)
{}
void AddValue(std::string value)
{
values_.push_back(value);
}
IIterator* GetIterator()
{
IIterator *iter = new MyIterator(this);
return iter;
}
std::string& operator[](int itemIndex)
{
return values_[itemIndex];
}
int Count()
{
return values_.size();
}
};
Implementing the Concrete Iterator
Let us now implement the MyIterator
, which is the concrete class for IIterator
. The actual logic of iterating through the values of the concrete
collection class will be in this class.
C# implementation of MyIterator
:
class MyIterator : IIterator
{
IAggregate aggregate_ = null;
int currentIndex_ = 0;
public MyIterator(IAggregate aggregate)
{
aggregate_ = aggregate;
}
#region IIterator Members
public string FirstItem
{
get
{
currentIndex_ = 0;
return aggregate_[currentIndex_];
}
}
public string NextItem
{
get
{
currentIndex_ += 1;
if (IsDone == false)
{
return aggregate_[currentIndex_];
}
else
{
return string.Empty;
}
}
}
public string CurrentItem
{
get
{
return aggregate_[currentIndex_];
}
}
public bool IsDone
{
get
{
if (currentIndex_ < aggregate_.Count)
{
return false;
}
return true;
}
}
#endregion
}
C++ implementation of MyIterator
:
class MyIterator : public IIterator
{
IAggregate *aggregate_;
int currentIndex_;
public:
MyIterator(IAggregate *aggregate)
: currentIndex_(0)
, aggregate_(aggregate)
{
}
std::string FirstItem()
{
currentIndex_ = 0;
return (*aggregate_)[currentIndex_];
}
std::string NextItem()
{
currentIndex_ += 1;
if (IsDone() == false)
{
return (*aggregate_)[currentIndex_];
}
else
{
return "";
}
}
std::string CurrentItem()
{
return (*aggregate_)[currentIndex_];
}
bool IsDone()
{
if (currentIndex_ < aggregate_->Count())
{
return false;
}
return true;
}
};
So now we have all the building blocks ready for a simple and rudimentary implementation of the Iterator pattern. Let's see how we can use the iterator to access the values of a collection.
Here is the C# implementation:
class Program
{
static void Main(string[] args)
{
MyAggregate aggr = new MyAggregate();
aggr[0] = "1";
aggr[1] = "2";
aggr[2] = "3";
aggr[3] = "4";
aggr[4] = "5";
aggr[5] = "6";
aggr[6] = "7";
aggr[7] = "8";
aggr[8] = "9";
aggr[9] = "10";
IIterator iter = aggr.GetIterator();
for (string s = iter.FirstItem; iter.IsDone == false; s = iter.NextItem )
{
Console.WriteLine(s);
}
}
}
and finally here is the C++ implementation:
int _tmain(int argc, _TCHAR* argv[])
{
MyAggregate aggr;;
aggr.AddValue("1");
aggr.AddValue("2");
aggr.AddValue("3");
aggr.AddValue("4");
aggr.AddValue("5");
aggr.AddValue("6");
aggr.AddValue("7");
aggr.AddValue("8");
aggr.AddValue("9");
aggr.AddValue("10");
IIterator *iter = aggr.GetIterator();
for (std::string s = iter->FirstItem(); iter->IsDone() == false; s = iter->NextItem() )
{
std::cout << s << std::endl;;
}
return 0;
}
Now we have a simple implementation of the Iterator pattern in place. There are a lot of possible optimizations possible in the code but the intent here is to explain
the Iterator pattern so the code is written in a simple (and perhaps not so efficient) manner.
Points of Interest
The .NET Framework and C# language has the Iterator pattern embedded deep in its code. The IEnumerable
interface is in fact the facilitator
of the Iterator pattern. Generics and Collection classes in C# can be iterated through an enumerator which is in fact an Iterator pattern implementation. C++ STL objects like vectors and
lists can also be iterated using iterators which is also an implementation of the Iterator pattern.
We have not seen the C#, .NET, or C++ specific implementations of the Iterator pattern in this article. Using the language and framework built-in iterators is definitely more
efficient and less error prone. The idea behind this article is to understand how the Iterator pattern works and we implemented a simple Iterator pattern in C# and C++.
History
- 07 April 2012: First version.