Ubiquitous Iterator
This article is contributed by Wang HaiLong.
Preface
As one of 23 basic Design Patterns, Iterator seems to appear everywhere. This article discusses some scenarios where Iterator Pattern is applied, including STL, Collection in Java, IEnumXXXX interface in COM, IRowset interface in OLE DB, RecordSet Object in ADO, ResultSet in JDBC, Cursor in Oracle's SQL/PL.
Iterator Concept
Iterator Pattern separates the iteration operation from Container/Collection. To satisfy Iterator Pattern, there must be two Objects: a Container and its Iterator.
The aim of Iterator Pattern is to unify the way of iterating a Container, in spite of what kiand of data is put in the Container, and how the Container's internal structure is implemented.
The following is a simple example imitating STL.
// SimpleArray.cpp
template<typename T>
class SimpleArray
{
T data[100];
public:
class Iterator
{
SimpleArray<T>* m_pArray;
int m_iCurrentIndex;
friend class SimpleArray<T>;
public:
Iterator( SimpleArray<T>* pArray = 0) : m_pArray(pArray)
{
}
void Reset()
{
m_iCurrentIndex = 0;
}
T operator *()
{
return m_pArray->data[m_iCurrentIndex];
}
void operator --()
{
m_iCurrentIndex--;
}
void operator ++()
{
m_iCurrentIndex++;
}
bool operator !=(const Iterator& another)
{
if( m_pArray != another.m_pArray )
return true;
if( m_iCurrentIndex != another.m_iCurrentIndex )
return true;
return false;
}
};
Iterator begin()
{
Iterator it(this);
it.m_iCurrentIndex = 0;
return it;
}
Iterator end()
{
Iterator it(this);
it.m_iCurrentIndex = 100;
return it;
}
friend class Iterator;
};
template<class Container>
int sum(Container & con)
{
Container::Iterator it;
int total = 0;
for( it = con.begin(); it != con.end(); it++)
{
total += *it;
}
return total;
}
void test()
{
SimpleArray<int> con;
int total = sum(con);
}
If later we don't want to use the SimpleArray any more, we can change the test function as below.
#include <set>
void test()
{
set<int> con;
int total = sum(con);
}
Hence the separation of data structure and algorithm.
STL
The above example demonstrates the usage of STL and how to write STL-style programs. Now lets discuss some STL features in more depth.
As we have seen, algorithms can exist independent of data structure using STL. The key concept is "Function Object", which is detailed in chapter 21 "STL Algorithms" of <<Thinking in C++>>.
Now lets take a glimpse of what is a "Function Object".
Take the method "sort" of list in STL, for example.
template<class Pred> void sort(greater<T> pr);
The parameter pr inherits the "Function Object" greater and is also a "Function Object".
And the implementation likely takes the following shape.
struct CCompareTwoItem : public std::greater< T >
{
public:
bool operator()( T item1, T item2 )
{
}
};
Iterator in Java and C++
Enumeration interface and Iterator interface( in Java2) are self-explanatory. What is more, sub view is supported in Java.
similar effect can be approximated through filter iterator.
IEnumXXXX interface in COM
The definition of IEnumXXXX is:
Interface IEnumXXX : IUnknown
{
virtual HRESULT Next(unsigned long celt, XXXX* rgelt, unsigned long * pceltFetched) = 0;
virtual HRESULT Skip(unsigned long celt) = 0;
virtual HRESULT Reset() = 0;
virtual HRESULT Clone(IEnumXXXX** ppeunm);
}
An good example is "Connectable Objects" in COM.
interface IConnectionPoint : IUnknown
{
HRESULT GetConnectionInterface(IID* pIID);
HRESULT GetConnectionPointContainer(IConnectionPointContainer** ppCPC);
HRESULT Advise(IUnknown* pUnk, DWORD* pdwCookie);
HRESULT Unadvise(DWORD dwCookie);
HRESULT EnumConnections(IenumConnections** ppEnum);
}
interface IconnectionPointContainer : IUnknown
{
HRESULT EnumConnectionPoints(IEnumConnectionPoints** ppEnum);
HRESULT FindConnectionPoint(REFIID riid, IConnectionPoint** ppCP);
}
interface IEnumConnectionPoints
{
HRESULT Next(ULONG cConnections, IConnectionPoint** rgpcn,ULONG* pcFetched);
HRESULT Skip(ULONG cConnections);
HRESULT Reset(void);
HRESULT Clone(IEnumConnectionPoints** ppEnum);
}
IConnectionPointContainer holds IConnectionPoint and IConnectionPointContainer's method EnumConnectionPoints returns an IEnumConnectionPoints which can iterate the IConnectionPointContainer to get every IConnectionPoint.
IRowset interface in OLE DB
IRowset method description:
AddRefRows Adds a reference count to an existing row handle.
GetData Retrieves data from the rowset's copy of the row.
GetNextRows Fetches rows sequentially, remembering the previous position.
ReleaseRows Releases rows.
RestartPosition Repositions the next fetch position to its initial position; that is, its position when the rowset was first created.
The definition of ICommand::Excute is:
HRESULT Execute (IUnknown* pUnkOuter, REFIID riid, DBPARAMS* pParams, LONG* pcRowsAffected, IUnknown** ppRowset);
This method returns an IRowset interface which can iterate through the result of "Excute".
RecordSet Object in ADO
The follow text is extracted from ADO help.
A Recordset object represents the entire set of records from a base table or the results of an executed command. At any time, the Recordset object only refers to a single record within the set as the current record.
Using the Open method on a Recordset object opens a cursor that represents records from a base table or the results of a query.
Ways to get RecordSet Object include:
On a Command object: Set recordset = command.Execute(RecordsAffected, Parameters, Options)
On a Connection object: Set recordset = connection.Execute(CommandText, RecordsAffected, Options)
ResultSet in JDBC
Connection Con = getConnection();
Statement stmt = con.createStatement(ResultSet.TYPE_SCROOL_INSENTIVE,
ResultSet.CONCUR_READ_ONLY);
ResultSet rs = stmt.excuteQuery(query);
While(rs.next()){c};
Cursor in Oracle's SQL/PL
We can look on Cursor as a forward-only iterator.
Appendix
Some great books about Design Patterns:
<<Design Patterns>> by Zurich, Sydney, Urbana, Hawthorne;
<<Thinking in C++>> and <<Thinking in Java >> by Bruce Eckel;
<<The Design Patterns Java Companion>> by James W. Cooper.
