Iterators, Circulators and Handles

Author

Mariette Yvinec (yvine.nosp@m.c@so.nosp@m.phia..nosp@m.inri.nosp@m.a.fr)

Iterators are a generalization of pointers that allow a programmer to work with different data structures (containers) in a uniform manner. An iterator is the glue that allows one to write a single implementation of an algorithm that will work for data contained in an array, a list or some other container - even a container that did not yet exist when the algorithm was implemented.

The concept of an iterator is one of the major tools of the genericity in STL. Iterators are used almost everywhere in the STL to achieve the communication between containers and algorithms. Iterators are widely used in CGAL too. CGAL extends the idea of the iterator, which works for linear data structures, to circular data structures by defining the concept of a circulator. Circulators are quite similar to iterators, with the major difference being the absence of a past-the-end position in a sequence. Note that circulators are NOT part of the STL, but of CGAL.

In CGAL, we also define the concept of handle,

which behaves roughly like a pointer to an object without an increment or decrement operation. More details about handles and their requirements can be found in the chapter Circulators and Handles of the Support Library part of CGAL manual. Section Handle, iterator, or circulator? below discusses when handles should be used in your code.

The concepts of iterators is relatively well described in textbooks such as Stroustrup's book (The C++ Programming Language [9]) and Austern's book (Generic Programming and the STL [2]) and in chapter Handles and Circulators of the Support Library part of the CGAL manual. which also presents the concepts of handles and circulators. Thus we will not give a full description of these concept here but only a few hints about how to use and write handle, iterators and circulators in CGAL. Developers should consult the above-mentioned references to become familiar with the iterator, circulator and handle concepts. In particular, the notions of iterator and circulator ranges, dereferencable and past-the-end values, mutable and constant iterators and circulators, and the different categories (forward, bidirectional, random-access, etc.) of iterators and circulators, are fundamental.

Iterator and circulator traits

Iterators and/or circulators are required to provide a set of types such as the value_type for the type of objects referred to by the iterator and circulator or the difference_type for the distance between two iterators or circulators. These types are usually declared in the iterator or circulator classes. The iterator traits have been introduced to attach such types to pointer classes, thus enabling the use of pointer classes as models of iterator and circulator concepts. Therefore, an algorithm using an iterator of the type Iter will find the relevant types in an instantiation of a small templated class iterator_traits.

There is a general templated version of iterator_traits that looks like:

template <class Iter> 
struct iterator_traits {
  typedef typename Iter::iterator_category  iterator_category ;
  typedef typename Iter::value_type         value_type;
  typedef typename Iter::difference_type    difference_type;
  typedef typename Iter::pointer            pointer;
  typedef typename Iter::reference          reference;
};

and a partial specialization of iterator_traits classes for pointers:

template <class T> 
struct iterator_traits<T*> {
  typedef random_access_iterator            iterator_category ;
  typedef T                                 value_type;
  typedef ptrdiff_t                         difference_type;
  typedef T*                                pointer;
  typedef T&                                reference;
};

Input and output iterators

Operator * for input and output iterators

The operator * of input and output iterators has a restricted semantics. Input iterators are designed for input operations, and it is not required that the value type T of an input iterator it be assignable. Thus, while assignments of the type t = *it are the usual way to get values from the input iterators, statements like *it = ... are likely to be illegal. On the other hand, output iterators are designed for write operations, and the only legal use of the operator * of an output iterator it is in the assignment *it = ..... The code of a standard copy function of the STL provides an example of both of these operations:

template< class InputIterator, class OutputIterator>
OutputIterator copy(InputIterator first, 
                    InputIterator last,
                    OutputIterator result) {
    while (first != last)
    {
        result = *first;
       ++first; 
       ++result;
    }
    return result;
}

The first two arguments of copy are of type InputIterator (meaning any type that fulfills the requirements for an input iterator) while the third one is of type OutputIterator. If these types were exchanged, then the statement *result = *first; might not be valid.

Stream iterators

STL provides a special type of input iterator called istream_iterator,

which is designed to be bound to an object of the class istream and provides a way to read a sequence of values from the input stream to which it is bound. For example, the following code reads numbers of type double from the standard input stream cin and computes their sum.

istream_iterator<double> it(cin);
istream_iterator<double> end();

double sum=0.0;
while(it != end) {
   sum += *it;
   ++it;
}
cout << sum << endl;

In a similar fashion, STL provides the type ostream_iterator,

which is designed to be bound to an object of the class ostream and used to output values to the output stream to which it is bound.

CGAL provides extensions of the classes istream_iterator and ostream_iterator. The class CGAL::Ostream_iterator<T,Stream> is an output iterator adaptor for the stream class Stream and value

type T. It provides output iterators that can be used to output values of type T to objects of the class Stream. For example, the following code fragment inserts a list of segments into a window stream (i.e., it draws the segments in the window) using the standard copy function:

typedef CGAL::Cartesian<double>   K;
typedef K::Segment_2              Segment;

std::vector<Segment>       segments;
Window_stream        W( 400, 400);

int main (int argc, char** argv)
{
  // initialize segments
  std::copy( segments.begin(),
             segments.end(),
             CGAL::Ostream_iterator< Segment, Window_stream>( W));
}

Likewise, the class CGAL::Istream_iterator<T,Stream> is an input iterator adaptor for the stream class Stream and value type T. These adaptors are particularly useful for stream classes that are similar to but not derived from std::istream and std::ostream. The only requirements of the stream classes are that they define operator>> (for Istream_iterator::value_type) and operator<< (for Ostream_iterator::value_type).

Insert iterators

Insert iterators are output iterators that can be used to insert items into containers. With regular iterator classes, the code given above for the copy function of STL, causes the range [first,last) to be copied into an existing range starting with result. No memory allocation is involved and the existing range is overwritten. With an insert iterator supplied as the third argument, the same code will cause elements to be inserted into the container with which the output iterator is associated. That is, new memory may be allocated for these inserted elements.

The STL provides three kinds of insert iterators: insert_iterators, back_insert_iterators and front_insert_iterators. The back_inserter_iterators are used to insert elements at the end of a container by using the push_back member function of the container. Similarly, front_insert_iterators are used to insert elements at the beginning of a container by using the container's push_front function. The general insert_iterator is used to insert elements at any point in a container, by using the container's insert member function and a provided location of the insertion.

For convenience, STL provides the templated functions (or adaptors) front_inserter,

back_inserter

and inserter to get insert iterators, also called inserters, from containers.

template<class Container, class Iterator> 
insert_iterators<Container> inserter(Container& c, Iterator it); 

template<class Container> 
back_insert_iterators<Container> back_inserter(Container& c); 

template<class Container> 
front_insert_iterators<Container> front_inserter(Container& c); 

Thus, the inserter adaptor can be called for any container that has an insert member function, and back_inserter (resp. front_inserter) can be called for any container that has a push_back (resp. push_front) member function.

The following code will insert 200 copies of the value 7 at the end of vec.

void g(vector<int>& vec)
{
    fill_n(std::back_inserter(vec),200,7);
}

and this code will insert the points contained in the vector vertices into a Delaunay triangulation data structure:

typedef CGAL::Cartesian<double>                          K;
typedef CGAL::Triangulation_euclidean_traits_2<K>        Gt;
typedef CGAL::Triangulation_vertex_base_2<Gt>            Vb;
typedef CGAL::Triangulation_face_base_2<Gt>              Fb;
typedef CGAL::Triangulation_default_data_structure_2<Gt,Vb,Fb>
                                                         Tds;
typedef CGAL::Delaunay_triangulation_2<Gt,Tds>           DT;

DT triangulation;

std::copy( vertices.begin(),
           vertices.end(),
           std::back_inserter( triangulation ));

Writing code with and for iterators, circulators, and handles

Because you should write generic code for CGAL, algorithms that require a sequence of data for input should be written to take an iterator (or circulator) range as input instead of, say, a particular container. Similarly, algorithms that compute a sequence of data as output should place the output data into an output iterator range. Both of these points are illustrated by the prototype of the following function that computes the convex hull of a set of points in two dimensions:

// generates the counterclockwise sequence of extreme points
// of the points in the range [first,beyond).
// The resulting sequence is placed starting at position
// result, and the past-the-end iterator for the resulting
// sequence is returned. It is not specified at which point the
// cyclic sequence of extreme points is cut into a linear sequence.
template <class InputIterator, class OutputIterator>
OutputIterator
convex_hull_points_2(InputIterator first, InputIterator beyond,
                     OutputIterator  result, const Traits & ch_traits );

Also, when writing container classes, you should be sure to provide iterators and/or circulators for the containers and design the interfaces so they can be used with generic algorithms from the STL and other CGAL algorithm. Here we give a few more details about how to accomplish these goals.

Handle, iterator, or circulator?

Handles are indirect references that do not move, so whenever you need a pointer-like reference to a single element of a data structure, and it is not necessary to iterate (or circulate), use a handle. In contrast, iterators should be used when you want to move (that is, iterate) over a linear sequences of elements. When the sequence is circular, prefer a circulator over an iterator.

Writing functions for iterators AND circulators

To make your code as generic as possible, you should, where appropriate, write functions that can accept either a circulator range or an iterator range to delimit the input values. Since empty circulator ranges are represented differently than empty iterator ranges, the following function is defined in <CGAL/circulator.h> so the test for an empty range can be done generically:

One would use this function in conjunction with a do-while loop as follows:

if ( ! CGAL::is_empty_range( i, j) )
{
  do
  { 
    // ...
  } while ( ++i != j )
}

The following two macros are also defined as a generic means for iterating over either a linear or circular sequence:

CGAL_For_all( ic1, ic2)

CGAL_For_all_backwards( ic1, ic2)

See the chapter Handles and Circulators in the Support Library part of CGAL manual for more information and examples.

Writing an iterator for your container

Every container class in CGAL should strive to be a model for the STL concept of a container. As for all concepts, this means that certain types and functions are provided, as detailed, for example in [2]. For the purposes of this discussion, the relevant types are:

iterator	type of iterator
const_iterator	iterator type for container with constant elements

and the relevant functions are:

iterator begin(); // beginning of container
const_iterator begin(); // beginning of container with constant elements
iterator end(); // past-the-end value for container
const_iterator end(); // past-the-end value for container with constant elements

Variations on the above names are possible when, for example, the container contains more than one thing that can be iterated over. See Section Naming scheme for more details about the naming conventions for iterators and their access functions.

Writing a circulator for your container

When a container represents a circular data structure (i.e., one without a defined beginning or end), one should provide circulators for the data elements in addition to (or, where appropriate, instead of) the iterators. This means that the following types should be defined:

circulator	type of circulator
const_circulator	circulator type for container with constant elements

as well as two access functions, one for each of the two types, with names that end in the suffix _circulator (Section Naming scheme ).

Requirements and recommendations

Requirements:

• All container classes should provide iterator types and access functions.

• All container classes that represent circular data structures should provide circulator types and access functions.

• Take care that decrement of the past-the-end value is, in accordance with the standard, a legal operation for a bidirectional iterator.

  This can, for example, be used to get the last element of a sequence.

Recommendations:

• Be aware that postincrement (respectively, postdecrement) is more expensive than preincrement (predecrement) since the iterator or circulator value must be copied in the former case.

• Remember that iterators and circulators are intended to be lightweight objects. That is, copying them should require only constant time.

• When writing a container-like structure, provide push_back, push_front, and insert member functions so all insert iterators can be used with your container.