2.10.0
Freundlich's C++ toolkit
Classes | Typedefs | Functions
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:

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:

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:

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;
typedef
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
>
iterator_types;

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}
{}
operator*() const
{
return *ptr_;
}
void
increment()
{
++ptr_;
}
bool
equal(my_iterator const &_other) const
{
return ptr_ == _other.ptr_;
}
void
decrement()
{
--ptr_;
}
void
advance(difference_type const _distance)
{
ptr_ += _distance;
}
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:

std::array<int,3> array{{1,2,3}};
my_iterator start(&*array.begin());
my_iterator it{start};
++it;
*it = 5;
// Array is now {1,5,3}
// Prints 5
std::cout << array[1] << '\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. More...
 

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. More...
 
template<typename Iterator >
fcppt::iterator::range< Iterator > fcppt::iterator::make_range (Iterator const _begin, Iterator const _end)
 Makes an iterator range. More...
 

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
CategoryMust be one of the std:: iterator category classes.
CategoryRefMust 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.