DGtal  1.5.beta
Iterators and ranges

Table of Contents

Author(s) of this documentation:
Tristan Roussillon

This part of the manual describes basic concepts of iterators and ranges. It also presents several tools available in DGtal to ease their use: traits class, useful functions, adapters, etc.

DGtal users usually have to play with ranges to iterate over finite sets of elements.

Introduction to iterators

The concept of iterator is one of the main concept introduced in the STL in order to make data structures and algorithms independent: a programmer would be able to apply one algorithm on different data structures. Algorithms typically take iterators as arguments, so a data structure is only required to provide a way to access its elements using iterators. An iterator is any object that, pointing to some element stored in a data structure, can be incremented so that it points to the next element. An iterator has at least, the dereference (*) and increment (++) operators, but can have more operators to implement extra functionalities. Depending on the functionality they implement,
they belong to one of the several categories of iterators.
Following The Boost.Iterator Library, which extends the hierarchy of concepts proposed in the STL and separates access and traversal functionalities, we consider in DGtal the following access and traversal categories:

  • Readable iterator: *i returns an instance of V (value type) and i->m is equivalent to (*i).m
  • Writable iterator: *i = o
  • LValue iterator: *i returns an instance of V&
  1. Incrementable iterator: dereference (*), indirection (->) and increment (++) operators.
  2. Single-pass iterator: equality operators (== and !=).
  3. Forward iterator: default constructor.
  4. Bidirectional iterator: decrement (--) operator.
  5. Random access iterator: arithmetic and comparison operators (<, <=, >, >=).

Each traversal category of level l obviously implements the functionalities of all the categories k < l and one or more extra functionalities. For each category, the main difference with the previous categories is provided in the above list, but The Boost.Iterator Library gives more details.

The following diagram sums up the main iterator concepts:

Introduction to ranges

A range of elements stored in a data structure (container) may be implicitly described by a well-chosen pair of iterators. Any pair does not define a valid range, even with iterators having nonsingular values. An iterator j is reachable from an iterator i if and only if i can be made equal to j with finitely many applications of the increment operator. If j is reachable from i, one can iterate over the range bounded by i and j, from the one pointed to by i and up to, but not including, the one pointed to by j. Such a range is valid and is denoted by [i,j).

In linear data structures, any iterator pointing to the last element is incremented so that it points to the past-the-end element, ie. it points past the last element (just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array).

If an iterator begin points to the first element of a data structure and an iterator end points to the past-the-end element, iterating over the range [begin,end) is a way of iterating over all the elements of the underlying data structure. Note that if the underlying data structure is empty, it only has a past-the-end element. As a consequence, a range [i,i) denotes an empty range.
A range of a linear data structure is illustrated below (normal values are depicted with a small straight segment, whereas the past-the-end value is depicted with a cross). In this example, [i,j) is not a valid range because j cannot be reached from i and the whole range may be denoted by [begin,end).

Linear range

Main concepts

Some objects have the capability to provide a pair of iterators describing a (valid) range. For instance, methods begin() and end() of STL containers return two iterators bounding the range of elements contained in the data structure. Similarly, in DGtal, there are several concepts of range having at least these begin() and end() methods.

The concept CConstSinglePassRange describes any object for which, one can iterate at least one time over a range of elements.
Models of concepts::CConstSinglePassRange have a nested type ConstIterator, which is a readable and (at least) single-pass iterator.
Instances of ConstIterator are returned by begin() and end() methods.

The concept CConstBidirectionalRange, which is a refinement of concepts::CConstSinglePassRange, describes any collection of elements that can be scanned several times, either forward or backward.
Models of this concept have obviously a nested type ConstIterator, but it is a readable and (at least) bidirectional iterator. They have in addition a nested type ConstReverseIterator, which is a readable and bidirectional iterator too. Finally, begin() and end() methods return instances of ConstIterator, whereas rbegin() and rend() methods return instances of ConstReverseIterator.

The concept CSinglePassRange (resp. CBidirectionalRange) is a refinement of concepts::CConstSinglePassRange (resp. concepts::CConstBidirectionalRange) for not constant, mutable elements. All their models have a nested type Iterator (resp. ReverseIterator), which are the readable and writable counterparts of ConstIterator (resp. ConstReverseIterator).

These four concepts and their links are depicted in the following figure:

Adapters to iterators

In DGtal, several adapters to iterators are provided.

Reverse iterator

Any bidirectional iterator may have a reverse counterpart, ie. an adapter that enables a backward scanning by calling the decrement operator instead of the increment operator and conversely. Bidirectional ranges provide reverse iterators that can be used as follows: 

template<typename Range>
void anyProcedure(const Range& aRange)
  {
    BOOST_CONCEPT_ASSERT(( concepts::CBidirectionalRange<Range> )); 
    ...
    for (typename Range::ReverseIterator ri = r.rbegin(), 
         typename Range::ReverseIterator riEnd = r.rend(); 
         ri != riEnd; ++ri)
      {
         ...
      }
   }

In order to take profit of the whole DGtal framework, you should use DGtal::ReverseIterator instead of std::reverse_iterator or even boost::reverse_iterator. 

#include "DGtal/base/ReverseIterator.h"
...
template<typename Iterator>
void anyProcedure(const Iterator& anIterator)
  {
    ...
    DGtal::ReverseIterator<Iterator> ri(anIterator); 
    ASSERT( ri.base() == anIterator ); //ie. anIterator is the underlying iterator of ri
    ...
  }
Note
Reverse iterators are a little tricky because *ri == *--ri.base() (or equivalently *++ri == *ri.base()), so that when an iterator is reversed, the reversed version does not point to the same element in the range, but to the one preceding it.
Developer trick: there is no erase or insert method taking a reverse iterator as input argument in STL containers. Static methods are provided to do that in a small struct called OpInSTLContainers.

On-line transformations

DGtal also provides adapters to iterators that transforms the data returned by the dereference (and indirection) operator into other data, possibly of different type. The transformation is delegated to a functor. Dereferencing any adapted iterator consists in applying the functor on the data to which points the underlying iterator: 

#include "DGtal/base/ConstIteratorAdapter.h"
...
template<typename Iterator, typename Functor, typename ReturnType>
void anyProcedure(const Iterator& anIterator, const Functor& aFunctor)
  {
    ...
    DGtal::ConstAdapterIterator<Iterator, Functor, ReturnType> a(i, f);
    ASSERT( *a == f(*i) ); //ie. *a and f(*i) return equivalent instances of ReturnType  
    ...
  }

The class ConstIteratorAdapter adapts any (at least) readable and (at least) incremental iterator with any functor, whereas the class IteratorAdapter adapts any readable, writable, Lvalue and (at least) incremental iterator.