CGAL 5.0 - Manual
|
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.
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:
and a partial specialization of iterator_traits
classes for pointers:
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:
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.
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:
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_iterator
s, back_insert_iterator
s and front_insert_iterator
s. The back_inserter_iterator
s are used to insert elements at the end of a container by using the push_back
member function of the container. Similarly, front_insert_iterator
s 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.
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
.
and this code will insert the points contained in the vector vertices
into a Delaunay triangulation data structure:
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:
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.
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.
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:
The following two macros are also defined as a generic means for iterating over either a linear or circular sequence:
See the chapter Handles and Circulators in the Support Library part of CGAL manual for more information and examples.
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:
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.
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:
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.