next up previous contents
Next: Appendix C: Cell Properties of Up: 4 Applied Concepts Previous: Appendix A: Common Mathematical Terms

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:

and by the traversal hierarchy:

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 TR112.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:

\begin{lstlisting}[frame=lines,label=,title={Separated iteration and data access...
++it; //iteration
bool value = pm(*it); //data access

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.


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

next up previous contents
Next: 13. Cell Properties of Up: 4 Applied Concepts Previous: 11. Common Mathematical Terms

R. Heinzl: Concepts for Scientific Computing