This chapter presents the concept of iterators in detail, defining and illustrating the five iterator categories of input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators.

Overview of Iterators library

This chapter describes the components used in C++ programs to perform iterations for container classes, streams and stream buffers.

The chapter is constructed in the following sub sections.

• "24.1 Requirements"

¯ "24.1.1 Input Iterators"

¯ "24.1.2 Output Iterators"

¯ "24.1.3 Forward Iterators"

¯ "24.1.4 Bidirectional Iterators"

¯ "24.1.5 Random Access Iterators"

"24.2 Header <iterator>" "24.3 Iterator Primitives"

¯ "24.3.1 Iterator Traits"

¯ "24.3.2 Basic Iterator"

¯ "24.3.3 Standard Iterator Tags"

"24.4 Predefined Iterators"

¯ "24.4.1 Reverse iterators"

¯ "24.4.2 Insert Iterators"

"24.5 Stream Iterators"

¯ "24.5.1 Template Class Istream_iterator"

¯ "24.5.2 Template Class Ostream_iterator"

¯ "24.5.3 Template Class Istreambuf_iterator"

¯ "24.5.4 Template Class Ostreambuf_iterator"

24.1 Requirements

Iterators are a generalized pointer that allow the C++ program to work with various containers in a unified manner.

All iterators allow the dereference into a value type.

Since iterators are an abstraction of a pointer all functions that work with regular pointers work equally with regular pointers.

24.1.1 Input Iterators

There are requirements for input iterators, this manual, does not attempt to list them all.

Algorithms on input iterators should never attempt to pass through the same iterator more than once.

24.1.2 Output Iterators

There are requirements for output iterators, this manual, does not attempt to list them all.

An output iterator is assignable.

24.1.3 Forward Iterators

Forward iterators meet all the requirements of input and output iterators.

There are requirements for forward iterators, this manual, does not attempt to list them all.

24.1.4 Bidirectional Iterators

Bidirectional iterators meet the requirements of forward iterators.

There are requirements for forward iterators, this manual, does not attempt to list them all.

24.1.5 Random Access Iterators

Random access iterators meet the requirements of bidirectional iterators.

There are requirements for forward iterators, this manual, does not attempt to list them all.

24.2 Header <iterator>

The header iterator includes classes, types and functions used to allow the C++ program to work with various containers in a unified manner.

24.2 Header <iterator> Synopsis:

namespace std {
template<class Iterator> struct iterator_traits;
template<class T> struct iterator_traits<T*>;
template<class Category, class T, class Distance = ptrdiff_t,
	class Pointer = T*, class Reference = T&> struct iterator; 
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag: 
	public input_iterator_tag {};
struct bidirectional_iterator_tag: 
	public forward_iterator_tag {};
struct random_access_iterator_tag: 
	public bidirectional_iterator_tag {};
template <class InputIterator, class Distance>
	void advance(InputIterator& i, Distance n);
template <class InputIterator>
	typename iterator_traits<InputIterator>::difference_type 
	distance(InputIterator first, InputIterator last);

template <class Iterator> class reverse_iterator;
template <class Iterator> bool operator==(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator> bool operator<(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator> bool operator!=(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator> bool operator>(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator> bool operator>=(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator> bool operator<=(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator>
typename reverse_iterator<Iterator>::difference_type operator-(
	const reverse_iterator<Iterator>& x,
	const reverse_iterator<Iterator>& y);
template <class Iterator>
reverse_iterator<Iterator> operator+(
	typename reverse_iterator<Iterator>::difference_type n, 
	const reverse_iterator<Iterator>& x); 

template <class Container> class back_insert_iterator;
template <class Container> back_insert_iterator<Container>
	back_inserter(Container& x);

template <class Container> class front_insert_iterator;
template <class Container> front_insert_iterator<Container> 
	front_inserter(Container& x);

template <class Container> class insert_iterator;
template <class Container, class Iterator>
	insert_iterator<Container> inserter(Container& x, Iterator i);

template <class T, class charT = char, 
	class traits = char_traits<charT>, 
	class Distance = ptrdiff_t> class istream_iterator;

template <class T, class charT, class traits, class Distance>
bool operator==
	(const istream_iterator<T,charT,traits,Distance>& x,
	const istream_iterator<T,charT,traits,Distance>& y); 
template <class T, class charT, class traits, class Distance>
bool operator!=
	(const istream_iterator<T,charT,traits,Distance>& x,
	const istream_iterator<T,charT,traits,Distance>& y); 

template <class T, class charT = char, 
class traits = char_traits<charT> > class ostream_iterator;

template<class charT, class traits = char_traits<charT> >
class istreambuf_iterator;

template <class charT, class traits> bool operator==
	(const istreambuf_iterator<charT,traits>& a,
	const istreambuf_iterator<charT,traits>& b); 
template <class charT, class traits> bool operator!=
	(const istreambuf_iterator<charT,traits>& a,
	const istreambuf_iterator<charT,traits>& b); 
template <class charT, class traits = char_traits<charT> >
class ostreambuf_iterator;
}

24.3 Iterator Primitives

The library provides several classes and functions to simplify the task of defining iterators:.

24.3.1 Iterator Traits

To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types for a particular iterator type. Therefore, it is required that if iterator is the type of an iterator, then the types

  iterator_traits<Iterator>::difference_type   iterator_traits<Iterator>::value_type
  iterator_traits<Iterator>::iterator_category

are defined as the iterator's difference type, value type and iterator category, respectively.

In the case of an output iterator, the types

  iterator_traits<Iterator>::difference_type   iterator_traits<Iterator>::value_type

defined as void.

The template iterator_traits<Iterator> is specialized for pointers and for pointers to const

24.3.2 Basic Iterator

The iterator template may be used as a base class for new iterators.

Basic Iterator Synopsis:

namespace std {
template<class Category, class T, class Distance = ptrdiff_t,
class Pointer = T*, class Reference = T&> 
struct iterator {
typedef T value_type;
typedef Distance difference_type;
typedef Pointer pointer;
typedef Reference reference;
typedef Category iterator_category;
};
}

24.3.3 Standard Iterator Tags

The standard library includes category tag classes which are used as compile time tags for algorithm selection. These tags are used to determine the best iterator argument at compile time. These tags are:

  input_iterator_tag   output_iterator_tag
  forward_iterator_tag,
  bidirectional_iterator_tag
  random_access_iterator_tag
Iterator Tag Synopsis:

namespace std {
struct input_iterator_tag {};
struct output_iterator_tag {};
struct forward_iterator_tag
	: public input_iterator_tag {};
struct bidirectional_iterator_tag
	: public forward_iterator_tag {};
struct random_access_iterator_tag
	: public bidirectional_iterator_tag {};
}

24.3.4 Iterator Operations

Since only random access iterators provide plus and minus operators, the library provides two template functions for this functionality.

advance

Increments or decrements iterators.

Prototype:

template <class InputIterator, class Distance>

distance

Provides a means to determine the number of increments or decrements necessary to get from the beginning to the end.

Prototype:

template<class InputIterator>

difference_type distance

The distance from last must be reachable from first.

Return:

The the number of increments from first to last.

24.4 Predefined Iterators

The standard provides for two basic predefined iterators.

• "24.4.1 Reverse iterators"
• "24.4.2 Insert Iterators"

24.4.1 Reverse iterators

Both bidirectional and random access iterators have corresponding reverse iterator adaptors that they iterate through.

24.4.1.1 Template Class Reverse_iterator

A reverse_iterator must meet the requirements of a bidirectional iterator.

Template Class Reverse_iterator Synopsis:

Template class reverse_iterator
namespace std {
template <class Iterator>
class reverse_iterator : public 
	iterator<typename iterator_traits<Iterator>::iterator_category, 
		typename iterator_traits<Iterator>::value_type, 
		typename iterator_traits<Iterator>::difference_type, 
		typename iterator_traits<Iterator>::pointer, 
		typename iterator_traits<Iterator>::reference> { 
protected:
Iterator current;

public:
typedef Iterator
	iterator_type;
typedef typename iterator_traits<Iterator>::difference_type 
	difference_type; 
typedef typename iterator_traits<Iterator>::reference 
	reference; 
typedef typename iterator_traits<Iterator>::pointer 
	pointer; 

reverse_iterator();
explicit reverse_iterator(Iterator x);
template <class U> reverse_iterator
	(const reverse_iterator<U>& u); 

Iterator base() const; // explicit 
reference operator*() const; 
pointer operator->() const; 

reverse_iterator& operator++();
reverse_iterator operator++(int);
reverse_iterator& operator--();
reverse_iterator operator--(int);

reverse_iterator operator+ (difference_type n) const; *
reverse_iterator& operator+=(difference_type n);
reverse_iterator operator- (difference_type n) const;
reverse_iterator& operator-=(difference_type n);
reference operator[](difference_type n) const;
};

template <class Iterator> bool operator==(
	const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> bool operator<
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> bool operator!=
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> bool operator>
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 

template <class Iterator> bool operator>=
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> bool operator<=
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> 
typename reverse_iterator<Iterator>::difference_type operator-
	(const reverse_iterator<Iterator>& x, 
	const reverse_iterator<Iterator>& y); 
template <class Iterator> reverse_iterator<Iterator> operator+
	(typename reverse_iterator<Iterator>::difference_type n, 
	const reverse_iterator<Iterator>& x); 
} 

24.4.1.2 Reverse_iterator Requirements

Additional requirements may be necessary if random access operators are referenced in a way that requires instantiation.

Constructors

Creates an instance of a reverse_iterator object.

Prototype:

explicit reverse_iterator(Iterator x);

template <class U> reverse_iterator

base

The base operator is used for conversion.

Prototype:

Iterator base() const; // explicit 

The current iterator is returned.

Reverse_iterator operators

Common operators are provided for reverse_iterators.

Prototype:

reference operator*() const;

A reference iterator is returned.

Prototype:

pointer operator->() const;

A pointer to the dereferenced iterator.

Prototype:

reverse_iterator& operator++();

reverse_iterator operator++(int);

The this pointer is returned.

Prototype:

reverse_iterator& operator--();

reverse_iterator operator--(int);

The this pointer is returned.

Prototype:

reverse_iterator operator+

The reverse_iterator representing the result of the operation is returned.

Prototype:

reverse_iterator& operator+=

The reverse_iterator representing the result of the operation is returned.

Prototype:

iterator operator-

The reverse_iterator representing the result of the operation is returned.

Prototype:

reverse_iterator& operator-=

The reverse_iterator representing the result of the operation is returned.

Prototype:

reference  operator[] 

An element access reference is returned.

Prototype:

template <class Iterator>bool operator==

A bool true value is returned if the iterators are equal.

Prototype:

template <class Iterator> bool operator<

A bool true value is returned if the first iterator is less than the second.

Prototype:

template <class Iterator> bool operator!=

A bool true value is returned if the first iterator is not equal to the second.

Prototype:

template <class Iterator> bool operator>

A bool true value is returned if the first iterator is greater than the second.

Prototype:

template <class Iterator> bool operator>=

The reverse_iterator representing the result of the operation is returned.

Prototype:

template <class Iterator> bool operator<=

The reverse_iterator representing the result of the operation is returned.

Prototype:

template <class Iterator>

typename reverse_iterator<Iterator>

::difference_type operator-

The reverse_iterator representing the result of the operation is returned.

Prototype:

template <class Iterator>

The reverse_iterator representing the result of the operation is returned.

24.4.2 Insert Iterators

Insert iterators, are provided to make it possible to deal with insertion in the same way as writing into an array.

24.4.2.1 Class Back_insert_iterator

A back_insert_iterator inserts at the back.

Template Class Back_insert_iterator Synopsis:

namespace std {
template <class Container>
class back_insert_iterator : 
	public iterator<output_iterator_tag,void,void,void,void> { 
protected:
Container* container;

public:
typedef Container container_type;
explicit back_insert_iterator(Container& x);
back_insert_iterator<Container>&operator=
	(typename Container::const_reference value); 
back_insert_iterator<Container>& operator*();
back_insert_iterator<Container>& operator++();
back_insert_iterator<Container> operator++(int);
};
template <class Container> back_insert_iterator<Container>
	back_inserter(Container& x);
}

Constructors

Constructs a back_insert_iterator object.

Prototype:

explicit back_insert_iterator(Container& x);

Operator =

An operator is provided for copying a const_reference value.

Prototype:

back_insert_iterator<Container>& operator=

A reference to the copied back_insert_iterator is returned.

Back_insert_iterator Operators

Several standard operators are provided for Back_insert_iterator.

Prototype:

back_insert_iterator<Container>& operator*();

The dereference iterator is returned.

Prototype:

back_insert_iterator<Container>& operator++();

back_insert_iterator<Container> operator++(int);

The incremented iterator is returned.

back_inserter

Provides a means to get the back iterator.

Prototype:

template <class Container> 
back_insert_iterator<Container> back_inserter

The back_insert_iterator is returned.

24.4.2.3 Template Class Front_insert_iterator

A front_insert_iterator inserts at the front.

Template Class Front_insert_iterator Synopsis:

namespace std {
template <class Container>
class front_insert_iterator : 
public iterator<output_iterator_tag,void,void,void,void> { 
protected:
Container* container;
public:
typedef Container container_type;
explicit front_insert_iterator(Container& x);
front_insert_iterator<Container>& operator=
	(typename Container::const_reference value); 
front_insert_iterator<Container>& operator*();
front_insert_iterator<Container>& operator++();
front_insert_iterator<Container> operator++(int);
};
template <class Container>
front_insert_iterator<Container> front_inserter(Container& x);
} 

Constructors

Creates a front_insert_iterator object.

Prototype:

explicit front_insert_iterator(Container& x);

Operator =

Assigns a value to an already create assignment operator.

Prototype:

front_insert_iterator<Container>& operator=

A front_insert_iterator copy of the const_reference value is returned.

Front_insert_iterator operators

Several common operators are provided for the front_insert_iterator class.

Prototype:

front_insert_iterator<Container>& operator*();

A this pointer is returned.

Prototype:

front_insert_iterator<Container>& operator++();

front_insert_iterator<Container> operator++(int);

A post or pre increment operator.

Return:

The this pointer.

front_inserter

Provides a means to get the front iterator.

Prototype:

template <class Container>

front_inserter(Container& x);

The front_insert_iteraor is returned.

24.4.2.5 Template Class Insert_iterator

A bidirectional insertion iterator.

Template Class Insert_iterator Synopsis:

namespace std {
template <class Container>
class insert_iterator : 
public iterator<output_iterator_tag,void,void,void,void> { 
protected:
Container* container;
typename Container::iterator iter;

public:
typedef Container container_type;
insert_iterator(Container& x, typename Container::iterator i);
insert_iterator<Container>& operator=
	(typename Container::const_reference value); 
insert_iterator<Container>& operator*();
insert_iterator<Container>& operator++();
insert_iterator<Container>& operator++(int);
};
template <class Container, class Iterator>
	insert_iterator<Container> 
inserter(Container& x, Iterator i);
}

Constructors

Creates an instance of an insert_iterator object.

Prototype:

insert_iterator

operator =

An operator for assignment of a const_reference value.

Prototype:

insert_iterator<Container>& operator=

A copy of the insert_iterator.

Insert_iterator Operators

Various operators are provided for an insert_iterator.

Prototype:

insert_iterator<Container>& operator*();

The dereferenced iterator is returned.

Prototype:

insert_iterator<Container>& operator++();

insert_iterator<Container>& operator++(int);

The this pointer is returned.

inserter

Provides a means to get the iterator.

Prototype:

template <class Container, class Inserter>

insert_iterator<Container> inserter

The inserter iterator is returned.

24.5 Stream Iterators

Input and output iterators are provided to make it possible for algorithmic templates to work directly with input and output streams.

24.5.1 Template Class Istream_iterator

An istream_iterator reads (using operator>>) successive elements from the input stream. It reads after it is constructed, and every time the increment operator is used.

If an end of stream is reached the iterator returns false.

Since istream iterators are not assignable istream iterators can only be used for one pass algorithms.

Template Class Istream_iterator Synopsis:

namespace std {
template <class T, class charT = char, class traits = char_traits<charT>, 
class Distance = ptrdiff_t>
class istream_iterator:
public iterator<input_iterator_tag,
	T, Distance, const T*, const T&> {
public:
typedef charT char_type
typedef traits traits_type;
typedef basic_istream<charT,traits> istream_type;

istream_iterator();
istream_iterator(istream_type& s);
istream_iterator
	(const istream_iterator<T,charT,traits,Distance>& x);
~istream_iterator();

const T& operator*() const;
const T* operator->() const;
istream_iterator<T,charT,traits,Distance>& operator++();
istream_iterator<T,charT,traits,Distance> operator++(int);

private:
//basic_istream<charT,traits>* in_stream; exposition only 
//T value; exposition only 
};
template <class T, class charT, class traits, class Distance>
bool operator==
	(const istream_iterator<T,charT,traits,Distance>& x,
	const istream_iterator<T,charT,traits,Distance>& y); 
template <class T, class charT, class traits, class Distance>
bool operator!=
	(const istream_iterator<T,charT,traits,Distance>& x,
	const istream_iterator<T,charT,traits,Distance>& y); 
}

Constructors

Creates and object of an istream_iterator object.

Prototype:

istream_iterator();

istream_iterator(istream_type& s);

istream_iterator

The parameterless iterator is the only legal constructor for an end condition.

destructor

Removes an instance of an istream_iterator.

Prototype:

~istream_iterator();

24.5.1.2 Istream_iterator Operations

Prototype:

const T& operator*() const;

A dereferenced iterator is returned.

Prototype:

const T* operator->() const;

The address of a dereferenced iterator is returned.

Prototype:

istream_iterator

istream_iterator

The this pointer is returned.

Prototype:

template <class T, class charT, 

class traits, class Distance> bool operator==

A bool true value is retuned if the arguments ate the same.

24.5.2 Template Class Ostream_iterator

The ostream_iterator writes (using operator<<) successive elements onto the output stream.

Template Class Ostream_iterator Synopsis:

namespace std {
template <class T, 
	class charT = char, class traits = char_traits<charT> > 
class ostream_iterator:
public iterator<output_iterator_tag, void, void, void, void> {
public:
typedef charT char_type;
typedef traits traits_type;
typedef basic_ostream<charT,traits> ostream_type;

ostream_iterator(ostream_type& s);
ostream_iterator(ostream_type& s, const charT* delimiter);
ostream_iterator(const ostream_iterator<T,charT,traits>& x);
~ostream_iterator();

ostream_iterator<T,charT,traits>& operator=(const T& value);
ostream_iterator<T,charT,traits>& operator*();
ostream_iterator<T,charT,traits>& operator++();
ostream_iterator<T,charT,traits>& operator++(int);

private:
// basic_ostream<charT,traits>* out_stream; exposition only 
// const char* delim; exposition only 
};
} 

Constructors

Creates and instance of an ostream_iterator object.

Prototype:

ostream_iterator(ostream_type& s);

ostream_iterator

ostream_iterator(const ostream_iterator& x);

destructor

Removes and instance of an ostream_iterator object.

Prototype:

~ostream_iterator();

24.5.2.2 Ostream_iterator Operations

Prototype:

ostream_iterator& operator=(const T& value);

Returns a value to an ostream iterator.

Prototype:

ostream_iterator& operator*();

The dereference iterator is returned.

Prototype:

ostream_iterator& operator++();

ostream_iterator& operatot++(int);

The this pointer is returned.

24.5.3 Template Class Istreambuf_iterator

The istreambuf_iterator reads successive characters from the istreambuf object for which it was constructed.

An istream_iterator can only be used for a one pass algorithm.

Template Class Istreambuf_iterator Synopsis:

namespace std {
template<class charT, class traits = char_traits<charT> >
class istreambuf_iterator
	: public iterator<input_iterator_tag, charT, 
typename traits::off_type, charT*, charT&> { 
public:
typedef charT char_type;
typedef traits traits_type;
typedef typename traits::int_type int_type;
typedef basic_streambuf<charT,traits> streambuf_type;
typedef basic_istream<charT,traits> istream_type;

class proxy; // exposition only 

public:
istreambuf_iterator() throw();
istreambuf_iterator(istream_type& s) throw();
istreambuf_iterator(streambuf_type* s) throw();
istreambuf_iterator(const proxy& p) throw();

charT operator*() const;
istreambuf_iterator<charT,traits>& operator++();
proxy operator++(int);
bool equal(istreambuf_iterator& b);
private:

streambuf_type* sbuf_; exposition only
};

template <class charT, class traits> bool operator==
	(const istreambuf_iterator<charT,traits>& a,
	const istreambuf_iterator<charT,traits>& b); 
template <class charT, class traits> bool operator!=
	(const istreambuf_iterator<charT,traits>& a,
	const istreambuf_iterator<charT,traits>& b); 
}

Constructors

An overloaded constructor is provided for creation of an istreambuf_iterator object.

Prototype:

istreambuf_iterator() throw();

istreambuf_iterator

istreambuf_iterator

istreambuf_iterator(const proxy& p) throw();

Istreambuf_iterator Operators

Prototype:

charT operator*() const

A dereferenced character type is returned.

Prototype:

istreambuf_iterator<charT,traits>&

istreambuf_iterator<charT,traits>::operator++();

The this pointer is returned.

Prototype:

template <class charT, class traits> 

bool operator==

True is returned if the arguments are equal.

Prototype:

template <class charT, class traits> 

bool operator!=

True is returned if the arguments are not equal.

equal

An equality comparison.

Prototype:

bool equal(istreambuf_iterator<charT,traits>& b);

Return:

True is returned if the arguments are equal.

24.5.4 Template Class Ostreambuf_iterator

The ostreambuf_iterator writes successive characters to the ostreambuf object for which it was constructed.

Template Class Ostreambuf_iterator Synopsis:

namespace std {
template <class charT, class traits = char_traits<charT> >
class ostreambuf_iterator:
public iterator<output_iterator_tag, void, void, void, void> {
public:
typedef charT char_type;
typedef traits traits_type;
typedef basic_streambuf<charT,traits> streambuf_type;
typedef basic_ostream<charT,traits> ostream_type;

public:
ostreambuf_iterator(ostream_type& s) throw();
ostreambuf_iterator(streambuf_type* s) throw();
ostreambuf_iterator& operator=(charT c);
ostreambuf_iterator& operator*();
ostreambuf_iterator& operator++();
ostreambuf_iterator& operator++(int);

bool failed() const throw();

private:
streambuf_type* sbuf_; exposition only
};
}

Constructors

The constructor is overloaded for creation of an ostreambuf_iterator object.

Prototype:

ostreambuf_iterator(ostream_type& s) throw();

ostreambuf_iterator(streambuf_type* s) throw();

Ostreambuf_iterator Operators

Prototype:

ostreambuf_iterator<charT,traits>& 

The result of the assignment is returned.

Prototype:

ostreambuf_iterator<charT,traits>& operator*();

The dereferenced ostreambuf_iterator is returned.

Prototype:

ostreambuf_iterator<charT,traits>& operator++();

ostreambuf_iterator<charT,traits>& 
operator++(int);

The this pointer is returned.

failed

Reports a failure in writing.

Prototype:

bool failed() const throw();

The bool false value is returned if a write failure occurs.