1 This clause describes components that C++ programs may use to perform iterations over containers (clause 23), streams (27.6), and stream buffers (27.5).
2 The following subclauses describe iterator requirements, and components for iterator primitives, predefined iterators, and stream iterators, as summarized in Table 70:
| Table 70---Iterators library summary |
_ ____________________________________ _ Subclause Header(s) _ ____________________________________ ____________________________________ _ 24.1 Requirements ____________________________________ 24.3 Iterator primitives 24.4 Predefined iterators <iterator> _ 24.5 Stream iterators ____________________________________ |
1 Iterators are a generalization of pointers that allow a C++ program to work with different data structures (containers) in a uniform manner. To be able to construct template algorithms that work correctly and efficiently on different types of data structures, the library formalizes not just the interfaces but also the semantics and complexity assumptions of iterators. All iterators i support the expression *i, resulting in a value of some class, enumeration, or built-in type T, called the value type of the iterator. All iterators i for which the expression (*i).m is well-defined, support the expression i->m with the same semantics as (*i).m. For every iterator type X for which equality is defined, there is a corresponding signed integral type called the difference type of the iterator.
2 Since iterators are an abstraction of pointers, their semantics is a generalization of most of the semantics of pointers in C++. This ensures that every template function that takes iterators works as well with regular pointers. This International Standard defines five categories of iterators, according to the operations defined on them: input iterators, output iterators, forward iterators, bidirectional iterators and random access iterators, as shown in Table 71.
| Table 71---Relations among iterator categories |
_ ________________________________________________________ Random access --> Bidirectional --> Forward --> Input _ --> Output ________________________________________________________ |
3 Forward iterators satisfy all the requirements of the input and output iterators and can be used whenever either kind is specified; Bidirectional iterators also satisfy all the requirements of the forward iterators and can be used whenever a forward iterator is specified; Random access iterators also satisfy all the requirements of bidirectional iterators and can be used whenever a bidirectional iterator is specified.
4 Besides its category, a forward, bidirectional, or random access iterator can also be mutable or constant depending on whether the result of the expression *i behaves as a reference or as a reference to a constant. Constant iterators do not satisfy the requirements for output iterators, and the result of the expression *i (for constant iterator i) cannot be used in an expression where an lvalue is required.
5 Just as a regular pointer to an array guarantees that there is a pointer value pointing past the last element of the array, so for any iterator type there is an iterator value that points past the last element of a corresponding container. These values are called past-the-end values. Values of an iterator i for which the expression *i is defined are called dereferenceable. The library never assumes that past-the-end values are dereferenceable. Iterators can also have singular values that are not associated with any container. [Example: After the declaration of an uninitialized pointer x (as with int* x;), x must always be assumed to have a singular value of a pointer. ] Results of most expressions are undefined for singular values; the only exception is an assignment of a non-singular value to an iterator that holds a singular value. In this case the singular value is overwritten the same way as any other value. Dereferenceable and past-the-end values are always non-singular.
6 An iterator j is called reachable from an iterator i if and only if there is a finite sequence of applications of the expression ++i that makes i == j. If j is reachable from i, they refer to the same container.
7 Most of the library's algorithmic templates that operate on data structures have interfaces that use ranges. A range is a pair of iterators that designate the beginning and end of the computation. A range [i, i) is an empty range; in general, a range [i, j) refers to the elements in the data structure starting with the one pointed to by i and up to but not including the one pointed to by j. Range [i, j) is valid if and only if j is reachable from i. The result of the application of functions in the library to invalid ranges is undefined.
8 All the categories of iterators require only those functions that are realizable for a given category in constant time (amortized). Therefore, requirement tables for the iterators do not have a complexity column.
9 In the following sections, a and b denote values of X, n denotes a value of the difference type Distance, u, tmp, and m denote identifiers, r denotes a value of X&, t denotes a value of value type T.
1 A class or a built-in type X satisfies the requirements of an input iterator for the value type T if the following expressions are valid, where U is the type of any specified member of type T, as shown in Table 72.
2 In Table 72, the term the domain of == is used in the ordinary mathematical sense to denote the set of values over which == is (required to be) defined. This set can change over time. Each algorithm places additional requirements on the domain of == for the iterator values it uses. These requirements can be inferred from the uses that algorithm makes of == and !=. [Example: the call find(a,b,x) is defined only if the value of a has the property p defined as follows: b has property p and a value i has property p if (*i==x) or if (*i!=x and ++i has property p). ]
| Table 72---Input iterator requirements |
_ _______________________________________________________________________________
_ operation type semantics, pre/post-conditions
_ _______________________________________________________________________________
_______________________________________________________________________________
X u(a); X post: u is a copy of a
_ A destructor is assumed to be present and accessible.
_______________________________________________________________________________
u = a; X& result: u
_ post: u is a copy of a
_______________________________________________________________________________
_ a == b convertible to bool == is an equivalence relation over its domain.
_______________________________________________________________________________
_ a != b convertible to bool bool(a==b) != bool(a!=b) over the domain of ==
_______________________________________________________________________________
*a convertible to T pre: a is dereferenceable.
If a==b and (a,b) is in the domain of ==
_ then *a is equivalent to *b.
_______________________________________________________________________________
a->m pre: (*a).m is well-defined
_ Equivalent to (*a).m
_______________________________________________________________________________
++r X& pre: r is dereferenceable.
post: r is dereferenceable or r is past-the-end.
post: any copies of the previous value of r are no longer
required either to be dereferenceable or to be in the domain
_ of ==.
_______________________________________________________________________________
_ (void)r++ equivalent to (void)++r
_______________________________________________________________________________
_ *r++ T { T tmp = *r; ++r; return tmp; }
_______________________________________________________________________________
|
3 [Note: For input iterators, a == b does not imply ++a == ++b. (Equality does not guarantee the substitution property or referential transparency.) Algorithms on input iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Value type T is not required to be an Assignable type (23.1). These algorithms can be used with istreams as the source of the input data through the istream_iterator class. ]
1 A class or a built-in type X satisfies the requirements of an output iterator if X is an Assignable type (23.1) and also the following expressions are valid, as shown in Table 73:
| Table 73---Output iterator requirements |
_ _________________________________________________________________________
expression return type operational assertion/note
_ semantics pre/post-condition
_ _________________________________________________________________________
_________________________________________________________________________
X(a) a = t is equivalent to
X(a) = t.
_ note: a destructor is assumed.
_________________________________________________________________________
X u(a);
_ X u = a;
_________________________________________________________________________
_ *a = t result is not used
_________________________________________________________________________
_ ++r X& &r == &++r.
_________________________________________________________________________
r++ convertible to { X tmp = r;
const X& ++r;
_ return tmp; }
_________________________________________________________________________
_ *r++ = t result is not used
_________________________________________________________________________
|
2 [Note: The only valid use of an operator* is on the left side of the assignment statement. Assignment through the same value of the iterator happens only once. Algorithms on output iterators should never attempt to pass through the same iterator twice. They should be single pass algorithms. Equality and inequality might not be defined. Algorithms that take output iterators can be used with ostreams as the destination for placing data through the ostream_iterator class as well as with insert iterators and insert pointers. ---end note]
1 A class or a built-in type X satisfies the requirements of a forward iterator if the following expressions are valid, as shown in Table 74:
| Table 74---Forward iterator requirements |
_ _______________________________________________________________________________
expression return type operational assertion/note
_ semantics pre/post-condition
_ _______________________________________________________________________________
_______________________________________________________________________________
X u; note: u might have a singular
value.
_ note: a destructor is assumed.
_______________________________________________________________________________
_ X() note: X() might be singular.
_______________________________________________________________________________
_ X(a) a == X(a).
_______________________________________________________________________________
X u(a); X u; u = a; post: u == a.
_ X u = a;
_______________________________________________________________________________
_ a == b convertible to bool == is an equivalence relation.
_______________________________________________________________________________
_ a != b convertible to bool !(a == b)
_______________________________________________________________________________
_ r = a X& post: r == a.
_______________________________________________________________________________
*a T& pre: a is dereferenceable.
a == b implies *a == *b.
_ If X is mutable, *a = t is valid.
_______________________________________________________________________________
_ a->m U& (*a).m pre: (*a).m is well-defined.
_______________________________________________________________________________
++r X& pre: r is dereferenceable.
post: r is dereferenceable or r is
past-the-end.
r == s and r is dereference able implies ++r == ++s.
_ &r == &++r.
_______________________________________________________________________________
r++ convertible to { X tmp = r;
const X& ++r;
_ return tmp; }
_______________________________________________________________________________
_ *r++ T&
_______________________________________________________________________________
|
2 [Note: The condition that a == b implies ++a == ++b (which is not true for input and output iterators) and the removal of the restrictions on the number of the assignments through the iterator (which applies to output iterators) allows the use of multi-pass one-directional algorithms with forward iterators. ---end note]
1 A class or a built-in type X satisfies the requirements of a bidirectional iterator if, in addition to satisfying the requirements for forward iterators, the following expressions are valid as shown in Table 75:
| Table 75---Bidirectional iterator requirements (in addition to forward iterator) |
______________________________________________________________________
operational assertion/note
expression return type
semantics pre/post-condition
______________________________________________________________________
______________________________________________________________________
--r X& pre: there exists s such
that r == ++s.
post: s is dereferenceable.
--(++r) == r.
--r == --s implies r
== s.
&r == &--r.
______________________________________________________________________
r-- convertible to { X tmp = r;
const X& --r;
return tmp; }
______________________________________________________________________
*r-- convertible to T
______________________________________________________________________
|
2 [Note: Bidirectional iterators allow algorithms to move iterators backward as well as forward. ---end note]
1 A class or a built-in type X satisfies the requirements of a random access iterator if, in addition to satisfying the requirements for bidirectional iterators, the following expressions are valid as shown in Table 76:
| Table 76---Random access iterator requirements (in addition to bidirectional iterator) |
_ __________________________________________________________________________
expression return type operational assertion/note
_ semantics pre/post-condition
_ __________________________________________________________________________
__________________________________________________________________________
r += n X& { Distance m =
n;
if (m >= 0)
while (m--)
++r;
else
while (m++)
--r;
_ return r; }
__________________________________________________________________________
a + n { X tmp = a;
X return tmp += a + n == n + a.
n; }
_ n + a
__________________________________________________________________________
_ r -= n X& return r += -n;
__________________________________________________________________________
a - n X { X tmp = a;
return tmp -=
_ n; }
__________________________________________________________________________
b - a Distance (a<b)? pre: there exists a value n
distance(a,b): of Distance such that a
-distance(b,a) + n == b. b == a +
_ (b - a).
__________________________________________________________________________
_ a[n] convertible to T *(a + n)
__________________________________________________________________________
_ a < b convertible to bool b - a > 0 < is a total ordering relation
__________________________________________________________________________
a > b convertible to bool b < a > is a total ordering relation
_ opposite to <.
__________________________________________________________________________
_ a >= b convertible to bool !(a < b)
__________________________________________________________________________
_ a <= b convertible to bool !(a > b)
__________________________________________________________________________
|
// 24.3, primitives:
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>void advance(InputIterator& i, Distance n);
// 24.4, predefined iterators: template <class Iterator> class reverse_iterator; template <class Iterator>typename iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);
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);
reverse_iterator<Iterator>
operator+(
typename reverse_iterator<Iterator>::difference_type n,
const reverse_iterator<Iterator>& x);
template <class Container> class front_insert_iterator; template <class Container>back_insert_iterator<Container> back_inserter(Container& x);
template <class Container> class insert_iterator; template <class Container, class Iterator>front_insert_iterator<Container> front_inserter(Container& x);
insert_iterator<Container> inserter(Container& x, Iterator i);
// 24.5, stream iterators:
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;
}
1 To simplify the task of defining iterators, the library provides several classes and functions:
1 To implement algorithms only in terms of iterators, it is often necessary to determine the value and difference types that correspond to a particular iterator type. Accordingly, it is required that if Iterator is the type of an iterator, the types
be defined as the iterator's difference type, value type and iterator category, respectively. In the case of an output iterator, the typesiterator_traits<Iterator>::difference_type iterator_traits<Iterator>::value_type iterator_traits<Iterator>::iterator_category
are both defined as void.iterator_traits<Iterator>::difference_type iterator_traits<Iterator>::value_type
2 The template iterator_traits<Iterator> is defined as
template<class Iterator> struct iterator_traits {
typedef typename Iterator::difference_type difference_type;
typedef typename Iterator::value_type value_type;
typedef typename Iterator::pointer pointer;
typedef typename Iterator::reference reference;
typedef typename Iterator::iterator_category iterator_category;
};
template<class T> struct iterator_traits<T*> {
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef random_access_iterator_tag iterator_category;
};
template<class T> struct iterator_traits<const T*> {
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef const T* pointer;
typedef const T& reference;
typedef random_access_iterator_tag iterator_category;
};
template<class T> struct iterator_traits<T _ _far*> {
typedef long difference_type;
typedef T value_type;
typedef T _ _far* pointer;
typedef T _ _far& reference;
typedef random_access_iterator_tag iterator_category;
};
3 [Example: To implement a generic reverse function, a C++ program can do the following:
template <class BidirectionalIterator>
void reverse(BidirectionalIterator first, BidirectionalIterator last) {
typename iterator_traits<BidirectionalIterator>::difference_type n =
distance(first, last);
--n;
while(n > 0) {
typename iterator_traits<BidirectionalIterator>::value_type
tmp = *first;
*first++ = *--last;
*last = tmp;
n -= 2;
}
}
1 The iterator template may be used as a base class to ease the definition of required types for new iterators.
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;
};
}
1 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 facilitate 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, bidirectional_iterator_tag and random_access_iterator_tag. For every iterator of type Iterator, iterator_traits<Iterator>::iterator_category must be defined to be the most specific category tag that describes the iterator's behavior.
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 {};
}
2 [Example: For a program-defined iterator BinaryTreeIterator, it could be included into the bidirectional iterator category by specializing the iterator_traits template:
template<class T> struct iterator_traits<BinaryTreeIterator<T> > {
typedef ptrdiff_t difference_type;
typedef T value_type;
typedef T* pointer;
typedef T& reference;
typedef bidirectional_iterator_tag iterator_category;
};
3 [Example: If evolve() is well defined for bidirectional iterators, but can be implemented more efficiently for random access iterators, then the implementation is as follows:
template <class BidirectionalIterator>
inline void
evolve(BidirectionalIterator first, BidirectionalIterator last) {
evolve(first, last,
typename iterator_traits<BidirectionalIterator>::iterator_category());
}
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
}
4 [Example: If a C++ program wants to define a bidirectional iterator for some data structure containing double and such that it works on a large memory model of the implementation, it can do so with:
class MyIterator :
public iterator<bidirectional_iterator_tag, double, long, T*, T&> {
// code implementing ++, etc.
};
5 Then there is no need to specialize the iterator_traits template. ---end example]
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 iterators they use ++ to provide linear time implementations.
template <class InputIterator, class Distance> void advance(InputIterator& i, Distance n);
2 Requires: n may be negative only for random access and bidirectional iterators.
3 Effects: Increments (or decrements for negative n) iterator reference i by n.
template<class InputIterator>
typename iterator_traits<InputIterator>::difference_type
distance(InputIterator first, InputIterator last);
4 Effects: Returns the number of increments or decrements needed to get from first to last.
5 Requires: last must be reachable from first.
1 Bidirectional and random access iterators have corresponding reverse iterator adaptors that iterate through the data structure in the opposite 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.
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);
}
1 The template parameter Iterator shall meet all the requirements of a Bidirectional Iterator (24.1.4).
2 Additionally, Iterator shall meet the requirements of a Random Access Iterator (24.1.5) if any of the members operator+ (24.4.1.3.7), operator- (24.4.1.3.9), operator+= (24.4.1.3.8), operator-= (24.4.1.3.10), operator[] (24.4.1.3.11), or the global operators operator< (24.4.1.3.13), operator> (24.4.1.3.15), operator<= (24.4.1.3.17), operator>= (24.4.1.3.16), operator- (24.4.1.3.18) or operator+ (24.4.1.3.19). is referenced in a way that requires instantiation (14.7.1).
explicit reverse_iterator(Iterator x);
1 Effects: Initializes current with x.
template <class U> reverse_iterator(const reverse_iterator<U> &u);
2 Effects: Initializes current with u.current.
Iterator base() const; // explicit
1 Returns: current
reference operator*() const;
1 Effects:
Iterator tmp = current; return *--tmp;
pointer operator->() const;
1 Effects:
24.4.1.3.5 operator++ [lib.reverse.iter.op++]return &(operator*());
reverse_iterator& operator++();
1 Effects: --current;
2 Returns: *this
reverse_iterator operator++(int);
3 Effects:
24.4.1.3.6 operator-- [lib.reverse.iter.op--]reverse_iterator tmp = *this; --current; return tmp;
reverse_iterator& operator--();
1 Effects: ++current
2 Returns: *this
reverse_iterator operator--(int);
3 Effects:
24.4.1.3.7 operator+ [lib.reverse.iter.op+]reverse_iterator tmp = *this; ++current; return tmp;
reverse_iterator operator+(typename reverse_iterator<Iterator>::difference_type n) const;
1 Returns: reverse_iterator(current-n) 24.4.1.3.8 operator+= [lib.reverse.iter.op+=]
reverse_iterator& operator+=(typename reverse_iterator<Iterator>::difference_type n);
1 Effects: current -= n;
2 Returns: *this 24.4.1.3.9 operator- [lib.reverse.iter.op-]
reverse_iterator operator-(typename reverse_iterator<Iterator>::difference_type n) const;
1 Returns: reverse_iterator(current+n) 24.4.1.3.10 operator-= [lib.reverse.iter.op-=]
reverse_iterator& operator-=(typename reverse_iterator<Iterator>::difference_type n);
1 Effects: current += n;
2 Returns: *this
reference operator[](typename reverse_iterator<Iterator>::difference_type n) const;
1 Returns: current[-n-1] 24.4.1.3.12 operator== [lib.reverse.iter.op==]
template <class Iterator>
bool operator==(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current == y.current 24.4.1.3.13 operator< [lib.reverse.iter.op<]
template <class Iterator>
bool operator<(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current > y.current 24.4.1.3.14 operator!= [lib.reverse.iter.op!=]
template <class Iterator>
bool operator!=(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current != y.current 24.4.1.3.15 operator> [lib.reverse.iter.op>]
template <class Iterator>
bool operator>(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current < y.current 24.4.1.3.16 operator>= [lib.reverse.iter.op>=]
template <class Iterator>
bool operator>=(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current <= y.current 24.4.1.3.17 operator<= [lib.reverse.iter.op<=]
template <class Iterator>
bool operator<=(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: x.current >= y.current
template <class Iterator>
typename reverse_iterator<Iterator>::difference_type operator-(
const reverse_iterator<Iterator>& x,
const reverse_iterator<Iterator>& y);
1 Returns: y.current - x.current
template <class Iterator>
reverse_iterator<Iterator> operator+(
typename reverse_iterator<Iterator>::difference_type n,
const reverse_iterator<Iterator>& x);
1 Returns: reverse_iterator<Iterator> (x.current - n)
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.
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);
}
explicit back_insert_iterator(Container& x);
1 Effects: Initializes container with &x. 24.4.2.2.2 back_insert_iterator::operator= [lib.back.insert.iter.op=]
back_insert_iterator<Container>& operator=(typename Container::const_reference value);
1 Effects: container->push_back(value);
2 Returns: *this. 24.4.2.2.3 back_insert_iterator::operator* [lib.back.insert.iter.op*]
back_insert_iterator<Container>& operator*();
1 Returns: *this. 24.4.2.2.4 back_insert_iterator::operator++ [lib.back.insert.iter.op++]
back_insert_iterator<Container>& operator++(); back_insert_iterator<Container> operator++(int);
1 Returns: *this.
template <class Container> back_insert_iterator<Container> back_inserter(Container& x);
1 Returns: back_insert_iterator<Container>(x).
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);
}
explicit front_insert_iterator(Container& x);
1 Effects: Initializes container with &x. 24.4.2.4.2 front_insert_iterator::operator= [lib.front.insert.iter.op=]
front_insert_iterator<Container>& operator=(typename Container::const_reference value);
1 Effects: container->push_front(value);
2 Returns: *this. 24.4.2.4.3 front_insert_iterator::operator* [lib.front.insert.iter.op*]
front_insert_iterator<Container>& operator*();
1 Returns: *this. 24.4.2.4.4 front_insert_iterator::operator++ [lib.front.insert.iter.op++]
front_insert_iterator<Container>& operator++(); front_insert_iterator<Container> operator++(int);
1 Returns: *this.
template <class Container> front_insert_iterator<Container> front_inserter(Container& x);
1 Returns: front_insert_iterator<Container>(x).
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);
}
insert_iterator(Container& x, typename Container::iterator i);
1 Effects: Initializes container with &x and iter with i. 24.4.2.6.2 insert_iterator::operator= [lib.insert.iter.op=]
insert_iterator<Container>& operator=(typename Container::const_reference value);
1 Effects:
iter = container->insert(iter, value); ++iter;
2 Returns: *this. 24.4.2.6.3 insert_iterator::operator* [lib.insert.iter.op*]
insert_iterator<Container>& operator*();
1 Returns: *this. 24.4.2.6.4 insert_iterator::operator++ [lib.insert.iter.op++]
insert_iterator<Container>& operator++(); insert_iterator<Container>& operator++(int);
1 Returns: *this.
template <class Container, class Inserter> insert_iterator<Container> inserter(Container& x, Inserter i);
1 Returns: insert_iterator<Container>(x,typename Container::iterator(i)).
1 To make it possible for algorithmic templates to work directly with input/output streams, appropriate iterator-like template classes are provided.
2 [Example:
reads a file containing floating point numbers from cin, and prints the partial sums onto cout. ---end example]partial_sum_copy(istream_iterator<double, char>(cin), istream_iterator<double, char>(), ostream_iterator<double, char>(cout, "\n"));
1 istream_iterator reads (using operator>>) successive elements from the input stream for which it was constructed. After it is constructed, 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 iterator value a const T& is returned. The result of operator-> on an end of stream is not defined. For any other iterator 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 inmemory data structures.
3 Two end-of-stream iterators are always equal. An end-of-stream iterator is not equal to a non-end-ofstream iterator. Two non-end-of-stream iterators are equal when they are constructed from the same stream.
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);
}
istream_iterator();
1 Effects: Constructs the end-of-stream iterator.
istream_iterator(istream_type& s);
2 Effects: Initializes in_stream with s. value may be initialized during construction or the first time it is referenced.
istream_iterator(const istream_iterator<T,charT,traits,Distance>& x);
3 Effects: Constructs a copy of x.
~istream_iterator();
4 Effects: The iterator is destroyed.
const T& operator*() const;
1 Returns: value
const T* operator->() const;
2 Returns: &(operator*())
istream_iterator<T,charT,traits,Distance>& operator++();
3 Effects: *in_stream >> value
4 Returns: *this
istream_iterator<T,charT,traits,Distance>& operator++(int);
5 Effects:
istream_iterator<T,charT,traits,Distance> tmp = *this; *in_stream >> value; return (tmp);
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);
6 Returns: (x.in_stream == y.in_stream)
1 ostream_iterator writes (using operator<<) successive elements onto the output stream from which it was constructed. If it was constructed 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:
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
};
}
ostream_iterator(ostream_type& s);
1 Effects: Initializes out_stream with s and delim with null.
ostream_iterator(ostream_type& s, const charT* delimiter);
2 Effects: Initializes out_stream with s and delim with delimiter.
ostream_iterator(const ostream_iterator& x);
3 Effects: Constructs a copy of x.
~ostream_iterator();
4 Effects: The iterator is destroyed.
ostream_iterator& operator=(const T& value);
1 Effects:
*out_stream << value; if(delim != 0) *out_stream << delim; return (*this);
ostream_iterator& operator*();
2 Returns: *this
ostream_iterator& operator++(); ostream_iterator& operatot++(int);
3 Returns: *this
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);
}
1 The template class istreambuf_iterator reads successive characters from the streambuf for which it was constructed. operator* provides access to the current input character, if any. Each time operator++ is evaluated, the iterator advances to the next input character. If the end of stream is reached (streambuf_type::sgetc() returns traits::eof()), the iterator becomes equal to the end of stream iterator value. The default constructor istreambuf_iterator() and the constructor istreambuf_iterator(0) both construct an end of stream iterator object suitable for use as an endof-range.
2 The result of operator*() on an end of stream is undefined. For any other iterator value a char_type value is returned. It is impossible to assign a character via an input iterator.
3 Note that in the input iterators, ++ operators are not equality preserving, that is, i == j does not guarantee at all that ++i == ++j. Every time ++ is evaluated a new value is used.
4 The practical consequence of this fact is that an istreambuf_iterator object can be used only for one-pass algorithms. Two end of stream iterators are always equal. An end of stream iterator is not equal to a non-end of stream iterator. 24.5.3.1 Template class istreambuf_iterator::proxy [lib.istreambuf.iterator::proxy]
namespace std {
template <class charT, class traits = char_traits<charT> >
class istreambuf_iterator<charT, traits>::proxy {
charT keep_;
basic_streambuf<charT,traits>* sbuf_;
proxy(charT c,
basic_streambuf<charT,traits>* sbuf);
: keep_(c), sbuf_(sbuf) {}
public:
charT operator*() { return keep_; }
};
}
1 Class istreambuf_iterator<charT,traits>::proxy is for exposition only. An implementation is permitted to provide equivalent functionality without providing a class with this name. Class istreambuf_iterator<charT,traits>::proxy provides a temporary placeholder as the return value of the post-increment operator (operator++). It keeps the character pointed to by the previous value of the iterator for some possible future access to get the character.
istreambuf_iterator() throw();
1 Effects: Constructs the end-of-stream iterator.
istreambuf_iterator(basic_istream<charT,traits>& s) throw(); istreambuf_iterator(basic_streambuf<charT,traits>* s) throw();
2 Effects: Constructs an istreambuf_iterator<> that uses the basic_streambuf<> object
*(s.rdbuf()), or *s, respectively. Constructs an end-of-stream iterator if s.rdbuf() is null. istreambuf_iterator(const proxy& p) throw();
3 Effects: Constructs a istreambuf_iterator<> that uses the basic_streambuf<> object pointed to by the proxy object's constructor argument p. 24.5.3.3 istreambuf_iterator::operator* [lib.istreambuf.iterator::op*]
charT operator*() const
1 Returns: The character obtained via the streambuf member sbuf_->sgetc(). 24.5.3.4 istreambuf_iterator::operator++ [lib.istreambuf.iterator::op++]
istreambuf_iterator<charT,traits>&
istreambuf_iterator<charT,traits>::operator++();
1 Effects: sbuf_->sbumpc().
2 Returns: *this.
proxy istreambuf_iterator<charT,traits>::operator++(int);
3 Returns: proxy(sbuf_->sbumpc(), sbuf_).
24.5.3.5 istreambuf_iterator::equal [lib.istreambuf.iterator::equal]istreambuf_iterator<charT,traits> tmp = *this; sbuf_->sbumpc(); return(tmp);
bool equal(istreambuf_iterator<charT,traits>& b);
1 Returns: true if and only if both iterators are at end-of-stream, or neither is at end-of-stream, regardless of what streambuf object they use. 24.5.3.6 operator== [lib.istreambuf.iterator::op==]
template <class charT, class traits>
bool operator==(const istreambuf_iterator<charT,traits>& a,
const istreambuf_iterator<charT,traits>& b);
1 Returns: a.equal(b). 24.5.3.7 operator!= [lib.istreambuf.iterator::op!=]
template <class charT, class traits>
bool operator!=(const istreambuf_iterator<charT,traits>& a,
const istreambuf_iterator<charT,traits>& b);
1 Returns: !a.equal(b).
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
};
}
1 The template class ostreambuf_iterator writes successive characters onto the output stream from which it was constructed. It is not possible to get a character value out of the output iterator.
ostreambuf_iterator(ostream_type& s) throw();
1 Requires: s is not null.
2 Effects: : sbuf_(s.rdbuf()) {}
ostreambuf_iterator(streambuf_type* s) throw();
3 Effects: : sbuf_(s) {}
ostreambuf_iterator<charT,traits>& operator=(charT c);
1 Effects: If failed() yields false, calls sbuf_->sputc(c); otherwise has no effect.
2 Returns: *this.
ostreambuf_iterator<charT,traits>& operator*();
3 Returns: *this.
ostreambuf_iterator<charT,traits>& operator++(); ostreambuf_iterator<charT,traits>& operator++(int);
4 Returns: *this.
bool failed() const throw();
5 Returns: true if in any prior use of member operator=, the call to sbuf_->sputc() returned
traits::eof(); or false otherwise.