4.5 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

• const_iterator<>

• iterator<>

• const_reverse_iterator<>

• reverse_iterator<>

Example 18: Declaring a polymorphic iterator

const_iterator< element_type > iter ( &aCollection );

or

iterator< element_type > iter ( &aCollection );

---

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;

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<>

With IConstTraversableT<>, you can rewrite the display_employees() function once for all collection types, as shown in Example 117.

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.

• 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 Section 8.3.6, "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.

Copyright © Rogue Wave Software, Inc. All Rights Reserved.

The Rogue Wave name and logo, and Stingray, are registered trademarks of Rogue Wave Software. All other trademarks are the property of their respective owners.
Provide feedback to Rogue Wave about its documentation.