12,896,539 members (56,067 online)
alternative version

#### Stats

41.9K views
18 bookmarked
Posted 6 Oct 2004

# Typed Iteration over a Composite

, 13 Oct 2004
 Rate this:
Implementation of STL compliant type sensitive composite iterators.

## Introduction

The composite is a very powerful pattern, allowing a polymorphic tree of objects to know about its structure. In order for this pattern to be successful, it is usual to implement a variety of iterators over the hierarchy. This article deals with the problem of typed iteration. Developing work from a previous article, I have constructed a set of tree iterators that only return children of a particular type.

## Background

In a previous article on Composites and Visitors, I dealt with the problem of creating a generic composite tree and applying different visitation strategies to that tree. In the first of two articles, I would like to deal with the problem of typed iteration. The second article will generalize this concept into the use of functors to limit what tree nodes are returned in an iteration. Typed iteration is particularly useful because it handles the down-casting of entries into a particular base type. Also, because the iterators are essentially STL compliant, they can be fed into STL algorithms as required.

The composite is often used in areas such as expression trees or 3D graphics applications. In a graphics application, the scene information is often stored in a composite. A typed iterator would allow you to iterate over the scene hierarchy picking out only material node, or only geometry nodes. This could be particularly useful if you are running a triangulation visitor that will triangulate all geometry nodes.

## Using the code

To understand how to use the composite tree, you should read my previous article. Essentially, the iterators are quite simple. The only major changes from a conventional iterator are that in the `begin` and `operator++` functions, a simple `while` loop iterates until we get the correctly typed entry. They must also check to ensure we have not reached the end of the list. We cannot rely on the user comparing against `end()` because the last item in the list might not be our required type; therefore, the iterator has to carry around the value of `end()`. This has two small down-sides. The first is that the iterator is twice the size of a conventional iterator. The second is that if the list grows during an iteration, the iterators will be invalidated. The second issue is no different to the problem seen with certain STL containers such as vectors or the associative containers. Showing the code, I have stripped out a lot of extraneous details from the classes (such as the const versions), and reformatted slightly. If you want to see the full original, then please download the source.

The shallow iterator:

```template <typename T>
class CGenericTree
{
public:
// Typed shallow iterator

template <typename child>
class typed_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors

typed_iterator<child>() :
m_iterator(),
m_end() {}
typed_iterator<child>( const typed_iterator<child> &src ) :
m_iterator( src.m_iterator ),
m_end( src.m_end ) {}
typed_iterator<child> &operator=( const typed_iterator<child> &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
m_end = src.m_end;
}
return *this;
}
~typed_iterator<child>() {}
// Equality operator

bool operator==( const typed_iterator<child> &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const typed_iterator<child> &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
// Referencing operators

child* operator*()
{
return dynamic_cast<child*>( *m_iterator );
}
child** operator->()
{
return &**this;
}
// Increment/decrement operators

typename typed_iterator<child>& operator++();
typename typed_iterator<child> operator++(int)
{
typed_iterator<child> tmp = *this;
++*this;
return tmp;
}
private:
// Private constructor off a normal iterator

explicit typed_iterator<child>( const container_iterator &iter,
const container_iterator &end );
// Internal storage is a normal iterator

container_iterator m_iterator;
container_iterator m_end;
};
template <typename child>
typename typed_iterator<child> begin_typed()
{
return typed_iterator<child>( m_children.begin(), m_children.end() );
}
template <typename child>
typename typed_iterator<child> end_typed()
{
return typed_iterator<child>( m_children.end(), m_children.end() );
}
// Rest of class definition

};

template <typename T>
template <typename child>
typename CGenericTree<T>::typed_iterator<child>&
CGenericTree<T>::typed_iterator<child>::operator++()
{
++m_iterator;
// Now increment until we either get the correct type or reach the end

while ( m_iterator != m_end && !dynamic_cast<child*>( *m_iterator ) )
++m_iterator;
return *this;
}

template <typename T>
template <typename child>
CGenericTree<T>::typed_iterator<child>::typed_iterator(
const container_iterator &iter, const container_iterator &end ) :
m_iterator( iter ),
m_end( end )
{
// Now increment until we either get the correct type or reach the end

while ( m_iterator != m_end && !dynamic_cast<CHILD*>( *m_iterator ) )
++m_iterator;
}```

The deep iterator:

```template <typename T>
class CGenericTree
{
// Typed deep iterator

template <typename child>
class typed_deep_iterator
{
friend class CGenericTree<T>;
public:
// Normal constructors and destructors

typed_deep_iterator<child>() : m_iterator( NULL ), m_end( NULL ) {}
typed_deep_iterator<child>( const typed_deep_iterator<child> &src ) :
m_iterator( src.m_iterator ), m_end( src.m_end ) {}
typed_deep_iterator<child>
&operator=( const typed_deep_iterator<child> &rhs )
{
if ( this != &rhs )
{
m_iterator = rhs.m_iterator;
m_end = rhs.m_end;
}
return *this;
}
~typed_deep_iterator<child>()
{
m_iterator = NULL;
m_end = NULL;
}
// Equality operator

bool operator==( const typed_deep_iterator<child> &rhs ) const
{
return m_iterator == rhs.m_iterator;
}
bool operator!=( const typed_deep_iterator<child> &rhs ) const
{
return m_iterator != rhs.m_iterator;
}
// Referencing operators

child* operator*()
{
return dynamic_cast<child*>( m_iterator );
}
child** operator->()
{
return &**this;
}
// Increment operators

typed_deep_iterator<child>& operator++()
{
increment();
while( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
increment();
return *this;
}
typed_deep_iterator<child> operator++(int)
{
typed_deep_iterator tmp = *this;
++*this;
return tmp;
}
private:
// Private constructor off a pointer

explicit typed_deep_iterator<child>( T *src, T *end ) :
m_iterator( src ), m_end( end )
{
while ( m_iterator != m_end && !dynamic_cast<child*>( m_iterator ) )
increment();
}
// Private increment operator

void increment()
{
if ( m_iterator )
m_iterator = m_iterator->GetNext();
}
// Internal storage is simply a pointer

T* m_iterator;
T* m_end;
};
template < typename child>
typename typed_deep_iterator<child> begin_deep_typed()
{
return typed_deep_iterator<child>( static_cast<T*>(this), end_val() );
}
template <typename child>
typename typed_deep_iterator<child> end_deep_typed()
{
return typed_deep_iterator<child>( end_val(), end_val() );
}
// Rest of class definition

};```

This code demonstrates iterating over the children of the node `head` only returning nodes of type `CNodeDerived1`.

```CNodeBase::typed_iterator<CNodeDerived1> iter =
for ( ; iter != head->end_typed<CNodeDerived1>(); ++iter )
cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;
```

The next example does the same but uses deep iteration:

```CNodeBase::typed_deep_iterator<CNodeDerived1> iter =
for ( ; iter != head->end_deep_typed<CNodeDerived1>(); ++iter )
cout << (*iter)->GetId() << " " << (*iter)->GetType() << endl;
```

## Points of Interest

A few quick points to note. The first is the syntax required for templates defined inside templates. This fooled me for a while as I wrote this class. Especially, the syntax when you are defining the function bodies outside the class. I specifically wrote some functions outside the class definition in the `typed_iterator` to demonstrate this point. Note the fact that you have to use the `template <typename T>` syntax twice. Once for the outer class and once for the inner class. Once you realize that, the rest makes sense.

The second point to note is the use of the member function template in order to generate the necessary begin and end functions to work with the typed iterators. This again has some oddities with the syntax, most notably the fact that, in use, you have to specify the template argument (unlike most other function templates). This is due to the fact that the begin and end functions differ from each other only in return type, so the static polymorphism of the compiler cannot resolve the correct one. In use, you would do

```iter =
begin<MyType>()```
.

The more astute reader will notice that the typed iterator can be used as a standard shallow or deep iterator simply by passing in the base type as the template parameter. At first glance, this appears wasteful; however, there is a way to more efficiently implement this using explicit template instantiation. I will not go through the detail here, unless there are specific requests from any readers.

## History

• 6 Oct 04 : Version 1 released.
• 10 Oct 04 : Version 2 released to resolve crash in remove functions.

A list of licenses authors might use can be found here

## Share

 Web Developer United Kingdom
I started programming on 8 bit machines as a teenager, writing my first compiled programming language before I was 16. I went on to study Engineering and Computer Science at Oxford University, getting a first and the University Prize for the best results in Computer Science. Since then I have worked in a variety of roles, involving systems management and development management on a wide variety of platforms. Now I manage a software development company producing CAD software for Windows using C++.

My 3 favourite reference books are: Design Patterns, Gamma et al; The C++ Standard Library, Josuttis; and Computer Graphics, Foley et al.

Outside computers, I am also the drummer in a band, The Unbelievers and we have just released our first album. I am a pretty good juggler and close up magician, and in my more insane past, I have cycled from Spain to Eastern Turkey, and cycled across the Namib desert.

## You may also be interested in...

 Pro

 First Prev Next
 How can I use this in VC++ 6.0 ? khroh8-May-05 23:52 khroh 8-May-05 23:52
 Re: How can I use this in VC++ 6.0 ? Dave Handley13-May-05 11:56 Dave Handley 13-May-05 11:56
 Good stuff! Don Clugston7-Oct-04 14:34 Don Clugston 7-Oct-04 14:34
 Re: Good stuff! Dave_H7-Oct-04 21:02 Dave_H 7-Oct-04 21:02
 Don, Thanks for the rating. To cover your points: 1. 'Your method at least restricts the casts to a single location.' - that was my whole idea - glad you like it. 2. 'I think you mean "member template function". ' - the ANSI C++ standard refers to member function templates. Essentially they are simply saying that a function template can be the member of a class. If you turn around the reference to be member template function then you could be refering to a function that is the member of a template. It doesn't really matter though so long as everyone understands you. 3. 'We cannot rely on the user comparing against end() ' - Essentially the problem is stopping the `operator++` falling off the end of the list looking for something of the correct type. Obviously your standard loop when iterating over a list looks something like: ```for ( iter = container.begin(); iter != end(); ++iter ) // Do something``` The comparison against `end()` is fine for terminating the list, the the increment also needs to know about the end. As far as I can see there are 2 ways to do this. One is to carry around the `end()` iterator, the second would be to flag the iterator as being about to end by looking ahead during the `operator!=`. The problem with the latter method is that it will restrict the ways you can use the not equals operator. Also, carrying around `end()` was the only way I could think of doing all the operations in constant time. There are restrictions on the use of algorithms, but this is only similar to the `std::vector`. In `std::vector` if you insert an extra element during iteration, you invalidate the iterators. This is because the `std::vector` can reallocate storage at any time. My typed iterator will also invalidate the iterators in the event of any change in container size, but this time because `end()` has changed. Your restrictions on algorithms include, for example, the fact that you can't to a typed `insert` - but that wouldn't really make sense anyway. Thanks again... Dave
 Re: Good stuff! okigan14-Oct-04 21:05 okigan 14-Oct-04 21:05
 Re: Good stuff! Dave Handley14-Oct-04 22:04 Dave Handley 14-Oct-04 22:04
 Re: Good stuff! okigan14-Oct-04 22:42 okigan 14-Oct-04 22:42
 Re: Good stuff! Dave Handley8-Oct-04 3:52 Dave Handley 8-Oct-04 3:52
 Re: Good stuff! Don Clugston10-Oct-04 13:55 Don Clugston 10-Oct-04 13:55
 Re: Good stuff! Dave Handley10-Oct-04 14:13 Dave Handley 10-Oct-04 14:13
 Last Visit: 31-Dec-99 18:00     Last Update: 29-Apr-17 11:29 Refresh 1