1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
|
In addition to the conceptual iterator types presented in this section the STL
defines several adapters hi(adapter: object to iterator) allowing objects to
be passed as iterators. These adapters are presented in the upcoming
sections. Before those adapters can be used the tthi(iterator) header file
must be included.
The standard iterator hi(iterator (std::) - deprecated) (tt(std::iterator)) is
now
deprecated+footnote(http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0174r1.html#2.1),
and the compiler issues a corresponding warning. Consequently,
tt(std::iterator) should no longer be used when designing your own iterators
(section ref(ITERATORCONS) describes how to design your own).
Iterators are objects acting like pointers. Iterators have the following
general hi(iterator) characteristics:
itemization(
it() Two iterators may be compared for (in)equality using the tt(==) and
tt(!=) operators. The em(ordering) operators (e.g., tt(>), tt(<))
can usually not be used.
it() Given an iterator tt(iter), tt(*iter) represents the object the
iterator points to (alternatively, tt(iter->) can be used to reach the members
of the object the iterator points to).
it() Given an iterator tt(iter), hi(base)tt(iter.base()) returns the
address of tt(*iter). It returns the same type as tt(&*iter). E.g.,
verb( vector<int> vi{ 1, 2, 3 };
int *ip = vi.begin().base();
cout << *ip << '\n'; // shows: 1)
it() tt(++iter) or tt(iter++) advances the iterator to the next
element. The notion of advancing an iterator to the next element is
consequently applied: several containers support emi(reverse_iterator) types,
in which the tt(++iter) operation actually reaches a previous element in a
sequence.
it() em(Pointer arithmetic) may be used with iterators of containers
storing their elements consecutively in memory like ti(vector) and
ti(deque). For such containers tt(iter + 2) points to the second element
beyond the one to which tt(iter) points. See also section ref(DISTANCE),
covering hi(distance)tt(std::distance).
it() Merely defining an iterator is comparable to having a
0-pointer. Example:
verb(#include <vector>
#include <iostream>
using namespace std;
int main()
{
vector<int>::iterator vi;
cout << &*vi; // prints 0
})
)
STL containers usually define members offering iterators (i.e., they
define their own type ti(iterator)). These members are commonly called
ti(begin) and ti(end) and (for reversed iterators (type tt(reverse_iterator)))
ti(rbegin) and ti(rend).
hi(iterators: forward <-> reverse)
Whereas reverse iterators can be constructed from ordinary (forward)
iterators using tt(reverse_iterator) constructors as in:
verb( string str;
auto revit = string::reverse_iterator{ str.begin() };)
the opposite is not accomplished that way. To retrieve the forward
iterator corresponding to a reverse iterator, the ti(reverse_iterator.base())
hi(base)hi(base(): reverse_terator)
member can be used. E.g., to obtain the forward iterator corresponding to
tt(revit) use
verb( auto forward { revit.base() };)
Standard practice requires hi(iterator: range) iterator ranges to be
em(left inclusive). The notation rangeti(left, right) indicates that tt(left)
is an iterator pointing to the first element, while tt(right) is an iterator
pointing just em(beyond) the last element. The iterator range is em(empty)
when tt(left == right).
The following example shows how all elements of a vector of strings can be
inserted into tt(cout) using its iterator ranges rangett(begin(), end()), and
rangett(rbegin(), rend()). Note that the tt(for-loops) for both ranges are
identical. Furthermore it nicely illustrates how the tt(auto) keyword can be
used to define the type of the loop control variable instead of using a much
more verbose variable definition like tt(vector<string>::iterator) (see also
section ref(AUTO)):
verbinclude(-a examples/iterator.cc)
Furthermore, the STL defines
hi(iterator: to const elements)emi(const_iterator) types that must be used
when visiting a series of elements in a constant container. Whereas the
elements of the vector in the previous example could have been altered, the
elements of the vector in the next example are immutable, and
tt(const_iterator)s are required:
verbinclude(-a examples/constiterator.cc)
The examples also illustrate that plain
hi(pointer as iterator) pointers can be used as iterators. The
initialization tt(vector<string> args(argv, argv + argc)) provides the
tt(args) vector with a pair of pointer-based iterators: tt(argv) points to the
first element to initialize tt(args) with, tt(argv + argc) points just beyond
the last element to be used, tt(++argv) reaches the next command line
argument. This is a general pointer characteristic, which is why they too can
be used in situations where tt(iterators) are expected.
The STL defines six types hi(iterator: types) of iterators. These
iterator types are expected by generic algorithms, and in order to create a
particular type of iterator yourself it is important to know their
characteristics. In general, iterators hi(iterator: requirements) (see also
section ref(ITERATORCONS)) must define:
itemization(
iti(operator==), testing two iterators for equality,
iti(operator!=), testing two iterators for inequality,
iti(operator++), incrementing the iterator, as prefix operator,
iti(operator*), to access the element the iterator refers to,
)
The following types of iterators are used when describing generic
algorithms in chapter ref(GENERIC):
itemization(
it() bi(InputIterator)bf(s):
quote(InputIterators are used to read from a container. The
dereference operator is guaranteed to work as ti(rvalue) in
expressions. Instead of an InputIterator it is also possible to use (see
below) Forward-, Bidirectional- or RandomAccessIterators. Notations like
tt(InputIterator1) and tt(InputIterator2) may be used as well. In these cases,
numbers are used to indicate which iterators `belong together'. E.g., the
generic algorithm link(tt(inner_product))(INNERPROD) has the following
prototype:
verb(Type inner_product(InputIterator1 first1, InputIterator1 last1,
InputIterator2 first2, Type init);)
tt(InputIterator1 first1) and tt(InputIterator1 last1) define a pair of
input iterators on one range, while tt(InputIterator2 first2) defines the
beginning of another range. Analogous notations may be used with other
iterator types.)
it() bi(OutputIterator)bf(s):
quote(OutputIterators can be used to write to a container. The
dereference operator is guaranteed to work as an ti(lvalue) in expressions,
but not necessarily as tt(rvalue). Instead of an OutputIterator it is also
possible to use (see below) Forward-, Bidirectional- or
RandomAccessIterators.)
it() bi(ForwardIterator)bf(s):
quote(ForwardIterators combine InputIterators and
OutputIterators. They can be used to traverse containers in one direction,
for reading and/or writing. Instead of a ForwardIterator it is also possible
to use (see below) Bidirectional- or RandomAccessIterators.)
it() bi(BidirectionalIterator)bf(s):
quote(BidirectionalIterators can be used to traverse containers in
both directions, for reading and writing. Instead of a BidirectionalIterator
it is also possible to use (see below) a RandomAccessIterator.)
it() bi(RandomAccessIterator)bf(s):
quote(RandomAccessIterators provide i(random access) to container
elements. An algorithm like link(tt(sort))(SORT) requires a
RandomAccessIterator, and can therefore em(not) be used to sort the elements
of lists or maps, which only provide BidirectionalIterators.)
it() bi(ContiguousIterator)bf(s):
quote(ContiguousIterators are like random access iterators, but in
addition guarantee that the elements these iterators point to are stored
contiguously in memory. A container like tt(std::vector) offers contiguous
iterators.)
)
The example given with the RandomAccessIterator illustrates how to relate
iterators and generic algorithms: look for the iterator that's required by the
(generic) algorithm, and then see whether the datastructure supports the
required type of iterator. If not, the algorithm cannot be used with the
particular datastructure.
|
