fcppt.iterator

Description

Iterator adaptors and utilities.

Implementing iterators

There are five iterator categories. Each one dictates which operations an iterator needs to provide and what these operations mean:

• Input iterator: Defines a single-pass range that can only be read from.
• Output itereator: Defines a single-pass range that can only be written to.
• Forward iterator: Defines a range that consists of real objects, i.e. dereferencing an iterator yields a reference. Such an iterator can only be incremented. A forward iterator is also in input iterator.
• Bidirectional iterator: A forward iterator that can also be decremented.
• Random access iterator: A bidirectional iterator that supports random access.

Forward, bidirectional and random access iterators are also output iterators if they are not const iterators.

The standard library provides a tag type for each iterator category. std::random_access_iterator_tag derives from std::bidirectional_iterator_tag, which derives from std::forward_iterator_tag, which derives from std::input_iterator_tag. In this hierarchy, std::output_iterator_tag is not used, meaning that this tag only comes into play when an iterator is an output iterator only.

For each category, a multitude of operations need to be implemented, a lot of which can be implemented from other operations, which commonly leads to a lot of boiler-plate code. For example, operator!= can be implemented from operator==, and operator< (and <=,> and >=) can be implemented from operator- that calculates the distance of two random access iterators. However, you might want to provide fundamentally different implementations for all of these (for performance reasons), but this is very rare. To make implementing iterators easier, fcppt::iterator::base provides most operations using a default implementation, which the actual iterator type derives from. This class gets an fcppt::iterator::types as its template parameter, which consists of:

• The actual iterator type, which is the type deriving from fcppt::iterator::base.
• The reference type of the iterator, which is what operator* returns.
• The value_type, which is what users of the iterator can use to store a copy of a dereferenced object.
• The difference_type, which is used to calculate distances between two iterators. This is only significant for random access iterator. Usually, this is std::ptrdiff_t.
• The iterator_category.

Deriving from fcppt::iterator::base also inherits all of these typedefs. In addition, pointer is also defined which is always std::remove_reference<reference>::type *, i.e. for forward iterators it is T * if reference is T & and T const * if reference is T const & for some type T.

Let It be the type of the iterator we are going to implement, i.e. the type deriving from fcppt::iterator::base. The following operations need to be implemented by the derived class as public member functions:

• For Input iterator and output iterators:

  reference operator*() const	Returns the object at the current position.
  bool equal(It it) const	Returns true if *this and it point to the same position. For input and output iterators, this is only used to tell if they reached their end.
  void increment()	Moves the iterator to the next position.

• Forward iterators must provide the same operations as input iterators. In addition, they must have a default constructor and reference must be an actual reference type.
• Bidirectional iterators must provide the same operations as forward iterators. In addition, they must also provide:

  void decrement()

  Moves the iterator to the previous position. This operation is the inverse to void increment().

• Random access iterators must provide the same operations as bidirectional iterators. In addition, they must also provide:

  void advance(difference_type d)	Moves the iterator forwards (backwards if d is negative) by d positions. This must be equal to d increment operations (-d decrement operations if d is negative).
  difference_type distance_to(It it) const	The distance d of *this to it, meaning that if *this is moved forwards by d positions, then *this and it are equal.

Note

For random access iterators, we could define void increment() in terms of advance(1), void decrement() in terms of advance(-1) and bool equal_to(It it) const as distance_to(it) == 0. For the time being, this is not done so that the sets of operations to implement are consistent with the order of iterator categories.

Here is an example of how to implement a random access iterator which is also an output iterator. For simplicity, we implement a simple iterator using pointers over int. First, we declare the types we are going to use:

class my_iterator;
 
using iterator_types = fcppt::iterator::types<
    my_iterator, // The derived type
    int, // The value type
    int &, // The reference type, which is non const so the iterator is also an output iterator
    std::ptrdiff_t, // The difference type for pointers
    std::random_access_iterator_tag // The iterator category
    >;

Next, we derive from fcppt::iterator::base and implement all operations required for random access iterators:

class my_iterator : public fcppt::iterator::base<iterator_types>
{
public:
  // Random access iterators require a default constructor.
  my_iterator() : ptr_{nullptr} {}
 
  explicit my_iterator(pointer const _ptr) : ptr_{_ptr} {}
 
  [[nodiscard]] reference operator*() const { return *ptr_; }
 
  void increment() { ++ptr_; }
 
  [[nodiscard]] bool equal(my_iterator const &_other) const { return ptr_ == _other.ptr_; }
 
  void decrement() { --ptr_; }
 
  void advance(difference_type const _distance) { ptr_ += _distance; }
 
  [[nodiscard]] difference_type distance_to(my_iterator const &_other) const
  {
    return _other.ptr_ - ptr_;
  }
 
private:
  pointer ptr_;
};

Here is an example showing how our iterator can be used:

  fcppt::array::object<int, 3> array{1, 2, 3};
 
  my_iterator const start(&*array.begin());
 
  my_iterator it{start};
 
  ++it;
 
  *it = 0;
 
  // Array is now {1,5,3}
 
  // Prints 5
  std::cout << fcppt::array::get<1U>(array) << '\n';
 
  // Prints 1
  std::cout << (it - start) << '\n';

Classes
class	fcppt::iterator::base< Types >
	A template for implementing iterators. More...
class	fcppt::iterator::range< Iterator >
	A range formed from two iterators. More...
struct	fcppt::iterator::types< Derived, ValueType, Reference, DifferenceType, IteratorCategory >
	The types passed to fcppt::iterator::base. More...

Typedefs
template<typename Category , typename CategoryRef >
using	fcppt::iterator::category_at_least = std::is_base_of< CategoryRef, Category >
	Checks if an iterator category includes another.

Functions
template<typename Range >
fcppt::iterator::range< fcppt::container::to_iterator_type< Range > >	fcppt::iterator::adapt_range (Range &_range)
	Turns a range into an fcppt::iterator::range.
template<typename Iterator >
fcppt::iterator::range< Iterator >	fcppt::iterator::make_range (Iterator const _begin, Iterator const _end)
	Makes an iterator range.

Typedef Documentation

category_at_least

template<typename Category , typename CategoryRef >

using fcppt::iterator::category_at_least = typedef std::is_base_of<CategoryRef, Category>

Checks if an iterator category includes another.

Checks if Category models CategoryRef. For example, if Category is std::bidirectional_iterator_category and CategoryRef is std::forward_iterator_category, then the value is true.

Template Parameters

Category	Must be one of the std:: iterator category classes.
CategoryRef	Must be one of the std:: iterator category classes.

Function Documentation

adapt_range()

template<typename Range >

fcppt::iterator::range< fcppt::container::to_iterator_type< Range > > fcppt::iterator::adapt_range ( Range &  _range )

inline

Turns a range into an fcppt::iterator::range.

make_range()

template<typename Iterator >

fcppt::iterator::range< Iterator > fcppt::iterator::make_range ( Iterator const  _begin, Iterator const  _end  )

inline

Makes an iterator range.