In software-library terminology, a container is a collection of elements of the same type. To provide highly efficient implementations of containers, data structures are often designed as nested hierarchies of components. We say that such data structures are compound. An iterator is an object that encapsulates a location within a data structure and provides mechanisms to move from one location to another. In this paper we describe various approaches and propose solution patterns for constructing iterators for compound data structures. Specifically, we have the following design goals in mind: time efficiency, space efficiency, exception safety, and configurability. We analyse the proposed approaches in use cases drawn from the CPH STL (Copenhagen Standard Template Library): compound iterators for static containers, bidirectional iterators for mergeable heaps, and random-access iterators for space-efficient vectors. The use cases clearly demonstrate that there are some interesting trade-offs between different design goals.

@unpublished{KM2013M,
  author = {Jyrki Katajainen and Andreas Milton Maniotis},
  title = {Conceptual frameworks for constructing iterators for compound data
    structures},
  howpublished = {Submitted for publication},
  year = {2013},
}