Appendix B: STL Iterator Analysis

The topological specification mechanisms of Section 5.1 and the separation properties of the fiber bundle concept are used to analyze the C++ STL iterator concept in detail. With the advent of the C++ STL the separation of access to data structures and algorithms by means of iterators has become one of the key elements for the generic programming paradigm. Thereby the implementation complexity of algorithms and data structures is significantly reduced. The value access requirements in existing iterator categories are given by:

output iterator	*iter = a
input iterator	*iter is convertible to T
forward iterator	*iter is T&
random access iterator	iter[n] is convertible to T

Here, iter represents the iterator and T the corresponding data type of the evaluated iterator. But unfortunately, it combines traversal and data access. An example of this problem of this iterator concept is, e.g., the well-known example of the std::vector<bool> which can actually be modeled by a random access container [110] due to the container data structure. But the return type is not bool& and can thereby only be modeled by the requirement of input and output iterators. An alternative approach was suggested [110] by separating traversal and access, where the access hierarchy is described by:

• Readable iterator
• Writable iterator
• Swappable iterator
• Lvalue iterator

and by the traversal hierarchy:

• Incrementable iterator
• Single Pass iterator
• Forward Traversal iterator
• Bidirectional Traversal iterator
• Random Access Traversal iterator

But up to now this concept is not widely used. The proposed new iterator concept [156] and another version [157] with a different focus on these problems, were accepted into the TR1^12.1 of C++. Additionally, the backward and forward compatibility of the new iterator categories are a major problem [158] and are not included in the new C++0x standard [159].

This concept is briefly illustrated in the following source snippet:

As explained in Section 5.1, there is a formal and distinguishable definition possible for all of these data structural properties. Based on this formal classification the combination of traversal and data access is analyzed in more detail. The following list gives an overview of the basic iterator traits [17] for the basic STL iterators:

iterator category	specification	property
input/output		data property
forward	local(2)	topological property
bidirectional	local(3)	topological property
random access	global	topological property

Problems are encountered if the new iterator categories [159] are integrated into the topological specification.

iterator category	specification	property
incrementable	local(2)	topological property
single pass		data property
forward	local(2)	data and topological property

The combinatorial property of the underlying space of these three categories is the same: a 0-cell complex with a local topological structure such as:

data structure	dimension	cell type	complex topology
single linked list / stream	0	simplex	local(2)

Only the incrementable property can be described by a topological property, whereas the other two categories are data-dependent. The former iterator properties [17] only use two different categories which specify the behavior of data, namely the input and output properties.

Footnotes

... TR1^12.1

Library Technical Report 1 (TR1) is a draft document specifying additions to the C++ Standard Library