Polymorphic Iteration
The iterator is a well-known and useful design pattern for simplifying access to elements in a collection without exposing the collection’s underlying representation. If you’ve used STL, you’re probably familiar with STL’s definition of iterators.
Example 16 illustrates how STL-style iterators are declared and used:
Example 16 – Declaring and using standard STL iterators
// Declare the vector and iterator
vector<int> v;
vector<int>::const_iterator i;
// Insert a few elements
v.push_back(1); v.push_back(2); v.push_back(3);
// Traverse and process the items
for (i = v.begin(); i != v.end(); i++) {
// process items
}
This code simply creates an array of integers and traverses the collection. Using iterators, your client code has less knowledge and dependence on the internal structure of the collection. All collections are traversed with identical semantics, making it easier to substitute one collection type for another. STL’s iterators are flexible and easy to use.
STL-style iterators are not polymorphic, however. To create an iterator, you must know the type of collection. By contrast, a
polymorphic iterator is a single class that can iterate over any type of collection which supports traversal. A polymorphic iterator can be created on any type of collection with no knowledge of the collection’s type. The Stingray Foundation Library provides a powerful extension to STL’s iterator definition, which makes STL iterators polymorphic.
Example 17 is equivalent to
Example 16, except that it uses SFL’s polymorphic iterators instead of STL-style iterators.
Example 17 – Declaring and using SFL polymorphic iterators
// Declare the vector and iterator
traversable < vector<int> > v; // 1
const_iterator<int> i(&v); // 2
// Insert a few elements
v.push_back(1); v.push_back(2); v.push_back(3);
// Traverse and process the items
for (i.begin(); !i.at_end(); i++) { // 3
// process items
}
Polymorphic iterators are declared and used in a very similar fashion to STL standard iterators, but with some important differences:
SFL’s polymorphic iteration solution can be divided into three parts:
• The polymorphic iterator templates
• The traversable interfaces
• The traversable mix-in templates
The Polymorphic Iterator Templates
STL offers five categories of iterators:
• Input
• Output
• Forward
• Bidirectional
• Random
The Stingray Foundation Library adds a sixth category: Polymorphic. Polymorphic iterators are derivatives of bidirectional iterators and offer the same capabilities. They can traverse in forward and reverse directions and allow retrieval and storage of elements. They add the ability to traverse a collection without express knowledge of its type. Polymorphic iterators can be used with most of the STL algorithms that accept bidirectional iterators. Note that polymorphic iterators are not randomly accessible and are not compatible with STL algorithms that require this property.
Like bidirectional iterators, polymorphic iterators come in four basic types:
• const_iterator<>
• iterator<>
• const_reverse_iterator<>
• reverse_iterator<>
These iterators are interface-compatible with their bidirectional counterparts and, for the most part, can be used interchangeably. However, their declaration is somewhat different. All polymorphic iterators are templatized classes whose parameter is the type of element contained in the collection being traversed. And unlike standard STL iterators, polymorphic iterators are not nested classes declared within a collection class. As a result, their declaration isn’t scoped by the collection class. Finally, the collection the iterator should attach itself to is passed as a constructor argument. The example below illustrates how a polymorphic iterator is declared:
Example 18 – Declaring a polymorphic iterator
const_iterator< element_type > iter ( &aCollection );
or
iterator< element_type > iter ( &aCollection );
NOTE >> STL also defines classes such as const_iterator and iterator. If you push STL and SFL into the global namespace, you can end up with a collision.
A namespace conflict can be corrected in three independent ways:
• Fully qualify iterator declarations. For example:
stingray::foundation::const_iterator<>)
• Make sure your SFL using clause follows your STL using clause.
• Add individual using clauses for SFL iterators. For example:
using stingray::foundation::const_iterator;
using stingray::foundation::iterator;
The Traversable Interfaces
Exchanging a collection between classes or functions usually requires an agreed-upon collection type. For example, perhaps you need to write a
display_employees() function that takes a collection of employees and writes their names to a console. With STL, you might write the function as in
Example 19.
Example 19 – Displaying a collection with standard STL iteration
void display_employees( const vector< employee >& vEmpl )
{
vector< employee >::const_iterator i;
// Traverse and process the items
for (i = vEmpl.begin(); i != vEmpl.end(); i++) {
cout << (*i).GetName();
}
}
But, what if the employees are sometimes stored in a map or a list? You would have to write this function three or more times, only changing the collection type. You can use templated functions to accomplish this, but they are still generating essentially the same function three or more times.
With polymorphic iteration, you can write one function to process an aggregate, regardless of the collection type. The Stingray Foundation Library defines two interface templates for this purpose:
• IConstTraversableT<>
• ITraversableT<>
All polymorphic iterators take one of these interfaces as a constructor argument, and use it as a bridge to the collection. The iterator calls the traversal interface members to move between and access elements. Any collection that implements these interfaces becomes accessible through the polymorphic iterators.
With
IConstTraversableT<>, you can rewrite the
display_employees() function once for all collection types, as shown in
Example 20.
Example 20 – Displaying all collection types with SFL polymorphic iteration
void display_employees( IConstTraversableT< employee >& tEmpl )
{
const_iterator< employee > i(tEmpl);
/*** Next line doesn’t compile
iterator< employee > i(tEmpl);
**** only const iterators allowed
**** on an IConstTraversableT<> */
// Traverse and process the items
for (i.begin(); !i.at_end(); i++) {
cout << (*i).GetName();
}
}
Both IConstTraversableT<> and ITraversableT<> serve as abstract aggregate objects that can be iterated over. The difference is that IConstTraversableT<> supports only const_iterator<> and const_reverse_iterator<>, while ITraversableT<> supports all four polymorphic iterator types.
The power of traversable interfaces is that they allow you to exchange and use aggregates without concern for collection type. Returning a collection is another place where this is useful, as shown in
Example 21, where a function searches for all employees contributing to a 401K plan.
Example 21 – Using aggregates without knowing collection type
ITraversableT< employee >& EmployeeServer::Get401kContributors()
{
// Perform SQL query
...
return m_tMatches;
}
Now, client code will be able to receive, traverse and process the returned set of employees, without knowing the collection type or impacting the code when the type changes.
The Traversable Mix-in Templates
As discussed in the previous section, any collection that implements one of the traversable interfaces is accessible through the polymorphic iterators. To ease the task of mixing in and implementing these interfaces, SFL provides two helpers:
• const_traversable<>
• traversable<>
The purpose of these templates is to make any STL-compliant collection usable with the polymorphic iterators by implementing
IConstTraversableT<> and
ITraversableT<>, respectively. These templates are an example of the decorator design pattern, discussed in
“Wrappers (Decorators).” Their approach is to use multiple derivation from the collection type argument and the appropriate traversable interface, implementing its members. Because derivation is used, the original collection interface is preserved. So, collection declarations can be wrapped with one of the templates without impacting existing code.
Example 22 illustrates how these templates are used.
Example 22 – Adapting STL collections to polymorphic iteration
traversable < vector<int> > v;
or
const_traversable < deque<int> > dq;
You can manually derive and implement the traversable interfaces for your own collection classes. Or, make your own collections STL-compliant so the traversable mix-in templates will work with them. To be STL-compliant in this sense, your collection class must have the nested iterators const_iterator, iterator, reverse_iterator, and const_reverse_iterator with STL’s calling conventions.
Lifetime Management
Lifetime management is dealt with by the traversable interfaces. Both IConstTraversableT<> and ITraversableT<> support reference counting through AddRef() and Release() members. However, STL collections (and many other collection classes) are not reference counted by default. You can fix that by aggregating and dynamically allocating the collection, but that approach does not preserve the collection’s interface.
The SFL solution is to declare AddRef() and Release() members in the traversable interface. If the underlying collection supports reference counting, these members delegate. Otherwise, they do nothing. To provide for reference-counted and non-reference-counted collections, SFL has two versions of the traversable mix-in templates:
• const_traversable<>
• traversable<>
• refcounted_const_traversable<>
• refcounted_traversable<>
The reference-counted prefixed versions handle lifetime management by delegating AddRef() and Release() calls to the underlying collections. The non-prefixed versions define AddRef() and Release() as no-ops; these versions should be used with STL collections.
MFC and COM Collections
The traversable interfaces can be mixed into any collection class, providing you with a uniform method of access for all collections. Through traversable interfaces, you can more easily use collection classes from MFC, STL, COM and your own custom collections in a single project. Using the traversable interfaces, you could even provide location transparency for a collection while still achieving a friendly, STL-like interface.