Standard Template Library Programmers Guide - читать онлайн бесплатно полную версию книги . Страница 4

Iterators

Introduction

Category: iterators

Component type: overview

Summary

Iterators are a generalization of pointers: they are objects that point to other objects. As the name suggests, iterators are often used to iterate over a range of objects: if an iterator points to one element in a range, then it is possible to increment it so that it points to the next element.

Iterators are central to generic programming because they are an interface between containers and algorithms: algorithms typically take iterators as arguments, so a container need only provide a way to access its elements using iterators. This makes it possible to write a generic algorithm that operates on many different kinds of containers, even containers as different as a vector and a doubly linked list.

The STL defines several different concepts related to iterators, several predefined iterators, and a collection of types and functions for manipulating iterators.

Description

Iterators are in fact not a single concept, but six concepts that form a hierarchy: some of them define only a very restricted set of operations, while others define additional functionality. The five concepts that are actually used by algorithms are Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, and Random Access Iterator. A sixth concept, Trivial Iterator, is introduced only to clarify the definitions of the other iterator concepts.

The most restricted sorts of iterators are Input Iterators and Output Iterators, both of which permit "single pass" algorithms but do not necessarily support "multi-pass" algorithms. Input iterators only guarantee read access: it is possible to dereference an Input Iterator to obtain the value it points to, but not it is not necessarily possible to assign a new value through an input iterator. Similarly, Output Iterators only guarantee write access: it is possible to assign a value through an Output Iterator, but not necessarily possible to refer to that value.

Forward Iterators are a refinement of Input Iterators and Output Iterators: they support the Input Iterator and Output Iterator operations and also provide additional functionality. In particular, it is possible to use "multi-pass" algorithms with Forward Iterators. A Forward Iterator may be constant, in which case it is possible to access the object it points to but not to to assign a new value through it, or mutable , in which case it is possible to do both.

Bidirectional Iterators, like Forward Iterators, allow multi-pass algorithms. As the name suggests, they are different in that they support motion in both directions: a Bidirectional Iterator may be incremented to obtain the next element or decremented to obtain the previous element. A Forward Iterator, by contrast, is only required to support forward motion. An iterator used to traverse a singly linked list, for example, would be a Forward Iterator , while an iterator used to traverse a doubly linked list would be a Bidirectional Iterator.

Finally, Random Access Iterators allow the operations of pointer arithmetic: addition of arbitrary offsets, subscripting, subtraction of one iterator from another to find a distance, and so on.

Most algorithms are expressed not in terms of a single iterator but in terms of a range of iterators [1]; the notation [first, last) refers to all of the iterators from first up to, but not including, last. [2] Note that a range may be empty, i.e.first and last may be the same iterator. Note also that if there are n iterators in a range, then the notation [first, last) represents n+1 positions. This is crucial: algorithms that operate on n things frequently require n+1 positions. Linear search, for example (find) must be able to return some value to indicate that the search was unsuccessful.

Sometimes it is important to be able to infer some properties of an iterator: the type of object that is returned when it is dereferenced, for example. There are two different mechanisms to support this sort of inferrence: an older mechanism called Iterator Tags, and a newer mechanism called iterator_traits [3].

Concepts

• Trivial Iterator

• Input Iterator

• Output Iterator

• Forward Iterator

• Bidirectional Iterator

• Random Access Iterator

Types

• istream_iterator

• ostream_iterator

• reverse_iterator

• reverse_bidirectional_iterator

• insert_iterator

• front_insert_iterator

• back_insert_iterator

• iterator_traits

• input_iterator_tag

• output_iterator_tag

• forward_iterator_tag

• bidirectional_iterator_tag

• random_access_iterator_tag

• input_iterator

• output_iterator

• forward_iterator

• bidirectional_iterator

• random_access_iterator

Functions

• distance_type

• value_type

• iterator_category

• distance

• advance

• inserter

• front_inserter

• back_inserter

Notes

[1] Ranges are not a well-defined concept for Trivial Iterators, because a Trivial Iterator cannot be incremented: there is no such thing as a next element. They are also not a well-defined concept for Output Iterators, because it is impossible to compare two Output Iterators for equality. Equality is crucial to the definition of a range, because only by comparing an iterator for equality with the last element is it possible to step through a range.

[2] Sometimes the notation [first, last) refers to the iterators first, first+1, …, last-1 and sometimes it refers to the objects pointed to by those iterators: *first, *(first+1), …, *(last-1). In most cases it will be obvious from context which of these is meant; where the distinction is important, the notation will be qualified explicitly as "range of iterators" or "range of objects".

[3] The iterator_traits class relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use iterator_traits, and you will instead have to continue using the functions iterator_category, distance_type, and value_type.

Concepts

Trivial Iterator

Category: iterators

Component type: concept

Description

A Trivial Iterator is an object that may be dereferenced to refer to some other object. Arithmetic operations (such as increment and comparison) are not guaranteed to be supported.

Refinement of

Assignable, Equality Comparable, Default Constructible

Associated types

Value type

The type of the value obtained by dereferencing a Trivial Iterator

Notation

X A type that is a model of Trivial Iterator

T The value type of X

x, y Object of type X

t Object of type T

Definitions

A type that is a model of Trivial Iterator may be mutable, meaning that the values referred to by objects of that type may be modified, or constant, meaning that they may not. For example, int* is a mutable iterator type and const int* is a constant iterator type. If an iterator type is mutable, this implies that its value type is a model of Assignable; the converse, though, is not necessarily true.

A Trivial Iterator may have a singular value, meaning that the results of most operations, including comparison for equality, are undefined. The only operation that a is guaranteed to be supported is assigning a nonsingular iterator to a singular iterator.

A Trivial Iterator may have a dereferenceable value, meaning that dereferencing it yields a well-defined value. Dereferenceable iterators are always nonsingular, but the converse is not true. For example, a null pointer is nonsingular (there are well defined operations involving null pointers) even thought it is not dereferenceable.

Invalidating a dereferenceable iterator means performing an operation after which the iterator might be nondereferenceable or singular. For example, if p is a pointer, then delete p invalidates p.

Valid expressions

In addition to the expressions defined in Assignable, Equality Comparable, and Default Constructible, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Default constructor	`X x`
Dereference	*x		Convertible to T [1]
Dereference assignment	`*x = t`	X is mutable
Member access	`x->m`[2]	T is a type for which x.m is defined

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Default constructor	`X x`			x is singular
Dereference	`*x`	x is dereferenceable
Dereference assignment	`*x = t`	x is dereferenceable		*x is a copy of t
Member access	`x->m`	x is dereferenceable	Equivalent to (x).m*

Complexity guarantees

The complexity of operations on trivial iterators is guaranteed to be amortized constant time.

Invariants

Identity

x == y if and only if &*x == &*y

Models

• A pointer to an object that is not part of an array.

Notes

[1] The requirement for the return type of *x is specified as "convertible to T", rather than simply T, because it sometimes makes sense for an iterator to return some sort of proxy object instead of the object that the iterator conceptually points to. Proxy objects are implementation details rather than part of an interface (one use of them, for example, is to allow an iterator to behave differently depending on whether its value is being read or written), so the value type of an iterator that returns a proxy is still T.

[2] Defining operator-> for iterators depends on a feature that is part of the C++ language but that is not yet implemented by all C++ compilers. If your compiler does not yet support this feature, the workaround is to use (*it).m instead of it->m.

Input Iterator

Category: iterators

Component type: concept

Description

An Input Iterator is an iterator that may be dereferenced to refer to some object, and that may be incremented to obtain the next iterator in a sequence. Input Iterators are not required to be mutable.

Refinement of

Trivial iterator.

Associated types

Value type	The type of the value obtained by dereferencing an Input Iterator
Distance type	A signed integral type used to represent the distance from one iterator to another, or the number of elements in a range.

Notation

X A type that is a model of Input Iterator

T The value type of X

i, j Object of type X

t Object of type T

Definitions

An iterator is past-the-end if it points beyond the last element of a container. Past-the-end values are nonsingular and nondereferenceable.

An iterator is valid if it is dereferenceable or past-the-end.

An iterator i is incrementable if there is a "next" iterator, that is, if ++i is well-defined. Past-the-end iterators are not incrementable.

An Input Iterator j is reachable from an Input Iterator i if, after applying operator++ to i a finite number of times, i == j. [1]

The notation [i,j) refers to a range of iterators beginning with i and up to but not including j.

The range [i,j) is a valid range if both i and j are valid iterators, and j is reachable from i [2].

Valid expressions

In addition to the expressions defined in Trivial Iterator, the following expressions must be valid.

Name	Expression	Return type
Preincrement	`++i`	`X&`
Postincrement	`(void)i++`
Postincrement and dereference	`*i++`	`T`

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Dereference	`*t`	i is incrementable
Preincrement	`++i`	i is dereferenceable		i is dereferenceable or past-the-end [3] [4]
Postincrement	`(void)i++`	i is dereferenceable	Equivalent to (void)++i	i is dereferenceable or past-the-end [3] [4]
Postincrement and dereference	`*i++`	i is dereferenceable	Equivalent to {T t = i; ++i; return t;}*	i is dereferenceable or past-the-end [3] [4]

Complexity guarantees

All operations are amortized constant time.

Models

• istream_iterator

Notes

[1] i == j does not imply ++i == ++j.

[2] Every iterator in a valid range [i, j) is dereferenceable, and j is either dereferenceable or past-the-end. The fact that every iterator in the range is dereferenceable follows from the fact that incrementable iterators must be deferenceable.

[3] After executing ++i, it is not required that copies of the old value of i be dereferenceable or that they be in the domain of operator==.

[4] It is not guaranteed that it is possible to pass through the same input iterator twice.

Output Iterator

Category: iterators

Component type: concept

Description

An Output Iterator is a type that provides a mechanism for storing (but not necessarily accessing) a sequence of values. Output Iterators are in some sense the converse of Input Iterators, but they have a far more restrictive interface: they do not necessarily support member access or equality, and they do not necessarily have either an associated distance type or even a value type [1]. Intuitively, one picture of an Output Iterator is a tape: you can write a value to the current location and you can advance to the next location, but you cannot read values and you cannot back up or rewind.

Refinement of

Assignable, DefaultConstructible

Associated types

None. [1]

Notation

X A type that is a model of Output Iterator

x, y Object of type X

Definitions

If x is an Output Iterator of type X, then the expression *x = t; stores the value t into x. Note that operator=, like other C++ functions, may be overloaded; it may, in fact, even be a template function. In general, then, t may be any of several different types. A type T belongs to the set of value types of X if, for an object t of type T, *x = t; is well-defined and does not require performing any non-trivial conversions on t. [1]

An Output Iterator may be singular, meaning that the results of most operations, including copying and dereference assignment, are undefined. The only operation that is guaranteed to be supported is assigning a nonsingular iterator to a singular iterator.

An Output Iterator may be dereferenceable, meaning that assignment through it is defined. Dereferenceable iterators are always nonsingular, but nonsingular iterators are not necessarily dereferenceable.

Valid expressions

Name	Expression	Type requirements	Return type
Default constructor	`X x;X()`
Copy constructor	`X(x)`		`X`
Copy constructor	`X y(x);` or `X y = x;`
Dereference assignment	`*x = t`	t is convertible to a type in the set of value types of X. [1]	Result is not used
Preincrement	`++x`		`X&`
Postincrement	`(void) x++`		`void`
Postincrement and assign	`*x++ = t;`		Result is not used

Expression semantics

Name	Expression	Precondition	Semantics	Postcondition
Default constructor	`X x;X()`			x may be singular
Copy constructor	`X(x)`	x is nonsingular		X(x) = t is equivalent to x = t [2]
Copy constructor	`X x(y);` or `X x = y;`	y is nonsingular		y = t is equivalent to x = t [2]
Dereference assignment	`*x = t`	x is dereferenceable. If there has been a previous assignment through x, then there has been an intervening increment. [3]
Preincrement	`++x`	x is dereferenceable. x has previously been assigned through. If x has previously been incremented, then there has been an intervening assignment through x [3] [4]		x points to the next location into which a value may be stored
Postincrement	`(void) x++`	x is dereferenceable. x has previously been assigned through.	Equivalent to (void) ++x	x points to the next location into which a value may be stored
Postincrement and assign	`*x++ = t;`	x is dereferenceable. If there has been a previous assignment through x, then there has been an intervening increment. [3] [4]	Equivalent to {x = t; ++x; }*	x points to the next location into which a value may be stored

Complexity guarantees

The complexity of operations on output iterators is guaranteed to be amortized constant time.

Models

• ostream_iterator

• insert_iterator

• front_insert_iterator

• back_insert_iterator

Notes

[1] Other iterator types, including Trivial Iterator and Input Iterator, define the notion of a value type, the type returned when an iterator is dereferenced. This notion does not apply to Output Iterators, however, since the dereference operator (unary operator*) does not return a usable value for Output Iterators. The only context in which the dereference operator may be used is assignment through an output iterator: *x = t. Although Input Iterators and output iterators are roughly symmetrical concepts, there is an important sense in which accessing and storing values are not symmetrical: for an Input Iterator ыoperator* must return a unique type, but, for an Output Iterator, in the expression *x = t, there is no reason why operator= must take a unique type. [5] Consequently, there need not be any unique "value type" for Output Iterators.

[2] There should be only one active copy of a single Output Iterator at any one time. That is: after creating and using a copy x of an Output Iterator y, the original output iterator y should no longer be used.

[3] Assignment through an Output Iterator x is expected to alternate with incrementing x, and there must be an assignment through x before x is ever incremented. Any other order of operations results in undefined behavior. That is: {*x = t ; ++x; *x = t2; ++x} is acceptable, but {*x = t; ++x; ++x; *x = t2;} is not.

[4] Note that an Output Iterator need not define comparison for equality. Even if an operator== is defined, x == y need not imply ++x == ++y.

[5] If you are implementing an Output Iterator class X, one sensible way to define *x = t is to define X::operator*() to return an object of some private class X_proxy, and then to define X_proxy::operator=. Note that you may overload X_proxy::operator=, or even define it as a member template; this allows assignment of more than one type through Output Iterators of class X.

Forward Iterator

Category: iterators

Component type: concept

Description

A Forward Iterator is an iterator that corresponds to the usual intuitive notion of a linear sequence of values. It is possible to use Forward Iterators (unlike Input Iterators and Output Iterators) in multipass algorithms. Forward Iterators do not, however, allow stepping backwards through a sequence, but only, as the name suggests, forward.

A type that is a model of Forward Iterator may be either mutable or immutable, as defined in the Trivial Iterators requirements.

Refinement of

Input Iterator, Output Iterator

Associated types

The same as for Input Iterator

Notation

X A type that is a model of Forward Iterator

T The value type of X

i, j Object of type X

t Object of type T

Valid expressions

Forward Iterator does not define any new expressions beyond those defined in Input Iterator. However, some of the restrictions described in Input Iterator are relaxed.

Name	Expression	Return type
Preincrement	`++i`	`X&`
Postincrement	`i++`	`X`

Expression semantics

Forward Iterator does not define any new expressions beyond those defined in Input Iterator. However, some of the restrictions described in Input Iterator are relaxed.

Name	Expression	Precondition	Semantics	Postcondition
Preincrement	`++i`	i is dereferenceable	i points to the next value	i is dereferenceable or past-the-end. &i == &++i . If i == j , then ++i == ++j. [1]
Postincrement	`i++`	i is dereferenceable	Equivalent to {X tmp = i; ++i; return tmp;}	i is dereferenceable or past-the-end. [1]

Complexity guarantees

The complexity of operations on Forward Iterators is guaranteed to be amortized constant time.

Models

• T*

• hash_set<T>::iterator

Notes

[1] The restrictions described in Input Iterator have been removed. Incrementing a forward iterator does not invalidate copies of the old value and it is guaranteed that, if i and j are dereferenceable and i == j, then ++i == ++j. As a consequence of these two facts, it is possible to pass through the same Forward Iterator twice.

Bidirectional Iterator

Category: iterators

Component type: concept

Description

A Bidirectional Iterator is an iterator that can be both incremented and decremented. The requirement that a Bidirectional Iterator can be decremented is the only thing that distinguishes Bidirectional Iterators from Forward Iterators.

Refinement of

Forward Iterator

Associated types

The same as for Forward Iterator.

Notation

X A type that is a model of Bidirectional Iterator

T The value type of X

i, j Object of type X

t Object of type T

Valid expressions

In addition to the expressions defined in Forward Iterator, the following expressions must be valid.

Name	Expression	Return type
Predecrement	`--i`	`X&`
Postdecrement	`i--`	`X`

Expression Semantics

Semantics of an expression is defined only where it is not defined in Forward Iterator.

Name	Expression	Precondition	Semantics	Postcondition
Predecrement	`--i`	i is dereferenceable or past-the-end. There exists a dereferenceable iterator j such that i == ++j.	i is modified to point to the previous element.	i is dereferenceable. &i = &--i . If i == j , then --i == --j . If j is dereferenceable and i == ++j , then --i == j.
Postdecrement	`i--`	i is dereferenceable or past-the-end. There exists a dereferenceable iterator j such that i == ++j.	Equivalent to { X tmp = i; --i; return tmp; }

Complexity guarantees

The complexity of operations on bidirectional iterators is guaranteed to be amortized constant time.

Invariants

Symmetry of increment and decrement

If i is dereferenceable, then ++i; --i; is a null operation. Similarly, --i; ++i; is a null operation.

Models

• T*

• list<T>::iterator

Random Access Iterator

Category: iterators

Component type: concept

Description

A Random Access Iterator is an iterator that provides both increment and decrement (just like a Bidirectional Iterator), and that also provides constant-time methods for moving forward and backward in arbitrary-sized steps. Random Access Iterators provide essentially all of the operations of ordinary C pointer arithmetic.

Refinement of

Bidirectional Iterator, LessThan Comparable

Associated types

The same as for Bidirectional Iterator

Notation

X A type that is a model of Random Access Iterator

T The value type of X

Distance The distance type of X

i, j Object of type X

t Object of type T

n Object of type Distance

Valid expressions

In addition to the expressions defined in Bidirectional Iterator, the following expressions must be valid.

Name	Expression	Type requirements	Return type
Iterator addition	`i += n`		`X&`
Iterator addition	`i + n` or`n + i`		`X`
Iterator subtraction	`i –= n`		`X&`
Iterator subtraction	`i – n`		`X`
Difference	`i – j`		`Distance`
Element operator	`i[n]`		Convertible to T
Element assignment	`i[n] = t`	X is mutable	Convertible to T

Expression semantics

Semantics of an expression is defined only where it differs from, or is not defined in, Bidirectional Iterator or LessThan Comparable.

Name	Expression	Precondition	Semantics	Postcondition
Forward motion	`i += n`	Including i itself, there must be n dereferenceable or past-the-end iterators following or preceding i, depending on whether n is positive or negative.	If n > 0, equivalent to executing ++i n times. If n < 0, equivalent to executing --i n times. If n == 0 , this is a null operation. [1]	i is dereferenceable or past-the-end.
Iterator addition	`i + n` or `n + i`	Same as for i += n	Equivalent to { X tmp = i; return tmp += n; } . The two forms i + n and n + i are identical.	Result is dereferenceable or past-the-end
Iterator subtraction	`i –= n`	Including i itself, there must be n dereferenceable or past-the-end iterators preceding or following i, depending on whether n is positive or negative.	Equivalent to i += (-n).	i is dereferenceable or past-the-end.
Iterator subtraction	`i – n`	Same as for i –= n	Equivalent to { X tmp = i; return tmp –= n; }.	Result is dereferenceable or past-the-end
Difference	`i – j`	Either i is reachable from j or j is reachable from i, or both.	Returns a number n such that i == j + n
Element operator	`i[n]`	i + n exists and is dereferenceable.	Equivalent to *(i + n) [2]
Element assignment	`i[n] = t`	i + n exists and is dereferenceable.	Equivalent to *(i + n) = t [2]	i[n] is a copy of t.
Less	`i < j`	Either i is reachable from j or j is reachable from i, or both. [3]	As described in LessThan Comparable [4]

Complexity guarantees

All operations on Random Access Iterators are amortized constant time. [5]

Invariants

Symmetry of addition and subtraction	If i + n is well-defined, then i += n; i –= n; and (i + n) – n are null operations. Similarly, if i – n is well-defined, then i –= n; i += n; and (i – n) + n are null operations.
Relation between distance and addition	If i – j is well-defined, then i == j + (i – j).
Reachability and distance	If i is reachable from j , then i – j >= 0.
Ordering	operator< is a strict weak ordering, as defined in LessThan Comparable.

Models

• T*

• vector<T>::iterator

• vector<T>::const_iterator

• deque<T>::iterator

• deque<T>::const_iterator

Notes

[1] "Equivalent to" merely means that i += n yields the same iterator as if i had been incremented (decremented) n times. It does not mean that this is how operator+= should be implemented; in fact, this is not a permissible implementation. It is guaranteed that i += n is amortized constant time, regardless of the magnitude of n. [5]

[2] One minor syntactic oddity: in C, if p is a pointer and n is an int, then p[n] and n[p] are equivalent. This equivalence is not guaranteed, however, for Random Access Iterators: only i[n] need be supported. This isn't a terribly important restriction, though, since the equivalence of p[n] and n[p] has essentially no application except for obfuscated C contests.

[3] The precondition defined in LessThan Comparable is that i and j be in the domain of operator<. Essentially, then, this is a definition of that domain: it is the set of pairs of iterators such that one iterator is reachable from the other.

[4] All of the other comparison operators have the same domain and are defined in terms of operator<, so they have exactly the same semantics as described in LessThan Comparable.

[5] This complexity guarantee is in fact the only reason why Random Access Iterator exists as a distinct concept. Every operation in iterator arithmetic can be defined for Bidirectional Iterators; in fact, that is exactly what the algorithms advance and distance do. The distinction is simply that the Bidirectional Iterator implementations are linear time, while Random Access Iterators are required to support random access to elements in amortized constant time. This has major implications for the sorts of algorithms that can sensibly be written using the two types of iterators.

Iterator Tags

Introduction

Category: iterators

Component type: overview

Summary

Iterator tag functions are a method for accessing information that is associated with iterators. Specifically, an iterator type must, as discussed in the Input Iterator requirements, have an associated distance type and value type. [1] It is sometimes important for an algorithm parameterized by an iterator type to be able to determine the distance type and value type. Iterator tags also allow algorithms to determine an iterator's category, so that they can take different actions depending on whether an iterator is an Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator.

Note that the iterator tag functions distance_type, value_type, and iterator_category are an older method of accessing the type information associated with iterators: they were defined in the original STL. The draft C++ standard, however, defines a different and more convenient mechanism: iterator_traits. Both mechanisms are supported [2], for reasons of backwards compatibility, but the older mechanism will eventually be removed.

Description

The basic idea of the iterator tag functions, and of iterator_traits, is quite simple: iterators have associated type information, and there must be a way to access that information. Specifically, iterator tag functions and iterator_traits are used to determine an iterator's value type, distance type, and iterator category.

An iterator's category is the most specific concept that it is a model of: Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. This information is expressed in the C++ type system by defining five category tag types, input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, and random_access_iterator_tag, each of which corresponds to one of those concepts. [3]

The function iterator_category takes a single argument, an iterator, and returns the tag corresponding to that iterator's category. That is, it returns a random_access_iterator_tag if its argument is a pointer, a bidirectional_iterator_tag if its argument is a list::iterator, and so on. Iterator_traits provides the same information in a slightly different way: if I is an iterator, then iterator_traits::iterator_category is a nested typedef: it is one of the five category tag types.

An iterator's value type is the type of object that is returned when the iterator is dereferenced. (See the discussion in the Input Iterator requirements.) Ideally, one might want value_type to take a single argument, an iterator, and return the iterator's value type. Unfortunately, that's impossible: a function must return an object, and types aren't objects. Instead, value_type returns the value (T*)0, where T is the argument's value type. The iterator_traits class, however, does not have this restriction: iterator_traits::value_type is a type, not a value. It is a nested typedef, and it can be used in declarations of variables, as an function's argument type or return type, and in any other ways that C++ types can be used.

(Note that the function value_type need not be defined for Output Iterators, since an Output Iterator need not have a value type. Similarly, iterator_traits::value_type is typically defined as void when I is an output iterator)

An iterator's distance type, or difference type (the terms are synonymous) is the type that is used to represent the distance between two iterators. (See the discussion in the Input Iterator requirements.) The function distance_type returns this information in the same form that value_type does: its argument is an iterator, and it returns the value (Distance*)0, where Distance is the iterator's distance type. Similarly, iterator_traits::difference_type is I's distance type.

Just as with value_type, the function distance_type need not be defined for Output Iterators, and, if I is an Output Iterator, iterator_traits::difference_type may be defined as void. An Output Iterator need not have a distance type.

The functions iterator_category, value_type, and distance_type must be provided for every type of iterator. (Except, as noted above, that value_type and distance_type need not be provided for Output Iterators.) In principle, this is simply a matter of overloading: anyone who defines a new iterator type must define those three functions for it. In practice, there's a slightly more convenient method. The STL defines five base classes, output_iterator, input_iterator, forward_iterator, bidirectional_iterator, and random_access_iterator. The functions iterator_category, value_type, and distance_type are defined for those base classes. The effect, then, is that if you are defining a new type of iterator you can simply derive it from one of those base classes, and the iterator tag functions will automatically be defined correctly. These base classes contain no member functions or member variables, so deriving from one of them ought not to incur any overhead.

(Again, note that base classes are provided solely for the convenience of people who define iterators. If you define a class Iter that is a new kind of Bidirectional Iterator, you do not have to derive it from the base class bidirectional_iterator. You do, however, have to make sure that iterator_category, value_type, and distance_type are defined correctly for arguments of type Iter, and deriving Iter from bidirectional_iterator is usually the most convenient way to do that.)

Examples

This example uses the value_type iterator tag function in order to declare a temporary variable of an iterator's value type. Note the use of an auxiliary function, __iter_swap. This is a very common idiom: most uses of iterator tags involve auxiliary functions.

template <class ForwardIterator 1, class ForwardIterator 2, class ValueType>

inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {

ValueType tmp = *a;

*a = *b;

*b = tmp;

}

template <class ForwardIterator 1, class ForwardIterator 2>

inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {

__iter_swap(a, b, value_type(a));

}

This example does exactly the same thing, using iterator_traits instead. Note how much simpler it is: the auxiliary function is no longer required.

template <class ForwardIterator 1, class ForwardIterator 2>

inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {

iterator_traits <ForwardIterator1>::value_type tmp = *a;

*a = *b;

*b = tmp;

}

This example uses the iterator_category iterator tag function: reverse can be implemented for either Bidirectional Iterator s or for Random Access Iterators , but the algorithm for Random Access Iterators is more efficient. Consequently, reverse is written to dispatch on the iterator category. This dispatch takes place at compile time, and should not incur any run-time penalty.

template <class BidirectionalIterator>

void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag ) {

while (true)

if (first == last || first == –last) return;

else iter_swap(first++, last);

}

template <class RandomAccessIterator>

void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag) {

while (first < last) iter_swap(first++, --last);

}

template <class BidirectionalIterator>

inline void reverse (BidirectionalIterator first, BidirectionalIterator last) {

__reverse(first, last, iterator_category(first));

}

In this case, iterator_traits would not be different in any substantive way: it would still be necessary to use auxiliary functions to dispatch on the iterator category. The only difference is changing the top-level function to

template <class BidirectionalIterator>

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

__reverse(first, last, iterator_traits<first>::iterator_category());

}

Types

• output_iterator

• input_iterator

• forward_iterator

• bidirectional_iterator

• random_access_iterator

• output_iterator_tag

• input_iterator_tag

• forward_iterator_tag

• bidirectional_iterator_tag

• random_access_iterator_tag

• iterator_traits

Functions

• iterator_category

• value_type

• distance_type

Notes

[1] Output Iterators have neither a distance type nor a value type; in many ways, in fact, Output Iterators aren't really iterators. Output iterators do not have a value type, because it is impossible to obtain a value from an output iterator but only to write a value through it. They do not have a distance type, similarly, because it is impossible to find the distance from one output iterator to another. Finding a distance requires a comparison for equality, and output iterators do not support operator==.

[2] The iterator_traits class relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use iterator_traits, and you will have to continue to use the older iterator tag functions.

[3] Note that Trivial Iterator does not appear in this list. The Trivial Iterator concept is introduced solely for conceptual clarity; the STL does not actually define any Trivial Iterator types, so there is no need for a Trivial Iterator tag. There is, in fact, a strong reason not to define one: the C++ type system does not provide any way to distinguish between a pointer that is being used as a trivial iterator (that is, a pointer to an object that isn't part of an array) and a pointer that is being used as a Random Access Iterator into an array.

iterator_traits<Iterator>

Category: iterators

Component type: type

Description

As described in the Iterator Overview, one of the most important facts about iterators is that they have associated types. An iterator type, for example, has an associated value type : the type of object that the iterator points to. It also has an associated distance type, or difference type, a signed integral type that can be used to represent the distance between two iterators.

(Pointers, for example, are iterators; the value type of int* is int. Its distance type is ptrdiff_t, because, if p1 and p2 are pointers, the expression p1 – p2 has type ptrdiff_t.)

Generic algorithms often need to have access to these associated types; an algorithm that takes a range of iterators, for example, might need to declare a temporary variable whose type is the iterators' value type. The class iterator_traits is a mechanism that allows such declarations.

The most obvious way to allow declarations of that sort would be to require that all iterators declare nested types; an iterator I's value type, for example, would be I::value_type. That can't possibly work, though. Pointers are iterators, and pointers aren't classes; if I is (say) int* , then it's impossible to define I::value_type to be int. Instead, I's value type is written iterator_traits::value_type. iterator_traits is a template class that contains nothing but nested typedef s; in addition to value_type, iterator_traits defines the nested types iterator_category, difference_type, pointer, and reference.

The library contains two definitions of iterator_traits: a fully generic one, and a specialization that is used whenever the template argument is a pointer type [1]. The fully generic version defines iterator_traits::value_type as a synonym for I::value_type, iterator_traits::difference_type as a synonym for I::difference_type, and so on. Since pointers don't have nested types, iterator_traits<T*> has a different definition.

The implementation of iterator_traits is actually simpler than this discussion.

template <class Iterator>

struct iterator_traits {

typedef typename Iterator::iterator_category iterator_category;

typedef typename Iterator::value_type value_type;

typedef typename Iterator::difference_type difference_type;

typedef typename Iterator::pointer pointer;

typedef typename Iterator::reference reference;

};

template <class T>

struct iterator_traits<T*> {

typedef random_access_iterator_tag iterator_category;

typedef T value_type;

typedef ptrdiff_t difference_type;

typedef T* pointer;

typedef T& reference;

};

If you are defining a new iterator type I, then you must ensure that iterator_traits is defined properly. There are two ways to do this. First, you can define your iterator so that it has nested types I::value_type, I::difference_type, and so on. Second, you can explicitly specialize iterator_traits for your type. The first way is almost always more convenient, however, especially since you can easily ensure that your iterator has the appropriate nested types just by inheriting from one of the base classes input_iterator, output_iterator, forward_iterator, bidirectional_iterator, or random_access_iterator.

Note that iterator_traits is new; it was added to the draft C++ standard relatively recently. Both the old iterator tags mechanism and the new iterator_traits mechanism are currently supported [1 , but the old iterator tag functions are no longer part of the standard C++ library and they will eventually be removed.

Example

This generic function returns the last element in a non-empty range. Note that there is no way to define a function with this interface in terms of the old value_type function, because the function's return type must be declared to be the iterator's value type.

template <class InputIterator>

iterator_traits<InputIterator>::value_type last_value(InputIterator first, InputIterator last) {

iterator_traits<InputIterator>::value_type result = *first;

for (++first; first != last; ++first) result = *first;

return result;

}

(Note: this is an example of how to use iterator_traits; it is not an example of good code. There are better ways of finding the last element in a range of bidirectional iterators, or even forward iterators.)

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
`Iterator`	The iterator type whose associated types are being accessed.

Model of

Default Constructible, Assignable

Type requirements

• Iterator is a model of one of the iterator concepts. (Input Iterator, Output Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator.)

Public base classes

None.

Members

None, except for nested types.

Member	Description
`iterator_category`	One of the types input_iterator_tag, output_iterator_tag, forward_iterator_tag, bidirectional_iterator_tag, or random_access_iterator_tag. An iterator's category is the most specific iterator concept that it is a model of.
`value_type`	Iterator's value type, as defined in the Trivial Iterator requirements.
`difference_type`	Iterator's distance type, as defined in the Input Iterator requirements.
`pointer`	Iterator's pointer type: a pointer to its value type.
`reference`	Iterator's reference type: a reference to its value type.

Notes

[1] The iterator_traits class relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use iterator_traits, and you will have to continue using the old iterator tag functions iterator_category, distance_type, and value_type. This is one reason that those functions have not yet been removed.

iterator_category

Category: iterators

Component type: function

Prototype

Iterator_category is overloaded; it is in fact six different functions.

inline output_iterator_tag iterator_category(const output_iterator&);

template <class T, class Distance> inline input_iterator_tag

iterator_category(const input_iterator<T, Distance>&);

template <class T, class Distance> inline forward_iterator_tag

iterator_category(const forward_iterator<T, Distance>&);

template <class T, class Distance> inline bidirectional_iterator_tag

iterator_category(const bidirectional_iterator<T, Distance>&);

template <class T, class Distance> inline random_access_iterator_tag

iterator_category(const random_access_iterator<T, Distance>&);

template <class T> inline random_access_iterator_tag iterator_category(const T*);

Description

Iterator_category is an iterator tag function: it is used to determine the category to which an iterator belongs. Specifically, every iterator must belong to a type that is a model of the concept Output Iterator, Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1] Iterator_category returns an object of class output_iterator_tag, input_iterator_tag, forward_iterator_tag, or random_access_iterator_tag, depending on which concept the type of iterator_category 's argument is a model of. [2] This information is useful in the case of an algorithm that has a sensible definition for more than one category of iterator, but whose definition is different depending on the category.

Although iterator_category looks like a single function whose return type depends on its argument type, in reality it is a set of functions; the name iterator_category is overloaded. The function iterator_category must be overloaded for every iterator type.

In practice, ensuring that iterator_category is defined requires essentially no work at all. It is already defined for pointers, and for the base classes input_iterator, output_iterator, forward_iterator, bidirectional_iterator, and random_access_iterator. If you are implementing a new type of forward iterator, for example, you can simply derive it from the base class forward_iterator; this means that iterator_category (along with distance_type and value_type ) will automatically be defined for your iterator. These base classes are empty: they contain no member functions or member variables, but only type information. Using them should therefore incur no overhead.

Note that, while the function iterator_category was present in the original STL, it is no longer present in the most recent draft C++ standard: it has been replaced by the iterator_traits class. At present both mechanisms are supported [3], but eventually iterator_category will be removed.

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This function is no longer part of the C++ standard, although it was present in early drafts of the standard. It is retained in this implementation for backward compatibility.

Requirements on types

The argument of iterator_category must be an iterator.

Preconditions

None. Iterator_category's argument is even permitted to be a singular iterator.

Complexity

At most amortized constant time. In many cases, a compiler should be able to optimize away iterator_category entirely.

Example

Reverse can be implemented for either Bidirectional Iterators or for Random Access Iterators, but the algorithm for Random Access Iterators is more efficient. Consequently, reverse uses iterator_category to select whichever algorithm is appropriate for the iterator type. This dispatch takes place at compile time, and should not incur any run-time penalty.

template <class BidirectionalIterator>

void __reverse(BidirectionalIterator first, BidirectionalIterator last, bidirectional_iterator_tag ) {

while (true)

if (first == last || first == --last) return;

else iter_swap(first++, last);

}

template <class RandomAccessIterator>

void __reverse(RandomAccessIterator first, RandomAccessIterator last, random_access_iterator_tag ) {

while (first < last) iter_swap(first++, --last);

}

template <class BidirectionalIterator>

inline void reverse(BidirectionalIterator first, BidirectionalIterator last) {

__reverse(first, last, iterator_category(first));

}

Notes

[1] The STL also defines one other concept, Trivial Iterator. This concept is introduced only for conceptual clarity, however, in order to separate the axioms related to an object that refers to another object from those related to iteration over a range. In fact, the STL does not define any types that are Trivial Iterators. Although built-in C pointers may be Trivial Iterators, the C type system does not allow a distinction between pointers that are Trivial Iterators and pointers that are Random Access Iterators into C arrays. Consequently, there is no Trivial Iterator category tag.

[2] Any type that is a model of Forward Iterator is also a model of Input Iterator, any type that is a model of Bidirectional Iterator is also a model of Forward Iterator, and any type that is a model of Random Access Iterator is also a model of Bidirectional Iterator. Iterator_category must return a tag representing the most specific concept that its argument is a model of. If its argument is a vector::iterator, for example, then it must return random_access_iterator_tag.

[3] The iterator_traits class relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use iterator_traits, and you will have to continue using the functions iterator_category, distance_type, and value_type. This is one reason that those functions have not yet been removed.

distance_type

Category: iterators

Component type: function

Prototype

Distance_type is overloaded; it is in fact five different functions.

template <class T, class Distance>

inline Distance* distance_type(const input_iterator <T, Distance>&);

template <class T, class Distance>

inline Distance* distance_type(const forward_iterator <T, Distance>&);

template <class T, class Distance>

inline Distance* distance_type(const bidirectional_iterator <T, Distance>&);

template <class T, class Distance>

inline Distance* distance_type(const random_access_iterator <T, Distance>&);

template <class T> inline ptrdiff_t* distance_type(const T*);

Description

Distance_type is an iterator tag function: it is used to determine the distance type associated with an iterator. An Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator [1] must have associated with it some signed integral type that is used to represent the distance between two iterators of that type. In some cases (such as an algorithm that must declare a local variable that represents the size of a range), it is necessary to find out an iterator's distance type. Accordingly, distance_type(Iter) returns (Distance*)0, where Distance is Iter's distance type.

Although distance_type looks like a single function whose return type depends on its argument type, in reality it is a set of functions; the name distance_type is overloaded. The function distance_type must be overloaded for every iterator type [1].

In practice, ensuring that distance_type is defined requires essentially no work at all. It is already defined for pointers, and for the base classes input_iterator, forward_iterator, bidirectional_iterator, and random_access_iterator. If you are implementing a new type of forward iterator, for example, you can simply derive it from the base class forward_iterator; this means that distance_type (along with iterator_category and value_type) will automatically be defined for your iterator. These base classes are empty: they contain no member functions or member variables, but only type information. Using them should therefore incur no overhead.

Note that, while the function distance_type was present in the original STL, it is no longer present in the most recent draft C++ standard: it has been replaced by the iterator_traits class. At present both mechanisms are supported [2], but eventually distance_type will be removed.

Definition

Requirements on types

The argument of distance_type must be an Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1]

Preconditions

None. Distance_type's argument is even permitted to be a singular iterator.

Complexity

At most amortized constant time. In many cases, a compiler should be able to optimize away distance_type entirely.

Example

template <class RandomAccessIterator, class LessThanComparable, class Distance>

RandomAccessIterator __lower_bound(RandomAccessIterator first, RandomAccessIterator last, const LessThanComparable& value, Distance*) Distance len = last – first;

Distance half;

RandomAccessIterator middle;

while (len > 0) {

half = len / 2;

middle = first + half;

if (*middle < value) {

first = middle + 1;

len = len – half – 1;

} else len = half;

}

return first;

}

template <class RandomAccessIterator, class LessThanComparable>

inline RandomAccessIterator lower_bound(RandomAccessIterator first, RandomAccessIterator last, const LessThanComparable& value) {

return __lower_bound(first, last, value, distance_type(first));

}

The algorithm lower_bound (a type of binary search) takes a range of iterators, and must declare a local variable whose type is the iterators' distance type. It uses distance type, and an auxiliary function, so that it can declare that variable. [3] Note: this is a simplified example. The actual algorithm lower_bound can operate on a range of Random Access Iterators or a range of Forward Iterators. It uses both distance_type and iterator_category.

Notes

[1] Note that distance_type is not defined for Output Iterators or for Trivial Iterators. There is no meaningful definition of a distance for either of those concepts, so there is no need for a distance type.

[3] This use of an auxiliary function is an extremely common idiom: distance_type is almost always used with auxiliary functions, simply because it returns type information in a form that is hard to use in any other way. This is one of the reasons that distance_type is so much less convenient than iterator_traits.

value_type

Category: iterators

Component type: function

Prototype

Value_type is overloaded; it is in fact five different functions.

template <class T, class Distance>

inline T* value_type(const input_iterator<T, Distance>&);

template <class T, class Distance>

inline T* value_type(const forward_iterator<T, Distance>&);

template <class T, class Distance>

inline T* value_type(const bidirectional_iterator<T, Distance>&);

template <class T, class Distance>

inline T* value_type(const random_access_iterator<T, Distance>&);

template <class T>

inline T* value_type(const T*);

Description

Value_type is an iterator tag function: it is used to determine the value type associated with an iterator. An iterator's value type is the type of object returned when the iterator is dereferenced; Output Iterators do not have value types (Output Iterators may only be used for storing values, not for accessing values), but Input Iterators, Forward Iterators, Bidirectional Iterators, and Random Access Iterators do. [1]

In some cases, such as an algorithm that must declare a local variable that holds a value returned from dereferencing an iterator, it is necessary to find out an iterator's value type. Accordingly, value_type(Iter) returns (T*)0 , where T is Iter's value type.

Although value_type looks like a single function whose return type depends on its argument type, in reality it is a set of functions; the name value_type is overloaded. The function value_type must be overloaded for every iterator type [1].

In practice, ensuring that value_type is defined requires essentially no work at all. It is already defined for pointers, and for the base classes input_iterator, forward_iterator, bidirectional_iterator, and random_access_iterator. If you are implementing a new type of forward iterator, for example, you can simply derive it from the base class forward_iterator; this means that value_type (along with iterator_category and distance_type) will automatically be defined for your iterator. These base classes are empty: they contain no member functions or member variables, but only type information. Using them should therefore incur no overhead.

Note that, while the function value_type was present in the original STL, it is no longer present in the most recent draft C++ standard: it has been replaced by the iterator_traits class At present both mechanisms are supported [2], but eventually value_type will be removed.

Definition

Requirements on types

The argument of value_type must be an Input Iterator, Forward Iterator, Bidirectional Iterator, or Random Access Iterator. [1]

Preconditions

None. Value_type's argument is even permitted to be a singular iterator.

Complexity

At most amortized constant time. In many cases, a compiler should be able to optimize away value_type entirely.

Example

This example uses the value_type iterator tag function in order to declare a temporary variable of an iterator's value type.

template <class ForwardIterator 1, class ForwardIterator 2, class ValueType>

inline void __iter_swap(ForwardIterator1 a, ForwardIterator2 b, ValueType*) {

T tmp = *a;

*a = *b;

*b = tmp;

}

template <class ForwardIterator 1, class ForwardIterator 2>

inline void iter_swap(ForwardIterator1 a, ForwardIterator2 b) {

__iter_swap(a, b, value_type (a));

}

Notes

[1] Note that distance_type is not defined for Output Iterators or for Trivial Iterators. In the case of Output Iterators, this is because an Output Iterator does not have a value type: it is not possible to dereference an Output Iterator and obtain a value. In the case of Trivial Iterators, this is because the concept was introduced only for conceptual clarity, in order to separate the axioms related to an object that refers to another object from those related to iteration over a range. In fact, the STL does not define any types that are Trivial Iterators. Although built-in C pointers may be Trivial Iterators, the C type system does not allow a distinction between pointers that are Trivial Iterators and pointers that are Random Access Iterators into C arrays. Consequently, there is no Trivial Iterator category tag or iterator base.

Iterator tag classes

input_iterator_tag

Category: iterators

Component type: type

Description

Input_iterator_tag is an empty class: it has no member functions, member variables, or nested types. It is used solely as a "tag": a representation of the Input Iterator concept within the C++ type system. Specifically, it is used as a return value for the function iterator_category. Iterator_category takes a single argument, an iterator, and returns an object whose type depends on the iterator's category. Iterator_category's return value is of type input_iterator_tag if its argument is an Input Iterator.

Example

See iterator_category

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

None.

Model of

Assignable

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

output_iterator_tag

Category: iterators

Component type: type

Description

Output_iterator_tag is an empty class: it has no member functions, member variables, or nested types. It is used solely as a "tag": a representation of the Output Iterator concept within the C++ type system. Specifically, it is used as a return value for the function iterator_category. Iterator_category takes a single argument, an iterator, and returns an object whose type depends on the iterator's category. Iterator_category's return value is of type output_iterator_tag if its argument is an Output Iterator.

Example

See iterator_category

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

None.

Model of

Assignable

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

forward_iterator_tag

Category: iterators

Component type: type

Description

Forward_iterator_tag is an empty class: it has no member functions, member variables, or nested types. It is used solely as a "tag": a representation of the Forward Iterator concept within the C++ type system. Specifically, it is used as a return value for the function iterator_category. Iterator_category takes a single argument, an iterator, and returns an object whose type depends on the iterator's category. Iterator_category's return value is of type forward_iterator_tag if its argument is a Forward Iterator.

Example

See iterator_category

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

None.

Model of

Assignable

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

bidirectional_iterator_tag

Category: iterators

Component type: type

Description

Bidirectional_iterator_tag is an empty class: it has no member functions, member variables, or nested types. It is used solely as a "tag": a representation of the Bidirectional Iterator concept within the C++ type system. Specifically, it is used as a return value for the function iterator_category. Iterator_category takes a single argument, an iterator, and returns an object whose type depends on the iterator's category. Iterator_category's return value is of type bidirectional_iterator_tag if its argument is a Bidirectional Iterator.

Example

See iterator_category

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

None.

Model of

Assignable

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

random_access_iterator_tag

Category: iterators

Component type: type

Description

Random_access_iterator_tag is an empty class: it has no member functions, member variables, or nested types. It is used solely as a "tag": a representation of the Random Access Iterator concept within the C++ type system. Specifically, it is used as a return value for the function iterator_category. Iterator_category takes a single argument, an iterator, and returns an object whose type depends on the iterator's category. Iterator_category 's return value is of type random_access_iterator_tag if its argument is a Random Access Iterator.

Example

See iterator_category.

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

None.

Model of

Assignable.

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

Iterator base classes

input_iterator<T, Distance>

Category: iterators

Component type: type

Description

Input_iterator is an iterator base class: it is intended that an iterator that is a model of Input Iterator, and whose value type and distance type are T and Distance, may be defined by inheriting from input_iterator<T, Distance> [1]. Input_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category, distance_type, and value_type.

Example

class my_input_iterator : public input_iterator<double> {

…

};

This declares my_input_iterator to be an Input Iterator whose value type is double and whose distance type is ptrdiff_t. If Iter is an object of class my_input_iterator, then iterator_category(Iter) will return input_iterator_tag(), value_type(Iter) will return (double*)0 , and distance_type(Iter) will return (ptrdiff_t*)0.

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This class is no longer part of the C++ standard, although it was present in early drafts of the standard. It is retained in this implementation for backward compatibility.

Template parameters

Parameter	Description	Default
`T`	The iterator's value type
`Distance`	The iterator's distance type	`ptrdiff_t`

Model of

Assignable

Public base classes

None

Type requirements

The distance type must be a signed integral type.

Public base classes

None.

Members

None.

New Members

None.

Notes

[1] It is not required that an Input Iterator inherit from the base input_iterator. It is, however, required that the functions iterator_category, distance_type, and value_type be defined for every Input Iterator. (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Input Iterator.) Since those functions are defined for the base input_iterator, the easiest way to ensure that are defined for a new iterator class is to derive that class from input_iterator and rely on the derived-to-base standard conversion of function arguments.

output_iterator

Category: iterators

Component type: type

Description

Output_iterator is an iterator base class: it is intended that an iterator that is a model of Output Iterator may be defined by inheriting from output_iterator [1]. Output_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category, distance_type, and value_type.

Example

class my_output_iterator : public output_iterator {

…

};

This declares my_output_iterator to be an Output Iterator. If Iter is an object of class my_output_iterator, then iterator_category(Iter) will return output_iterator_tag(), and distance_type and value_type will be undefined for objects of class my_output_iterator.

Definition

Template parameters

None. (Note that Output Iterators need have neither distance types nor value types.)

Model of

Assignable

Public base classes

None

Type requirements

None.

Public base classes

None.

Members

None.

New Members

None.

Notes

[1] It is not required that an Output Iterator inherit from the base output_iterator. It is, however, required that the function iterator_category be defined for every Output Iterator. (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Output Iterator.) Since it is defined for the base output_iterator, the easiest way to ensure that it defined for a new type is to derive that class from output_iterator and rely on the derived-to-base standard conversion of function arguments.

forward_iterator<T, Distance>

Category: iterators

Component type: type

Description

Forward_iterator is an iterator base class: it is intended that an iterator that is a model of Forward Iterator, and whose value type and distance type are T and Distance, may be defined by inheriting from forward_iterator<T, Distance>[1]. Forward_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category, distance_type, and value_type.

Example

class my_forward_iterator : public forward_iterator<double> {

…

};

This declares my_forward_iterator to be a Forward Iterator whose value type is double and whose distance type is ptrdiff_t. If Iter is an object of class my_forward_iterator, then iterator_category(Iter) will return forward_iterator_tag(), value_type(Iter) will return (double*)0, and distance_type(Iter) will return (ptrdiff_t*)0.

Definition

Template parameters

Parameter	Description	Default
`T`	The iterator's value type
`Distance`	The iterator's distance type	`ptrdiff_t`

Model of

Assignable

Public base classes

None

Type requirements

The distance type must be a signed integral type.

Public base classes

None.

Members

None.

New Members

None.

Notes

[1] It is not required that a Forward Iterator inherit from the base forward_iterator. It is, however, required that the functions iterator_category, distance_type, and value_type be defined for every Forward Iterator. (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Forward Iterator.) Since those functions are defined for the base forward_iterator, the easiest way to ensure that are defined for a new type is to derive that class from forward_iterator and rely on the derived-to-base standard conversion of function arguments.

bidirectional_iterator<T, Distance>

Category: iterators

Component type: type

Description

Bidirectional_iterator is an iterator base class: it is intended that an iterator that is a model of Bidirectional Iterator, and whose value type and distance type are T and Distance, may be defined by inheriting from bidirectional_iterator<T, Distance> [1]. Bidirectional_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category, distance_type, and value_type.

Example

class my_bidirectional_iterator : public bidirectional_iterator<double> {

…

};

This declares my_bidirectional_iterator to be a Bidirectional Iterator whose value type is double and whose distance type is ptrdiff_t. If Iter is an object of class my_bidirectional_iterator, then iterator_category(Iter) will return bidirectional_iterator_tag(), value_type(Iter) will return (double*)0, and distance_type(Iter) will return (ptrdiff_t*)0.

Definition

Template parameters

Parameter	Description	Default
`T`	The iterator's value type
`Distance`	The iterator's distance type	`ptrdiff_t`

Model of

Assignable

Public base classes

None

Type requirements

The distance type must be a signed integral type.

Public base classes

None.

Members

None.

New Members

None.

Notes

[1] It is not required that a Bidirectional Iterator inherit from the base bidirectional_iterator. It is, however, required that the functions iterator_category, distance_type, and value_type be defined for every Bidirectional Iterator. (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Bidirectional Iterator.) Since those functions are defined for the base bidirectional_iterator, the easiest way to ensure that are defined for a new type is to derive that class from bidirectional_iterator and rely on the derived-to-base standard conversion of function arguments.

random_access_iterator<T, Distance>

Category: iterators

Component type: type

Description

Random_access_iterator is an iterator base class: it is intended that an iterator that is a model of Random Access Iterator, and whose value type and distance type are T and Distance, may be defined by inheriting from random_access_iterator<T, Distance> [1]. Random_access_iterator is entirely empty: it has no member functions, member variables, or nested types. It exists solely to simplify the definition of the functions iterator_category, distance_type, and value_type.

Example

class my_random_access_iterator : public random_access_iterator<double> {

…

};

This declares my_random_access_iterator to be a Random Access Iterator whose value type is double and whose distance type is ptrdiff_t. If Iter is an object of class my_random_access_iterator, then iterator_category(Iter) will return random_access_iterator_tag(), value_type(Iter) will return (double*)0 , and distance_type(Iter) will return (ptrdiff_t*)0.

Definition

Template parameters

Parameter	Description	Default
`T`	The iterator's value type
`Distance`	The iterator's distance type	`ptrdiff_t`

Model of

Assignable

Public base classes

None

Type requirements

The distance type must be a signed integral type.

Public base classes

None.

Members

None.

New Members

None.

Notes

[1] It is not required that a Random Access Iterator inherit from the base random_access_iterator. It is, however, required that the functions iterator_category, distance_type, and value_type be defined for every Random Access Iterator . (Or, if you are using the iterator_traits mechanism, that iterator_traits is properly specialized for every Random Access Iterator.) Since those functions are defined for the base random_access_iterator, the easiest way to ensure that are defined for a new type is to derive that class from random_access_iterator and rely on the derived-to-base standard conversion of function arguments.

Iterator functions

distance

Categories: algorithms, iterators

Component type: function

Prototype

Distance is an overloaded name; there are actually two distance functions.

template <class InputIterator>

inline iterator_traits<InputIterator>::difference_type distance(InputIterator first, InputIterator last);

template <class InputIterator, class Distance>

void distance(InputIterator first, InputIterator last, Distance& n);

Description

Finds the distance between first and last, i.e. the number of times that first must be incremented until it is equal to last. [1] The first version of distance, which takes two arguments, simply returns that distance; the second version, which takes three arguments and which has a return type of void, increments n by that distance.

The second version of distance was the one defined in the original STL, and the first version is the one defined in the draft C++ standard; the definition was changed because the older interface was clumsy and error-prone. The older interface required the use of a temporary variable, and it has semantics that are somewhat nonintuitive: it increments n by the distance from first to last , rather than storing that distance in n. [2]

Both interfaces are currently supported [3], for reasons of backward compatibility, but eventually the older version will be removed.

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Requirements on types

For the first version:

• InputIterator is a model of Input Iterator.

For the second version:

• InputIterator is a model of Input Iterator.

• Distance is an integral type that is able to represent a distance between iterators of type InputIterator.

Preconditions

• [first, last) is a valid range, as defined in the Input Iterator requirements.

Complexity

Constant time if InputIterator is a model of random access iterator, otherwise linear time.

Example

int main() {

list<int> L;

L.push_back(0);

L.push_back(1);

assert(distance(L.begin(), L.end()) == L.size());

}

Notes

[1] This is the reason that distance is not defined for output iterators: it is impossible to compare two output iterators for equality.

[2] Forgetting to initialize n to 0 is a common mistake.

[3] The new distance interface uses the iterator_traits class, which relies on a C++ feature known as partial specialization. Many of today's compilers don't implement the complete standard; in particular, many compilers do not support partial specialization. If your compiler does not support partial specialization, then you will not be able to use the newer version of distance, or any other STL components that involve iterator_traits.

advance

Categories: algorithms, iterators

Component type: function

Prototype

template <class InputIterator, class Distance>

void advance(InputIterator& i, Distance n);

Description

Advance(i, n) increments the iterator i by the distance n . If n > 0 it is equivalent to executing ++i n times, and if n < 0 it is equivalent to executing --i n times. If n == 0 , the call has no effect.

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Requirements on types

• InputIterator is a model of Input Iterator.

• Distance is an integral type that is convertible to InputIterator's distance type.

Preconditions

• i is nonsingular.

• Every iterator between i and i+n (inclusive) is nonsingular.

• If InputIterator is a model of input iterator or forward iterator, then n must be nonnegative. If InputIterator is a model of bidirectional iterator or random access iterator, then this precondition does not apply.

Complexity

Constant time if InputIterator is a model of random access iterator, otherwise linear time.

Example

list<int> L;

L.push_back(0);

L.push_back(1);

list<int>::iterator i = L.begin();

advance(i, 2);

assert(i == L.end());

Iterator classes

istream_iterator<T, Distance>

Category: iterators

Component type: type

Description

An istream_iterator is an Input Iterator that performs formatted input of objects of type T from a particular istream. When end of stream is reached, the istream_iterator takes on a special end of stream value, which is a past-the-end iterator. Note that all of the restrictions of an Input Iterator must be obeyed, including the restrictions on the ordering of operator* and operator++ operations.

Example

Fill a vector with values read from standard input.

vector<int> V;

copy(istream_iterator<int>(cin), istream_iterator<int>(), back_inserter(V));

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description	Default
T	The istream_iterator's value type. Operator* returns a const T&.
`Distance`	The istream_iterator 's distance type.	`ptrdiff_t`

Model of

Input Iterator

Type requirements

The value type T must be a type such that cin >> T is a valid expression.

The value type T must be a model of Default Constructible.

The distance type must, as described in the Input Iterator requirements, be a signed integral type.

Public base classes

None.

Members

Member	Where defined	Description
`istream_iterator()`	`istream_iterator`	See below.
`istream_iterator(istream&)`	`istream_iterator`	See below.
`istream_iterator(const istream_iterator&)`	Trivial Iterator	The copy constructor
`istream_iterator& operator=(const istream_iterator&)`	Trivial Iterator	The assignment operator
`const T& operator*() const`	Input Iterator	Returns the next object in the stream.
`istream_iterator& operator++()`	Input Iterator	Preincrement.
`istream_iterator& operator++(int)`	Input Iterator	Postincrement.
`bool operator==(const istream_iterator&, const istream_iterator&)`	Trivial iterator	The equality operator. This is a global function, not a member function.
`input_iterator_tag iterator_category(const istream_iterator&)`	iterator tags	Returns the iterator's category.
`T* value_type(const istream_iterator&)`	iterator tags	Returns the iterator's value type.
`Distance* distance_type(const istream_iterator&)`	iterator tags	Returns the iterator's distance type.

New members

These members are not defined in the Input Iterator requirements, but are specific to istream_iterator.

Function	Description
`istream_iterator()`	The default constructor: Constructs an end-of-stream iterator. This is a past-the-end iterator, and it is useful when constructing a "range".
`istream_iterator(istream& s)`	Creates an istream_iterator that reads values from the input stream s. When s reaches end of stream, this iterator will compare equal to an end-of-stream iterator created using the default constructor.

ostream_iterator<T>

Category: iterators

Component type: type

Description

An ostream_iterator is an Output Iterator that performs formatted output of objects of type T to a particular ostream. Note that all of the restrictions of an Output Iterator must be obeyed, including the restrictions on the ordering of operator* and operator++ operations.

Example

Copy the elements of a vector to the standard output, one per line.

vector<int> V;

// …

copy(V.begin(), V.end(), ostream_iterator<int>(cout, "\n"));

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
`T`	The type of object that will be written to the ostream. The set of value types of an ostream_iterator consists of a single type, T.

Model of

Output Iterator.

Type requirements

T must be a type such that cout << T is a valid expression.

Public base classes

None.

Members

Member	Where defined	Description
`ostream_iterator(ostream&)`	`ostream_iterator`	See below.
`ostream_iterator(ostream&, const char* s)`	`ostream_iterator`	See below.
`ostream_iterator(const ostream_iterator&)`	Output Iterator	The copy constructor
`ostream_iterator& operator=(const ostream_iterator&)`	Output Iterator	The assignment operator
`ostream_iterator& operator=(const T&)`	Output Iterator	Used to implement the Output Iterator requirement *i = t. [1]
`ostream_iterator& operator*()`	Output Iterator	Used to implement the Output Iterator requirement *i = t. [1]
`ostream_iterator& operator++()`	Output Iterator	Preincrement
`ostream_iterator& operator++(int)`	Output Iterator	Postincrement
`output_iterator_tag iterator_category(const ostream_iterator&)`	iterator tags	Returns the iterator's category.

New members

These members are not defined in the Output Iterator requirements, but are specific to ostream_iterator.

Function	Description
ostream_iterator(ostream& s)	Creates an ostream_iterator such that assignment of t through it is equivalent to s << t.
ostream_iterator(ostream& s, const char delim)*	Creates an ostream_iterator such that assignment of t through it is equivalent to s << t << delim.

Notes

[1] Note how assignment through an ostream_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the output operation. In this case, for the sake of simplicity, the proxy object is the ostream_iterator itself. That is, *i simply returns i , and *i = t is equivalent to i = t. You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

front_insert_iterator<FrontInsertionSequence>

Categories: iterators, adaptors

Component type: type

Description

Front_insert_iterator is an iterator adaptor that functions as an Output Iterator: assignment through a front_insert_iterator inserts an object before the first element of a Front Insertion Sequence. [1] [2]

Example

list<int> L;

L.push_front(3);

front_insert_iterator<list<int> > ii(L);

*ii++ = 0;

*ii++ = 1;

*ii++ = 2;

copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));

// The values that are printed are 2 1 0 3

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
`FrontInsertionSequence`	The type of Front Insertion Sequence into which values will be inserted.

Model of

Output Iterator. A front insert iterator's set of value types (as defined in the Output Iterator requirements) consists of a single type: FrontInsertionSequence::value_type.

Type requirements

The template parameter FrontInsertionSequence must be a Front Insertion Sequence.

Public base classes

None.

Members

Member	Where defined	Description
`front_insert_iterator(FrontInsertionSequence&)`	`front_insert_iterator`	See below.
`front_insert_iterator(const front_insert_iterator&)`	Trivial Iterator	The copy constructor
`front_insert_iterator& operator=(const front_insert_iterator&)`	Trivial Iterator	The assignment operator
`front_insert_iterator& operator*()`	Output Iterator	Used to implement the output iterator expression *i = x. [3]
`front_insert_iterator& operator=(const FrontInsertionSequence::value_type&)`	Output Iterator	Used to implement the output iterator expression *i = x. [3]
`front_insert_iterator& operator++()`	Output Iterator	Preincrement.
`front_insert_iterator& operator++(int)`	Output Iterator	Postincrement.
`output_iterator_tag iterator_category(const front_insert_iterator&) iterator tags`	Returns the iterator's category.	This is a global function, not a member.
`template<class FrontInsertionSequence> front_insert_iterator<FrontInsertionSequence> front_inserter(FrontInsertionSequence& S)`	`front_insert_iterator`	See below.

New members.

These members are not defined in the Output Iterator requirements, but are specific to front_insert_iterator.

Member	Description
`front_insert_iterator(FrontInsertionSequence& S)`	Constructs a front_insert_iterator that inserts objects before the first element of S.
`template<class FrontInsertionSequence> front_insert_iterator<FrontInsertionSequence> front_inserter(FrontInsertionSequence& S);`	Equivalent to front_insert_iterator<FrontInsertionSequence>(S). [4] This is a global function, not a member function.

Notes

[1] Note the difference between assignment through a FrontInsertionSequence::iterator and assignment through an front_insert_iterator<FrontInsertionSequence>. If i is a valid FrontInsertionSequence::iterator, then it points to some particular element in the front insertion sequence; the expression *i = t replaces that element with t, and does not change the total number of elements in the sequence. If ii is a valid front_insert_iterator<FrontInsertionSequence>, however, then the expression *ii = t is equivalent, for some FrontInsertionSequence seq, to the expression seq.push_front(t). That is, it does not overwrite any of seq's elements and it does change seq's size.

[2] Note the difference between a front_insert_iterator and an insert_iterator. It may seem that a front_insert_iterator is the same as an insert_iterator constructed with an insertion point that is the beginning of a sequence. In fact, though, there is a very important difference: every assignment through afront_insert_iterator corresponds to an insertion before the first element of the sequence. If you are inserting elements at the beginning of a sequence using an insert_iterator, then the elements will appear in the order in which they were inserted. If, however, you are inserting elements at the beginning of a sequence using a front_insert_iterator, then the elements will appear in the reverse of the order in which they were inserted.

[3] Note how assignment through an front_insert_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the insert operation. In this case, for the sake of simplicity, the proxy object is the front_insert_iterator itself. That is, *i simply returns i, and *i = t is equivalent to i = t. You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

[4] This function exists solely for the sake of convenience: since it is a non-member function, the template parameters may be inferred and the type of the front_insert_iterator need not be declared explicitly. One easy way to reverse a range and insert it at the beginning of a Front Insertion Sequence S, for example, is copy(first, last, front_inserter(S)).

back_insert_iterator<BackInsertionSequence>

Categories: iterators, adaptors

Component type: type

Description

Back_insert_iterator is an iterator adaptor that functions as an Output Iterator: assignment through a back_insert_iterator inserts an object after the last element of a Back Insertion Sequence. [1]

Example

list<int> L;

L.push_front(3);

back_insert_iterator<list<int> > ii(L);

*ii++ = 0;

*ii++ = 1;

*ii++ = 2;

copy (L.begin(), L.end(), ostream_iterator<int>(cout, " "));

// The values that are printed are 3 0 1 2

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
`BackInsertionSequence`	The type of Back Insertion Sequence into which values will be inserted.

Model of

Output Iterator. An insert iterator's set of value types (as defined in the Output Iterator requirements) consists of a single type: BackInsertionSequence::value_type.

Type requirements

The template parameter BackInsertionSequence must be a Back Insertion Sequence.

Public base classes

None.

Members

Member	Where defined	Description
`back_insert_iterator(BackInsertionSequence&)`	`back_insert_iterator`	See below.
`back_insert_iterator(const back_insert_iterator&)`	Trivial Iterator	The copy constructor
`back_insert_iterator& operator=(const back_insert_iterator&)`	Trivial Iterator	The assignment operator
`back_insert_iterator& operator*()`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`back_insert_iterator& operator=(const BackInsertionSequence::value_type&)`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`back_insert_iterator& operator++()`	Output Iterator	Preincrement.
`back_insert_iterator& operator++(int)`	Output Iterator	Postincrement.
`output_iterator_tag iterator_category(const back_insert_iterator&)`	iterator tags	Returns the iterator's category. This is a global function, not a member.
`template<class BackInsertionSequence> back_insert_iterator<BackInsertionSequence> back_inserter(BackInsertionSequence& S)`	`back_insert_iterator`	See below.

New members

These members are not defined in the Output Iterator requirements, but are specific to back_insert_iterator.

Member function	Description
`back_insert_iterator(BackInsertionSequence& S)`	Constructs a back_insert_iterator that inserts objects after the last element of S. (That is, it inserts objects just before S's past-the-end iterator.)
`template<class BackInsertionSequence> back_insert_iterator<BackInsertionSequence> back_inserter(BackInsertionSequence& S);`	Equivalent to back_insert_iterator<BackInsertionSequence>(S). [3] This is a global function, not a member function.

Notes

[1] Note the difference between assignment through a BackInsertionSequence::iterator and assignment through a back_insert_iterator<BackInsertionSequence>. If i is a valid BackInsertionSequence::iterator, then it points to some particular element in the back insertion sequence; the expression *i = t replaces that element with t, and does not change the total number of elements in the back insertion sequence. If ii is a valid back_insert_iterator<BackInsertionSequence>, however, then the expression *ii = t is equivalent, to the expression seq.push_back(t). That is, it does not overwrite any of seq's elements and it does change seq's size.

[2] Note how assignment through a back_insert_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the insert operation. In this case, for the sake of simplicity, the proxy object is the back_insert_iterator itself. That is, *i simply returns i, and *i = t is equivalent to i = t. You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

[3] This function exists solely for the sake of convenience: since it is a non-member function, the template parameters may be inferred and the type of the back_insert_iterator need not be declared explicitly. One easy way to reverse a range and insert it at the end of a Back Insertion Sequence S, for example, is reverse_copy(first, last, back_inserter(S)).

insert_iterator<Container>

Categories: iterators, adaptors

Component type: type

Description

Insert_iterator is an iterator adaptor that functions as an Output Iterator: assignment through an insert_iterator inserts an object into a Container. Specifically, if ii is an insert_iterator, then ii keeps track of a Container c and an insertion point p; the expression *ii = x performs the insertion c.insert(p, x). [1]

There are two different Container concepts that define this expression: Sequence, and Sorted Associative Container. Both concepts define insertion into a container by means of c.insert(p, x), but the semantics of this expression is very different in the two cases.

For a Sequence S, the expression S.insert(p, x) means to insert the value ximmediately before the iterator p. That is, the two-argument version of insert allows you to control the location at which the new element will be inserted. For a Sorted Associative Container, however, no such control is possible: the elements in a Sorted Associative Container always appear in ascending order of keys. Sorted Associative Containers define the two-argument version of insert as an optimization. The first argument is only a hint: it points to the location where the search will begin.

If you assign through an insert_iterator several times, then you will be inserting several elements into the underlying container. In the case of a Sequence, they will appear at a particular location in the underlying sequence, in the order in which they were inserted: one of the arguments to insert_iterator's constructor is an iterator p, and the new range will be inserted immediately before p.

In the case of a Sorted Associative Container, however, the iterator in the insert_iterator's constructor is almost irrelevant. The new elements will not necessarily form a contiguous range; they will appear in the appropriate location in the container, in ascending order by key. The order in which they are inserted only affects efficiency: inserting an already-sorted range into a Sorted Associative Container is an O(N) operation.

Example

Insert a range of elements into a list.

list <int> L;

L.push_front(3);

insert_iterator<list<int> > ii(L, L.begin());

*ii++ = 0;

*ii++ = 1;

*ii++ = 2;

copy(L.begin(), L.end(), ostream_iterator<int>(cout, " "));

// The values that are printed are 0 1 2 3.

Merge two sorted lists, inserting the resulting range into a set. Note that a set never contains duplicate elements.

int main() {

const int N = 6;

int A1[N] = {1, 3, 5, 7, 9, 11};

int A2[N] = {1, 2, 3, 4, 5, 6};

set<int> result;

merge (A1, A1 + N, A2, A2 + N,

inserter(result, result.begin()));

copy(result.begin(), result.end(), ostream_iterator<int>(cout, " "));

cout << endl;

// The output is "1 2 3 4 5 6 7 9 11".

}

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
`Container`	The type of Container into which values will be inserted.

Model of

Output Iterator. An insert iterator's set of value types (as defined in the Output Iterator requirements) consists of a single type: Container::value_type.

Type requirements

• The template parameter Container is a model of Container.

• Container is variable-sized, as described in the Container requirements.

• Container has a two-argument insert member function. Specifically, if c is an object of type Container, p is an object of type Container::iterator and v is an object of type Container::value_type, then c.insert(p, v) must be a valid expression.

Public base classes

None.

Members

Member	Where defined	Description
`insert_iterator(Container&, Container::iterator)`	`insert_iterator`	See below.
`insert_iterator(const insert_iterator&)`	Trivial Iterator	The copy constructor
`insert_iterator& operator=(const insert_iterator&)`	Trivial Iterator	The assignment operator
`insert_iterator& operator*()`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`insert_iterator& operator=(const Container::value_type&)`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`insert_iterator& operator++()`	Output Iterator	Preincrement.
`insert_iterator& operator++(int)`	Output Iterator	Postincrement.
`output_iterator_tag iterator_category(const insert_iterator&)`	iterator tags	Returns the iterator's category. This is a global function, not a member.
`template<class Container, class Iter) insert_iterator<Container> inserter(Container& C, Iter i);`	`insert_iterator`	See below.

New members

These members are not defined in the Output Iterator requirements, but are specific to insert_iterator.

Member	Description
`insert_iterator(Container& C, Container::iterator i)`	Constructs an insert_iterator that inserts objects in C. If Container is a Sequence, then each object will be inserted immediately before the element pointed to by i. If C is a Sorted Associative Container, then the first insertion will use i as a hint for beginning the search. The iterator i must be a dereferenceable or past-the-end iterator in C.
`template<class Container, class Iter) insert_iterator<Container> inserter(Container& C, Iter i);`	Equivalent to insert_iterator<Container>(C, i). [2] This is a global function, not a member function.

Notes

[1] Note the difference between assignment through a Container::iterator and assignment through an insert_iterator<Container>. If i is a valid Sequence::iterator, then it points to some particular element in the container; the expression *i = t replaces that element with t, and does not change the total number of elements in the container. If ii is a valid insert_iterator<container>, however, then the expression *ii = t is equivalent, for some container c and some valid container::iterator j, to the expression c.insert(j, t). That is, it does not overwrite any of c's elements and it does change c's size.

[2] Note how assignment through an insert_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the insert operation. In this case, for the sake of simplicity, the proxy object is the insert_iterator itself. That is, *i simply returns i, and *i = t is equivalent to i = t. You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

[3] This function exists solely for the sake of convenience: since it is a non-member function, the template parameters may be inferred and the type of the insert_iterator need not be declared explicitly. One easy way to reverse a range and insert it into a Sequence S, for example, is reverse_copy(first, last, inserter(S, S.begin())).

reverse_iterator<RandomAccessIterator, T, Reference, Distance>

Categories: iterators, adaptors

Component type: type

Description

Reverse_iterator is an iterator adaptor that enables backwards traversal of a range. Operator++ applied to an object of class reverse_iterator<RandomAccessIterator> means the same thing as operator-- applied to an object of class RandomAccessIterator. There are two different reverse iterator adaptors: the class reverse_iterator has a template argument that is a Random Access Iterator, and the class reverse_bidirectional_iterator has a template argument that is a Bidirectional Iterator. [1]

Example

template <class T>

void forw(const vector<T>& V) {

vector<T>::iterator first = V.begin();

vector<T>::iterator last = V.end();

while (first != last) cout << *first++ << endl;

}

template <class T>

void rev(const vector<T>& V) {

typedef reverse_iterator<vector<T>::iterator, T, vector<T>::reference_type, vector<T>::difference_type> reverse_iterator; [2]

reverse_iterator rfirst(V.end());

reverse_iterator rlast(V.begin());

while (rfirst != rlast) cout << *rfirst++ << endl;

}

In the function forw, the elements are printed in the order *first, *(first+1) , …, *(last-1). In the function rev, they are printed in the order *(last – 1), *(last - 2), …, *first. [3]

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description	Default
`RandomAccessIterator`	The base iterator class. Incrementing an object of class reverse_iterator<Iterator> corresponds to decrementing an object of class Iterator.
`T`	The reverse iterator's value type. This should always be the same as the base iterator's value type.
`Reference`	The reverse iterator's reference type. This should always be the same as the base iterator's reference type.	`T&`
`Distance`	The reverse iterator's distance type. This should always be the same as the base iterator's distance type.	`ptrdiff_t`

Model of

Random Access Iterator

Type requirements

The base iterator type (that is, the template parameter RandomAccessIterator) must be a Random Access Iterator. The reverse_iterator's value type, reference type, and distance type (that is, the template parameters T, Reference, and Distance, respectively) must be the same as the base iterator's value type, reference type, and distance type.

Public base classes

None.

Members

Member	Where defined	Description
`self`	`reverse_iterator`	See below
`reverse_iterator()`	Trivial Iterator	The default constructor
`reverse_iterator(const reverse_iterator& x)`	Trivial Iterator	The copy constructor
`reverse_iterator& operator=(const reverse_iterator& x)`	Trivial Iterator	The assignment operator
`reverse_iterator(RandomAccessIterator x)`	`reverse_iterator`	See below.
`RandomAccessIterator base()`	`reverse_iterator`	See below.
`Reference operator*() const`	Trivial Iterator	The dereference operator
`reverse_iterator& operator++()`	Forward Iterator	Preincrement
`reverse_iterator operator++(int)`	Forward Iterator	Postincrement
`reverse_iterator& operator--()`	Bidirectional Iterator	Predecrement
`reverse_iterator operator--(int)`	Bidirectional Iterator	Postdecrement
`reverse_iterator operator+(Distance)`	Random Access Iterator	Iterator addition
`reverse_iterator& operator+=(Distance)`	Random Access Iterator	Iterator addition
`reverse_iterator operator-(Distance)`	Random Access Iterator	Iterator subtraction
`reverse_iterator& operator-=(Distance)`	Random Access Iterator	Iterator subtraction
`Reference operator[](Distance)`	Random Access Iterator	Random access to an element.
`reverse_iterator operator+(Distance, reverse_iterator)`	Random Access Iterator	Iterator addition. This is a global function, not a member function.
`Distance operator-(const reverse_iterator&, const reverse_iterator&)`	Random Access Iterator	Finds the distance between two iterators. This is a global function, not a member function.
`bool operator==(const reverse_iterator&, const reverse_iterator&)`	Trivial Iterator	Compares two iterators for equality. This is a global function, not a member function.
`bool operator<(const reverse_iterator&, const reverse_iterator&)`	Random Access Iterator	Determines whether the first argument precedes the second. This is a global function, not a member function.
`random_access_iterator_tag iterator_category(const reverse_iterator&)`	Iterator tags	Returns the iterator's category. This is a global function, not a member function.
`T* value_type(const reverse_iterator&)`	Iterator tags	Returns the iterator's value type. This is a global function, not a member function.
`Distance* distance_type(const reverse_iterator&)`	Iterator tags	Returns the iterator's distance type. This is a global function, not a member function.

New members

These members are not defined in the Random Access Iterator requirements, but are specific to reverse_iterator.

Member	Description
`self`	A typedef for reverse_iterator<RandomAccessIterator, T, Reference, Distance>.
`RandomAccessIterator base()`	Returns the current value of the reverse_iterator's base iterator. If ri is a reverse iterator and i is any iterator, the two fundamental identities of reverse iterators can be written as reverse_iterator(i).base() == i and &ri == &(ri.base() – 1).
`reverse_iterator(RandomAccessIterator i)`	Constructs a reverse_iterator whose base iterator is i.

Notes

[1] There isn't really any good reason to have two separate classes: this separation is purely because of a technical limitation in some of today's C++ compilers. If the two classes were combined into one, then there would be no way to declare the return types of the iterator tag functions iterator_category, distance_type and value_type correctly. The iterator traits class solves this problem: it addresses the same issues as the iterator tag functions, but in a cleaner and more flexible manner. Iterator traits, however, rely on partial specialization, and many C++ compilers do not yet implement partial specialization. Once compilers that support partial specialization become more common, these two different reverse iterator classes will be combined into a single class.

[2] The declarations for rfirst and rlast are written in this clumsy form simply as an illustration of how to declare a reverse_iterator. Vector is a Reversible Container, so it provides a typedef for the appropriate instantiation of reverse_iterator. The usual way of declaring these variables is much simpler:

vector<T>::reverse_iterator rfirst = rbegin();

vector<T>::reverse_iterator rlast = rend();

[3] Note the implications of this remark. The variable rfirst is initialized as reverse_iterator<…> rfirst(V.end());. The value obtained when it is dereferenced, however, is *(V.end() – 1). This is a general property: the fundamental identity of reverse iterators is &*(reverse_iterator(i)) == &*(i – 1). This code sample shows why this identity is important: if [f, l) is a valid range, then it allows [reverse_iterator(l), reverse_iterator(f)) to be a valid range as well. Note that the iterator l is not part of the range, but it is required to be dereferenceable or past-the-end. There is no requirement that any such iterator precedes f.

reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Distance>

Categories: iterators, adaptors

Component type: type

Description

Reverse_bidirectional_iterator is an iterator adaptor that enables backwards traversal of a range. Operator++ applied to an object of class reverse_bidirectional_iterator<BidirectionalIterator> means the same thing as operator-- applied to an object of class BidirectionalIterator. There are two different reverse iterator adaptors: the class reverse_bidirectional_iterator has a template argument that is a Bidirectional Iterator, and the class reverse_iterator has a template argument that is a Random Access Iterator. [1]

Example

template <class T>

void forw(const list <T>& L) {

list<T>::iterator first = L.begin();

list<T>::iterator last = L.end();

while (first != last) cout << *first++ << endl;

}

template <class T>

void rev(const list <T>& L) {

typedef reverse_bidirectional_iterator<list<T>::iterator, T, list<T>::reference_type, list<T>::difference_type> reverse_iterator; [2]

reverse_iterator rfirst(L.end());

reverse_iterator rlast(L.begin());

while (rfirst != rlast) cout << *rfirst++ << endl;

}

In the function forw, the elements are printed in the order *first, *(first+1) , …, *(last-1). In the function rev, they are printed in the order *(last – 1), *(last - 2), …, *first. [3]

Definition

Defined in the standard header iterator, and in the nonstandard backward-compatibility header iterator.h. This class is no longer part of the C++ standard, but it was present in early drafts, and it is retained in this implementation for backward compatibility.

Template parameters

Parameter	Description	Default
`BidirectionalIterator`	The base iterator class. Incrementing an object of class reverse_bidirectional_iterator<BidirectionalIterator> corresponds to decrementing an object of class BidirectionalIterator.
`T`	The reverse iterator's value type. This should always be the same as the base iterator's value type.
`Reference`	The reverse iterator's reference type. This should always be the same as the base iterator's reference type.	`T&`
`Distance`	The reverse iterator's distance type. This should always be the same as the base iterator's distance type.	`ptrdiff_t`

Model of

Bidirectional Iterator.

Type requirements

The base iterator type (that is, the template parameter BidirectionalIterator) must be a Bidirectional Iterator. The reverse_bidirectional_iterator's value type, reference type, and distance type (that is, the template parameters T, Reference, and Distance, respectively) must be the same as the base iterator's value type, reference type, and distance type.

Public base classes

None.

Members

Member	Where defined	Description
`self`	`reverse_bidirectional_iterator`	See below
`reverse_bidirectional_iterator()`	Trivial Iterator	The default constructor
`reverse_bidirectional_iterator(const reverse_bidirectional_iterator& x)`	Trivial Iterator	The copy constructor
`reverse_bidirectional_iterator& operator=(const reverse_bidirectional_iterator& x)`	Trivial Iterator	The assignment operator
`reverse_bidirectional_iterator(BidirectionalIterator x)`	`reverse_bidirectional_iterator`	See below.
`BidirectionalIterator base()`	reverse_bidirectional_iterator	See below.
`Reference operator*() const`	Trivial Iterator	The dereference operator
`reverse_bidirectional_iterator& operator++()`	Forward Iterator	Preincrement
`reverse_bidirectional_iterator operator++(int)`	Forward Iterator	Postincrement
`reverse_bidirectional_iterator& operator--()`	Bidirectional Iterator	Predecrement
`reverse_bidirectional_iterator operator--(int)`	Bidirectional Iterator	Postdecrement
`bool operator==(const reverse_bidirectional_iterator&, const reverse_bidirectional_iterator&)`	Trivial Iterator	Compares two iterators for equality. This is a global function, not a member function.
`bidirectional_iterator_tag iterator_category(const reverse_bidirectional_iterator&)`	Iterator tags	Returns the iterator's category. This is a global function, not a member function.
`T* value_type(const reverse_bidirectional_iterator&)`	Iterator tags	Returns the iterator's value type. This is a global function, not a member function.
`Distance* distance_type(const reverse_bidirectional_iterator&)`	Iterator tags	Returns the iterator's distance type. This is a global function, not a member function.

New members

These members are not defined in the Bidirectional Iterator requirements, but are specific to reverse_bidirectional_iterator.

Member	Description
`self`	A typedef for reverse_bidirectional_iterator<BidirectionalIterator, T, Reference, Distance>.
`BidirectionalIterator base()`	Returns the current value of the reverse_bidirectional_iterator's base iterator. If ri is a reverse iterator and i is any iterator, the two fundamental identities of reverse iterators can be written as reverse_bidirectional_iterator(i).base() == i and &ri == &(ri.base() – 1).
`reverse_bidirectional_iterator(BidirectionalIterator i)`	Constructs a reverse_bidirectional_iterator whose base iterator is i.

Notes

[2] The declarations for rfirst and rlast are written in this clumsy form simply as an illustration of how to declare a reverse_bidirectional_iterator. List is a Reversible Container, so it provides a typedef for the appropriate instantiation of reverse_bidirectional_iterator. The usual way of declaring these variables is much simpler:

list<T>::reverse_bidirectional_iterator rfirst = rbegin();

list<T>::reverse_bidirectional_iterator rlast = rend();

[3] Note the implications of this remark. The variable rfirst is initialized as reverse_bidirectional_iterator<…> rfirst(V.end());. The value obtained when it is dereferenced, however, is *(V.end() – 1). This is a general property: the fundamental identity of reverse iterators is &*(reverse_bidirectional_iterator(i)) == &*(i – 1). This code sample shows why this identity is important: if [f, l) is a valid range, then it allows [reverse_bidirectional_iterator(l), reverse_bidirectional_iterator(f)) to be a valid range as well. Note that the iterator l is not part of the range, but it is required to be dereferenceable or past-the-end. There is no requirement that any such iterator precedes f.

raw_storage_iterator<ForwardIterator, T>

Categories: allocators, iterators, adaptors

Component type: type

Description

In C++, the operator new allocates memory for an object and then creates an object at that location by calling a constructor. Occasionally, however, it is useful to separate those two operations. [1] If i is an iterator that points to a region of uninitialized memory, then you can use construct to create an object in the location pointed to by i. Raw_storage_iterator is an adaptor that makes this procedure more convenient. If r is a raw_storage_iterator, then it has some underlying iterator i. The expression *r = x is equivalent to construct(&*i, x).

Example

class Int {

public:

Int(int x) : val(x) {}

int get() { return val; }

private:

int val;

};

int main() {

int A1[] = {1, 2, 3, 4, 5, 6, 7};

const int N = sizeof(A1) / sizeof(int);

Int* A2 = (Int*)malloc(N * sizeof(Int));

transform(A1, A1 + N, raw_storage_iterator<Int*, int>(A2), negate<int>());

}

Definition

Defined in the standard header memory, and in the nonstandard backward-compatibility header iterator.h.

Template parameters

Parameter	Description
OutputIterator	The type of the raw_storage_iterator's underlying iterator.
`T`	The type that will be used as the argument to the constructor.

Model of

Output Iterator

Type requirements

• ForwardIterator is a model of Forward Iterator

• ForwardIterator's value type has a constructor that takes a single argument of type T.

Public base classes

None.

Members

Member	Where defined	Description
`raw_storage_iterator(ForwardIterator x)`	`raw_storage_iterator`	See below.
`raw_storage_iterator(const raw_storage_iterator&)`	trivial iterator	The copy constructor
`raw_storage_iterator& operator=(const raw_storage_iterator&)`	trivial iterator	The assignment operator
`raw_storage_iterator& operator*()`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`raw_storage_iterator& operator=(const Sequence::value_type&)`	Output Iterator	Used to implement the output iterator expression *i = x. [2]
`raw_storage_iterator& operator++()`	Output Iterator	Preincrement.
`raw_storage_iterator& operator++(int)`	Output Iterator	Postincrement.
`output_iterator_tag iterator_category(const raw_storage_iterator&)`	iterator tags	Returns the iterator's category. This is a global function, not a member.

New members

These members are not defined in the Output Iterator requirements, but are specific to raw_storage_iterator.

Function	Description
`raw_storage_iterator(ForwardIterator i)`	Creates a raw_storage_iterator whose underlying iterator is i.
`raw_storage_iterator& operator=(const T& val)`	Constructs an object of ForwardIterator's value type at the location pointed to by the iterator, using val as the constructor's argument.

Notes

[1] In particular, this sort of low-level memory management is used in the implementation of some container classes.

[2] Note how assignment through a raw_storage_iterator is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the insert operation. In this case, for the sake of simplicity, the proxy object is the raw_storage_iterator itself. That is, *i returns i, and *i = t is equivalent to i = t . You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

sequence_buffer<Container, buf_sz>

Categories: iterators, adaptors

Component type: type

Description

Sequence_buffer is similar to back_insert_iterator: it is an output iterator adaptor that appends elements to the end of a container.

The main difference between sequence_buffer and back_insert_iterator is that back_insert_iterator inserts elements into a sequence one element at a time; sequence_buffer, however, as the "buffer" part of the name suggests, accumulates elements into a buffer and appends the entire buffer in a single operation.

Specifically, the expression *it = v adds v to the end of it's internal buffer. The buffer is automatically flushed when it gets full, or when it is destroyed; flushing the buffer means emptying it and appending its contents to it 's underlying container. (It is also possible to flush the buffer manually, by invoking the flush() member function.)

This difference has two implications. First, sequence_buffer is only useful if appending an array of N elements is much more efficient than inserting a single element N times. Second, sequence_buffer assumes that it can insert elements at the end of a container using an append member function. This member function is not part of the Container or Sequence requirements. The sequence_buffer adaptor can be used with rope, but not with any of the other containers in the library. (This is the reason why sequence_buffer is defined in the file rope.h, instead of in iterator.h.)

If you want to build up a string one character at a time, it is much more efficient to use sequence_buffer than to repeatedly add single characters to the end of a rope.

Example

int main() {

const char* const s = "this is a test";

const int N = strlen(s);

crope r;

transform(s, s + N, sequence_buffer<crope>(r), toupper);

cout << "r = " << r << endl;

}

Definition

Defined in the header rope, and in the backward-compatibility header rope.h. The sequence_buffer class, and the rope header, are SGI extensions; they are not part of the C++ standard.

Template parameters

Parameter	Description	Default
`Container`	The type of the underlying container that elements are being written to. [1]
`buf_sz`	Number of elements in the buffer. This is a number, not a type. buf_sz has type size_t.	100

Model of

Output Iterator.

Type requirements

• Container is a variable-sized Forward Container

• Container 's value type T is a model of Default Constructible, as well as Assignable.

• Container has a member function that appends a range. Specifically: If x is an object of type Container and f and l are of type T*, then x.append(f, l) appends the range [f, l) to x. [1]

Public base classes

output_iterator

Members

Member	Where defined	Description
`value_type`	`sequence_buffer`	The underlying container's value type.
`sequence_buffer(Container& C)`	`sequence_buffer`	Create a sequence_buffer whose underlying container is C.
`sequence_buffer()`	Default Constructible	The default constructor. The resulting iterator is singular.
`sequence_buffer(const sequence_buffer&)`	Assignable	Copy constructor.
`sequence_buffer& operator=(const sequence_buffer& s)`	Assignable	Assignment operator.
`sequence_buffer& operator=(sequence_buffer& s)`	Assignable	Faster version of assignment operator.
`sequence_buffer& operator=(const value_type&)`	Output Iterator	Used to implement the Output Iterator requirement *i = t. [2]
`sequence_buffer& operator*()`	Output Iterator	Used to implement the Output Iterator requirement *i = t. [2]
`sequence_buffer& operator++()`	Output Iterator	Preincrement
`sequence_buffer& operator++(int)`	Output Iterator	Postincrement
`void flush()`	`sequence_buffer`	Flush the buffer.
`void push_back(value_type)`	`sequence_buffer`	i.push_back(x) is equivalent to *i = x.
`void append(value_type* s, size_t len)`	`sequence_buffer`	Append multiple values.

New members

These members are not defined in the Output Iterator requirements, but are specific to sequence_buffer.

Function	Description
`value_type`	The underlying container's value type. That is, typename Container::value_type.
`sequence_buffer(Container& C)`	Create a sequence_buffer whose underlying container is C. Elements appended to the sequence_buffer will be appended to C whenever the sequence_buffer is flushed.
`void flush()`	Append all elements in the buffer to the underlying container, and empty the buffer. That is, make the underlying container consistent with the sequence_buffer. Note that flush is called automatically whenever the buffer is full, and also by sequence_buffer's destructor. Sometimes, however, it is useful to be sure that the buffer is flushed at a particular time.
`void push_back(value_type x)`	Append x to the sequence_buffer. Note that this member function is strictly unnecessary: i.push_back(x) is just alternate syntax for *i = x.
`void append(value_type* s, size_t len)`	Append the range [s, s + len) to the sequence_buffer. Note that i.append(s, n) is just the same as copy(s, s + n, i). The append member function, however, is faster.

Notes

[1] Despite the name "sequence_buffer", this adaptor cannot actually be used with arbitrary sequences: it requires that the template argument Container have an append member function that can insert multiple elements at the end of the container. This member function is not part of the Sequence requirements. This means that sequence_buffer can be used with rope, but not with any of the other predefined container classes.

[2] Note how assignment through a sequence_buffer is implemented. In general, unary operator* must be defined so that it returns a proxy object, where the proxy object defines operator= to perform the output operation. In this case, for the sake of simplicity, the proxy object is the sequence_buffer itself. That is, *i simply returns i, and *i = t is equivalent to i = t. You should not, however, rely on this behavior. It is an implementation detail, and it is not guaranteed to remain the same in future versions.

Standard Template Library Programmers Guide - читать онлайн бесплатно полную версию книги . Страница 4

Iterators

Introduction

Summary

Description

Concepts

Types

Functions

Notes

Concepts

Trivial Iterator

Description

Refinement of

Associated types

Notation

Definitions

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Notes

See also

Input Iterator

Description

Refinement of

Associated types

Notation

Definitions

Valid expressions

Expression semantics

Complexity guarantees

Models

Notes

See also

Output Iterator

Description

Refinement of

Associated types

Notation

Definitions

Valid expressions

Expression semantics

Complexity guarantees

Models

See also

Forward Iterator

Description

Refinement of

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Models

See also

Bidirectional Iterator

Description

Refinement of

Associated types

Notation

Valid expressions

Expression Semantics

Complexity guarantees

Invariants

Models

See also

Random Access Iterator

Description

Refinement of

Associated types

Notation

Valid expressions

Expression semantics

Complexity guarantees

Invariants

Models

Notes

See also

Iterator Tags