This talk has two parts. The first part presents the concept of complete traversal (CT), which for a given a container C (such as a set) is defined by the iteration scheme
where F is a function that might possibly modify C by inserting new elements into it. We assume that the order in which the elements are treated is not relevant, as long as the iteration continues until F has been applied to all of the elements currently in C, including those F has inserted. Standard iteration mechanisms, such as the iterators provided in the C++ Standard Template Library (STL), do not directly support complete traversals. We show generic solutions to the complete traversal problem by means of two generic algorithms and a container adaptor. We also discuss the complexity of these solutions, and their scope in terms of the class of containers they support. This part is based on a joint paper with Dave Musser and Eric Gamess published elsewhere.1for all x in C
F(x,C)
The second part of the talk addresses the question of how general this iteration scheme (CT) is. The way of approaching this question is by comparing the CT problem with well-known problems such as the computation of the transitive closure (TC) of a relation, and the computation of the closure of a set under a given relation (CR). We formally define the meaning of problem and the relation is an instance of among problems, to prove that TC and CR are indeed instances of the CT problem, and present a diagram which depicts the relation is an instance of among CT, TC, CR, and other well-known problems.