______________________________________________________________________
24 Iterators library [lib.iterators]
______________________________________________________________________
1 This clause describes components that C++ programs may use to perform
iterations over containers (_lib.containers_), streams
(_lib.default.iostreams_), and stream buffers (_lib.stream.buffers_).
2 The following subclauses describe components for iterator tags
(_lib.iterator.tags_), predefined iterators (_lib.predef.iterators_),
stream iterators (_lib.stream.iterators_), and streambuf iterators
(_lib.streambuf.iterators_).
3 Headers:
--<stl iterators (TBD)>
4 Table 1:
Table 1--Header <stl iterators (TBD)> synopsis
+--------------------------------------------------------------------------+
| Type Name(s) |
+--------------------------------------------------------------------------+
|Template classes: |
|back_insert_iterator ostream_iterator |
|front_insert_iterator reverse_bidirectional_iterator |
|insert_iterator reverse_iterator |
|istream_iterator |
+--------------------------------------------------------------------------+
|Template structs: |
|bidirectional_iterator input_iterator |
|forward_iterator random_access_iterator |
+--------------------------------------------------------------------------+
|Template operators: |
|operator+ (reverse_iterator) operator== (reverse_bidir_iter) |
|operator- (reverse_iterator) operator== (reverse_iterator) |
|operator< (reverse_iterator) operator== (istream_iterator) |
+--------------------------------------------------------------------------+
|Template functions: |
|advance distance_type [5] iterator_category [5] |
|back_inserter front_inserter value_type [5] |
|distance inserter |
+--------------------------------------------------------------------------+
|Structs: |
|bidirectional_iterator_tag output_iterator_tag |
|forward_iterator_tag random_access_iterator_tag |
|input_iterator_tag |
|output_iterator |
+--------------------------------------------------------------------------+
|Function: iterator_category(output_iterator) |
+--------------------------------------------------------------------------+
24.1 Iterator tags [lib.iterator.tags]
1 To implement algorithms only in terms of iterators, it is often neces
sary to infer both of the value type and the distance type from the
iterator. To enable this task it is required that for an iterator i
of any category other than output iterator, the expression
value_type(i) returns (T*)(0) and the expression distance_type(i)
returns (Distance*)(0). For output iterators, these expressions are
not required.
24.1.1 Examples of using iterator tags [lib.examples]
1 For all the regular pointer types we can define value_type and dis
tance_type with the help of:
template <class T>
inline T* value_type(const T*) { return (T*)(0); }
template <class T>
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
2 Then, if we want to implement a generic reverse function, we do the
following:
template <class BidirectionalIterator>
inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {
__reverse(first, last, value_type(first), distance_type(first));
}
3 where __reverse is defined as:
template <class BidirectionalIterator, class T, class Distance>
void __reverse(BidirectionalIterator first, BidirectionalIterator last, T*,
Distance*)
{
Distance n;
distance(first, last, n); // see Iterator operations section
--n;
while (n > 0) {
T tmp = *first;
*first++ = *--last;
*last = tmp;
n -= 2;
}
}
4 If there is an additional pointer type far such that the difference of
two far pointers is of the type long, we define:
template <class T>
inline T* value_type(const T far *) { return (T*)(0); }
template <class T>
inline long* distance_type(const T far *) { return (long*)(0); }
5 It is often desirable for a template function to find out what is the
most specific category of its iterator argument, so that the function
can select the most efficient algorithm at compile time. To facili
tate this, the library introduces category tag classes which are used
as compile time tags for algorithm selection. They are:
input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidi
rectional_iterator_tag and random_access_iterator_tag. Every iterator
i must have an expression iterator_category(i) defined on it that
returns the most specific category tag that describes its behavior.
For example, we define that all the pointer types are in the random
access iterator category by:
template <class T>
inline random_access_iterator_tag iterator_category(T*) {
return random_access_iterator_tag();
}
6 For a user-defined iterator BinaryTreeIterator, it can be included
into the bidirectional iterator category by saying:
template <class T>
inline bidirectional_iterator_tag iterator_category(
const BinaryTreeIterator<T>&) {
return bidirectional_iterator_tag();
}
7 If a template function evolve is well defined for bidirectional itera
tors, but can be implemented more efficiently for random access itera
tors, then the implementation is like:
template <class BidirectionalIterator>
inline void evolve(BidirectionalIterator first, BidirectionalIterator last) {
evolve(first, last, iterator_category(first));
}
template <class BidirectionalIterator>
void evolve(BidirectionalIterator first, BidirectionalIterator last,
bidirectional_iterator_tag) {
// ... more generic, but less efficient algorithm
}
template <class RandomAccessIterator>
void evolve(RandomAccessIterator first, RandomAccessIterator last,
random_access_iterator_tag) {
// ... more efficient, but less generic algorithm
}
8 If a user wants to define a bidirectional iterator for some data
structure containing double and such that it works on a large memory
model of his computer, he can do it with:
class MyIterator : public bidirectional_iterator<double, long> {
// code implementing ++, etc.
};
9 Then there is no need to define iterator_category, value_type, and
distance_type on MyIterator.
24.1.2 Library defined primitives [lib.library.primitives]
1 To simplify the task of defining the iterator_category, value_type and
distance_type for user definable iterators, the library provides the
following predefined classes and functions:
24.1.2.1 Standard iterator tags [lib.std.iterator.tags]
struct input_iterator_tag : empty {};
struct output_iterator_tag : empty {};
struct forward_iterator_tag : empty {};
struct bidirectional_iterator_tag : empty {};
struct random_access_iterator_tag : empty {};
24.1.2.2 Basic iterators [lib.basic.iterators]
template <class T, class Distance = ptrdiff_t> struct input_iterator : empty{};
struct output_iterator : empty{};
// output_iterator is not a template because output iterators
// do not have either value type or distance type defined.
template <class T, class Distance = ptrdiff_t> struct forward_iterator : empty{};
template <class T, class Distance = ptrdiff_t> struct bidirectional_iterator
: empty {};
template <class T, class Distance = ptrdiff_t> struct random_access_iterator
: empty {};
24.1.2.3 iterator_category [lib.iterator.category]
// iterator_category
template <class T, class Distance>
inline input_iterator_tag
iterator_category(const input_iterator<T, Distance>&) {
return input_iterator_tag();
}
inline output_iterator_tag iterator_category(const output_iterator&) {
return output_iterator_tag();
}
template <class T, class Distance>
inline forward_iterator_tag
iterator_category(const forward_iterator<T, Distance>&) {
return forward_iterator_tag();
}
template <class T, class Distance>
inline bidirectional_iterator_tag
iterator_category(const bidirectional_iterator<T, Distance>&) {
return bidirectional_iterator_tag();
}
template <class T, class Distance>
inline random_access_iterator_tag
iterator_category(const random_access_iterator<T, Distance>&) {
return random_access_iterator_tag();
}
template <class T>
inline random_access_iterator_tag iterator_category(const T*) {
return random_access_iterator_tag();
}
24.1.2.4 value_type [lib.value.type]
template <class T, class Distance>
inline T* value_type(const input_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const forward_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const bidirectional_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T, class Distance>
inline T* value_type(const random_access_iterator<T, Distance>&) {
return (T*)(0);
}
template <class T>
inline T* value_type(const T*) { return (T*)(0); }
24.1.2.5 distance_type [lib.distance.type]
// distance_type of iterator
template <class T, class Distance>
inline Distance* distance_type(const input_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance* distance_type(const forward_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const bidirectional_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T, class Distance>
inline Distance*
distance_type(const random_access_iterator<T, Distance>&) {
return (Distance*)(0);
}
template <class T>
inline ptrdiff_t* distance_type(const T*) { return (ptrdiff_t*)(0); }
24.1.3 Iterator operations [lib.iterator.operations]
1 Since only random access iterators provide + and - operators, the
library provides two template functions advance and distance. These
functions use + and - for random access iterators (and are, therefore,
constant time for them); for input, forward and bidirectional itera
tors they use ++ to provide linear time implementations. advance
takes negative argument n for random access and bidirectional itera
tors only. advance increments (or decrements for negative n) iterator
reference i by n. distance increments n by the number of times it
takes to get from first to last.
template <class InputIterator, class Distance>
inline void advance(InputIterator& i, Distance n);
template <class InputIterator, class Distance>
inline void distance(InputIterator first, InputIterator last, Distance& n);
2 distance must be a three argument function storing the result into a
reference instead of returning the result because the distance type
cannot be deduced from built-in iterator types such as int*.
24.2 Predefined iterators [lib.predef.iterators]
24.2.1 Reverse iterators [lib.reverse.iterators]
1 Bidirectional and random access iterators have corresponding reverse
iterator adaptors that iterate through the data structure in the oppo
site direction. They have the same signatures as the corresponding
iterators. The fundamental relation between a reverse iterator and
its corresponding iterator i is established by the identity
&*(reverse_iterator(i)) == &*(i - 1).
2 This mapping is dictated by the fact that while there is always a
pointer past the end of an array, there might not be a valid pointer
before the beginning of an array.
3 The formal class parameter T of reverse iterators should be instanti
ated with the type that Iterator::operator* returns, which is usually
a reference type. For example, to obtain a reverse iterator for int*,
one should declare reverse_iterator<int*, int&>. To obtain a constant
reverse iterator for int*, one should declare reverse_iterator<const
int*, const int&>. The interface thus allows one to use reverse iter
ators with those iterator types for which operator* returns something
other than a reference type.
24.2.1.1 Template class [lib.reverse.bidir.iter]
reverse_bidirectional_iterator
template <class BidirectionalIterator, class T, class Distance = ptrdiff_t>
class reverse_bidirectional_iterator
: public bidirectional_iterator<T, Distance> {
protected:
BidirectionalIterator current;
public:
reverse_bidirectional_iterator() {}
reverse_bidirectional_iterator(BidirectionalIterator x) : current(x) {}
operator BidirectionalIterator() { return current; }
T operator*() {
BidirectionalIterator tmp = current;
return *--tmp;
}
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>&
operator++() {
--current;
return *this;
}
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
operator++(int) {
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
tmp = *this;
--current;
return tmp;
}
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>&
operator--() {
++current;
return *this;
}
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
operator--(int) {
reverse_bidirectional_iterator<BidirectionalIterator, T, Distance>
tmp = *this;
++current;
return tmp;
}
};
template <class BidirectionalIterator, class T, class Distance>
inline bool
operator==(
const reverse_bidirectional_iterator<BidirectionalIterator,T,Distance>& x,
const reverse_bidirectional_iterator<BidirectionalIterator,T,Distance>& y)
{
return x.current == y.current;
}
24.2.1.2 Template class reverse_iterator [lib.reverse.iterator]
template <class RandomAccessIterator, class T, class Distance = ptrdiff_t>
class reverse_iterator : public random_access_iterator<T, Distance> {
protected:
RandomAccessIterator current;
public:
reverse_iterator() {}
reverse_iterator(RandomAccessIterator x) : current(x) {}
operator RandomAccessIterator() { return current; }
T operator*() {
RandomAccessIterator tmp = current;
return *--tmp;
}
reverse_iterator<RandomAccessIterator, T, Distance>& operator++() {
--current;
return *this;
}
reverse_iterator<RandomAccessIterator, T, Distance> operator++(int) {
reverse_iterator<RandomAccessIterator, T, Distance> tmp = *this;
--current;
return tmp;
}
reverse_iterator<RandomAccessIterator, T, Distance>& operator--() {
++current;
return *this;
}
reverse_iterator<RandomAccessIterator, T, Distance> operator--(int) {
reverse_iterator<RandomAccessIterator, T, Distance> tmp = *this;
++current;
return tmp;
}
reverse_iterator<RandomAccessIterator, T, Distance>
operator+(Distance n) const {
return reverse_iterator<RandomAccessIterator, T, Distance>(current - n);
}
reverse_iterator<RandomAccessIterator, T, Distance>&
operator+=(Distance n) const {
current -= n;
return *this;
}
reverse_iterator<RandomAccessIterator, T, Distance>
operator-(Distance n) const {
return reverse_iterator<RandomAccessIterator, T, Distance>(current + n);
}
reverse_iterator<RandomAccessIterator, T, Distance>
operator-(Distance n) const {
current += n;
return *this;
}
T operator[](Distance n) { return *(*this + n); }
};
template <class RandomAccessIterator, class T, class Distance>
inline bool operator==(
const reverse_iterator<RandomAccessIterator, T, Distance>& x,
const reverse_iterator<RandomAccessIterator, T, Distance>& y)
{
return x.current == y.current;
}
template <class RandomAccessIterator, class T, class Distance>
inline bool operator<(
const reverse_iterator<RandomAccessIterator, T, Distance>& x,
const reverse_iterator<RandomAccessIterator, T, Distance>& y)
{
return y.current < x.current;
}
template <class RandomAccessIterator, class T, class Distance>
inline Distance operator-(
const reverse_iterator<RandomAccessIterator, T, Distance>& x,
const reverse_iterator<RandomAccessIterator, T, Distance>& y)
{
return y.current - x.current;
}
template <class RandomAccessIterator, class T, class Distance>
inline reverse_iterator<RandomAccessIterator, T, Distance> operator+(
Distance n,
const reverse_iterator<RandomAccessIterator, T, Distance>& x)
{
return reverse_iterator<RandomAccessIterator, T, Distance>(current - n);
}
1 There is no way a default for T can be expressed in terms of Bidirec
tionalIterator because the value type cannot be deduced from built-in
iterators such as int*. Otherwise, we would have written
template <class BidirectionalIterator,
class T = BidirectionalIterator::reference_type,
class Distance = BidirectionalIterator::difference_type>
class reverse_bidirectional_iterator: bidirectional_iterator<T, Distance> {
/* ... */
};
24.2.2 Insert iterators [lib.insert.iterators]
1 To make it possible to deal with insertion in the same way as writing
into an array, a special kind of iterator adaptors, called insert
iterators, are provided in the library. With regular iterator
classes,
while (first != last) *result++ = *first++;
2 causes a range [first, last) to be copied into a range starting with
result. The same code with result being an insert iterator will
insert corresponding elements into the container. This device allows
all of the copying algorithms in the library to work in the insert
mode instead of the regular overwrite mode.
3 An insert iterator is constructed from a container and possibly one of
its iterators pointing to where insertion takes place if it is neither
at the beginning nor at the end of the container. Insert iterators
satisfy the requirements of output iterators. operator* returns the
insert iterator itself. The assignment operator=(const T& x) is
defined on insert iterators to allow writing into them, it inserts x
right before where the insert iterator is pointing. In other words,
an insert iterator is like a cursor pointing into the container where
the insertion takes place. back_insert_iterator inserts elements at
the end of a container, front_insert_iterator inserts elements at the
beginning of a container, and insert_iterator inserts elements where
the iterator points to in a container. back_inserter, front_inserter,
and inserter are three functions making the insert iterators out of a
container.
24.2.2.1 Template class [lib.back.insert.iterator]
back_insert_iterator
template <class Container>
class back_insert_iterator : public output_iterator {
protected:
Container& container;
public:
back_insert_iterator(Container& x) : container(x) {}
back_insert_iterator<Container>&
operator=(const Container::value_type& value) {
container.push_back(value);
return *this;
}
back_insert_iterator<Container>& operator*() { return *this; }
back_insert_iterator<Container>& operator++() { return *this; }
back_insert_iterator<Container> operator++(int) { return *this; }
};
template <class Container>
back_insert_iterator<Container> back_inserter(Container& x) {
return back_insert_iterator<Container>(x);
}
24.2.2.2 Template class [lib.front.insert.iterator]
front_insert_iterator
template <class Container>
class front_insert_iterator : public output_iterator {
protected:
Container& container;
public:
front_insert_iterator(Container& x) : container(x) {}
front_insert_iterator<Container>&
operator=(const Container::value_type& value) {
container.push_front(value);
return *this;
}
front_insert_iterator<Container>& operator*() { return *this; }
front_insert_iterator<Container>& operator++() { return *this; }
front_insert_iterator<Container> operator++(int) { return *this; }
};
template <class Container>
front_insert_iterator<Container> front_inserter(Container& x) {
return front_insert_iterator<Container>(x);
}
24.2.2.3 Template class insert_iterator [lib.insert.iterator]
template <class Container>
class insert_iterator : public output_iterator {
protected:
Container& container;
Container::iterator iter;
public:
insert_iterator(Container& x, Container::iterator i)
: container(x), iter(i) {}
insert_iterator<Container>& operator=(const Container::value_type& value) {
iter = container.insert(iter, value);
++iter;
return *this;
}
insert_iterator<Container>& operator*() { return *this; }
insert_iterator<Container>& operator++() { return *this; }
insert_iterator<Container> operator++(int) { return *this; }
};
template <class Container, class Iterator>
insert_iterator<Container> inserter(Container& x, Iterator i) {
return insert_iterator<Container>(x, Container::iterator(i));
}
24.3 Stream iterators [lib.stream.iterators]
1 To make it possible for algorithmic templates to work directly with
input/output streams, appropriate iterator-like template classes are
provided. For example,
partial_sum_copy(istream_iterator<double>(cin), istream_iterator<double>(),
ostream_iterator<double>(cout, "\n"));
2 reads a file containing floating point numbers from cin, and prints
the partial sums onto cout.
24.3.1 Template class istream_iterator [lib.istream.iterator]
1 istream_iterator<T> reads (using operator>>) successive elements from
the input stream for which it was constructed. After it is con
structed, and every time ++ is used, the iterator reads and stores a
value of T. If the end of stream is reached (operator void*() on the
stream returns false), the iterator becomes equal to the end-of-stream
iterator value. The constructor with no arguments istream_iterator()
always constructs an end of stream input iterator object, which is the
only legitimate iterator to be used for the end condition. The result
of operator* on an end of stream is not defined. For any other itera
tor value a const T& is returned. It is impossible to store things
into istream iterators. The main peculiarity of the istream iterators
is the fact that ++ operators are not equality preserving, that is, i
== j does not guarantee at all that ++i == ++j. Every time ++ is used
a new value is read.
2 The practical consequence of this fact is that istream iterators can
be used only for one-pass algorithms, which actually makes perfect
sense, since for multi-pass algorithms it is always more appropriate
to use in- memory data structures. Two end-of-stream iterators are
always equal. An end-of-stream iterator is not equal to a non-end-of-
stream iterator. Two non-end-of-stream iterators are equal when they
are constructed from the same stream.
template <class T, class Distance = ptrdiff_t>
class istream_iterator : input_iterator<T, Distance> {
public:
istream_iterator();
istream_iterator(istream& s);
istream_iterator(const istream_iterator<T, Distance>& x);
~istream_iterator();
const T& operator*() const;
istream_iterator<T, Distance>& operator++();
istream_iterator<T, Distance> operator++(int);
};
template <class T, class Distance>
bool operator==(const istream_iterator<T, Distance>& x,
const istream_iterator<T, Distance>& y);
24.3.2 Template class ostream_iterator [lib.ostream.iterator]
1 ostream_iterator<T> writes (using operator<<) successive elements onto
the output stream from which it was constructed. If it was con
structed with char* as a constructor argument, this string, called a
delimiter string, is written to the stream after every T is written.
It is not possible to get a value out of the output iterator. Its
only use is as an output iterator in situations like
while (first != last) *result++ = *first++;
2 ostream_iterator is defined as:
template <class T>
class ostream_iterator : public output_iterator {
public:
ostream_iterator(ostream& s);
ostream_iterator(const char* delimiter);
ostream_iterator(ostream& s, const char* delimiter);
ostream_iterator(const ostream_iterator<T>& x);
~ostream_iterator();
ostream_iterator<T>& operator=(const T& value);
ostream_iterator<T>& operator*();
ostream_iterator<T>& operator++();
ostream_iterator<T> operator++(int);
};
24.4 Streambuf iterators [lib.streambuf.iterators]
+------- BEGIN BOX 1 -------+
TO BE SPECIFIED.
istreambuf_iterator is currently part of <istream>, subclause
_lib.input.streams_.
ostreambuf_iterator is currently part of <ostream>, subclause
_lib.output.streams_.
Both should be moved here.
+------- END BOX 1 -------+