|
|
|
|
"http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
|
"http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
|
[ ]>
|
[ ]>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ISO C++
|
ISO C++
|
|
|
|
|
library
|
library
|
|
|
|
|
|
|
|
|
</code></pre></td>
<td class="diff"><pre><code><title></code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code> Iterators</code></pre></td>
<td class="diff"><pre><code> Iterators</code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code> <indexterm><primary>Iterators</primary></indexterm></code></pre></td>
<td class="diff"><pre><code> <indexterm><primary>Iterators</primary></indexterm></code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code>
|
|
|
|
|
|
|
|
Predefined
|
Predefined
|
|
|
|
|
Iterators vs. Pointers
|
Iterators vs. Pointers
|
|
|
The following
|
The following
|
FAQ entry points out that
|
FAQ entry points out that
|
iterators are not implemented as pointers. They are a generalization
|
iterators are not implemented as pointers. They are a generalization
|
of pointers, but they are implemented in libstdc++ as separate
|
of pointers, but they are implemented in libstdc++ as separate
|
classes.
|
classes.
|
|
|
|
|
Keeping that simple fact in mind as you design your code will
|
Keeping that simple fact in mind as you design your code will
|
prevent a whole lot of difficult-to-understand bugs.
|
prevent a whole lot of difficult-to-understand bugs.
|
|
|
|
|
You can think of it the other way 'round, even. Since iterators
|
You can think of it the other way 'round, even. Since iterators
|
are a generalization, that means
|
are a generalization, that means
|
that pointers are
|
that pointers are
|
iterators, and that pointers can be used
|
iterators, and that pointers can be used
|
whenever an iterator would be. All those functions in the
|
whenever an iterator would be. All those functions in the
|
Algorithms sect1 of the Standard will work just as well on plain
|
Algorithms sect1 of the Standard will work just as well on plain
|
arrays and their pointers.
|
arrays and their pointers.
|
|
|
|
|
That doesn't mean that when you pass in a pointer, it gets
|
That doesn't mean that when you pass in a pointer, it gets
|
wrapped into some special delegating iterator-to-pointer class
|
wrapped into some special delegating iterator-to-pointer class
|
with a layer of overhead. (If you think that's the case
|
with a layer of overhead. (If you think that's the case
|
anywhere, you don't understand templates to begin with...) Oh,
|
anywhere, you don't understand templates to begin with...) Oh,
|
no; if you pass in a pointer, then the compiler will instantiate
|
no; if you pass in a pointer, then the compiler will instantiate
|
that template using T* as a type, and good old high-speed
|
that template using T* as a type, and good old high-speed
|
pointer arithmetic as its operations, so the resulting code will
|
pointer arithmetic as its operations, so the resulting code will
|
be doing exactly the same things as it would be doing if you had
|
be doing exactly the same things as it would be doing if you had
|
hand-coded it yourself (for the 273rd time).
|
hand-coded it yourself (for the 273rd time).
|
|
|
|
|
How much overhead is there when using an
|
How much overhead is there when using an
|
iterator class? Very little. Most of the layering classes
|
iterator class? Very little. Most of the layering classes
|
contain nothing but typedefs, and typedefs are
|
contain nothing but typedefs, and typedefs are
|
"meta-information" that simply tell the compiler some
|
"meta-information" that simply tell the compiler some
|
nicknames; they don't create code. That information gets passed
|
nicknames; they don't create code. That information gets passed
|
down through inheritance, so while the compiler has to do work
|
down through inheritance, so while the compiler has to do work
|
looking up all the names, your runtime code does not. (This has
|
looking up all the names, your runtime code does not. (This has
|
been a prime concern from the beginning.)
|
been a prime concern from the beginning.)
|
|
|
|
|
|
|
|
|
|
|
|
|
One Past the End
|
One Past the End
|
|
|
This starts off sounding complicated, but is actually very easy,
|
This starts off sounding complicated, but is actually very easy,
|
especially towards the end. Trust me.
|
especially towards the end. Trust me.
|
|
|
Beginners usually have a little trouble understand the whole
|
Beginners usually have a little trouble understand the whole
|
'past-the-end' thing, until they remember their early algebra classes
|
'past-the-end' thing, until they remember their early algebra classes
|
(see, they told you that stuff would come in handy!) and
|
(see, they told you that stuff would come in handy!) and
|
the concept of half-open ranges.
|
the concept of half-open ranges.
|
|
|
First, some history, and a reminder of some of the funkier rules in
|
First, some history, and a reminder of some of the funkier rules in
|
C and C++ for builtin arrays. The following rules have always been
|
C and C++ for builtin arrays. The following rules have always been
|
true for both languages:
|
true for both languages:
|
|
|
|
|
|
|
You can point anywhere in the array, or to the first element
|
You can point anywhere in the array, or to the first element
|
past the end of the array. A pointer that points to one
|
past the end of the array. A pointer that points to one
|
past the end of the array is guaranteed to be as unique as a
|
past the end of the array is guaranteed to be as unique as a
|
pointer to somewhere inside the array, so that you can compare
|
pointer to somewhere inside the array, so that you can compare
|
such pointers safely.
|
such pointers safely.
|
|
|
|
|
|
|
You can only dereference a pointer that points into an array.
|
You can only dereference a pointer that points into an array.
|
If your array pointer points outside the array -- even to just
|
If your array pointer points outside the array -- even to just
|
one past the end -- and you dereference it, Bad Things happen.
|
one past the end -- and you dereference it, Bad Things happen.
|
|
|
|
|
|
|
Strictly speaking, simply pointing anywhere else invokes
|
Strictly speaking, simply pointing anywhere else invokes
|
undefined behavior. Most programs won't puke until such a
|
undefined behavior. Most programs won't puke until such a
|
pointer is actually dereferenced, but the standards leave that
|
pointer is actually dereferenced, but the standards leave that
|
up to the platform.
|
up to the platform.
|
|
|
|
|
|
|
The reason this past-the-end addressing was allowed is to make it
|
The reason this past-the-end addressing was allowed is to make it
|
easy to write a loop to go over an entire array, e.g.,
|
easy to write a loop to go over an entire array, e.g.,
|
while (*d++ = *s++);.
|
while (*d++ = *s++);.
|
|
|
So, when you think of two pointers delimiting an array, don't think
|
So, when you think of two pointers delimiting an array, don't think
|
of them as indexing 0 through n-1. Think of them as boundary
|
of them as indexing 0 through n-1. Think of them as boundary
|
markers:
|
markers:
|
|
|
|
|
|
|
beginning end
|
beginning end
|
| |
|
| |
|
| | This is bad. Always having to
|
| | This is bad. Always having to
|
| | remember to add or subtract one.
|
| | remember to add or subtract one.
|
| | Off-by-one bugs very common here.
|
| | Off-by-one bugs very common here.
|
V V
|
V V
|
array of N elements
|
array of N elements
|
|---|---|--...--|---|---|
|
|---|---|--...--|---|---|
|
| 0 | 1 | ... |N-2|N-1|
|
| 0 | 1 | ... |N-2|N-1|
|
|---|---|--...--|---|---|
|
|---|---|--...--|---|---|
|
|
|
^ ^
|
^ ^
|
| |
|
| |
|
| | This is good. This is safe. This
|
| | This is good. This is safe. This
|
| | is guaranteed to work. Just don't
|
| | is guaranteed to work. Just don't
|
| | dereference 'end'.
|
| | dereference 'end'.
|
beginning end
|
beginning end
|
|
|
|
|
See? Everything between the boundary markers is chapter of the array.
|
See? Everything between the boundary markers is chapter of the array.
|
Simple.
|
Simple.
|
|
|
Now think back to your junior-high school algebra course, when you
|
Now think back to your junior-high school algebra course, when you
|
were learning how to draw graphs. Remember that a graph terminating
|
were learning how to draw graphs. Remember that a graph terminating
|
with a solid dot meant, "Everything up through this point,"
|
with a solid dot meant, "Everything up through this point,"
|
and a graph terminating with an open dot meant, "Everything up
|
and a graph terminating with an open dot meant, "Everything up
|
to, but not including, this point," respectively called closed
|
to, but not including, this point," respectively called closed
|
and open ranges? Remember how closed ranges were written with
|
and open ranges? Remember how closed ranges were written with
|
brackets, [a,b], and open ranges were written with parentheses,
|
brackets, [a,b], and open ranges were written with parentheses,
|
(a,b)?
|
(a,b)?
|
|
|
The boundary markers for arrays describe a half-open range,
|
The boundary markers for arrays describe a half-open range,
|
starting with (and including) the first element, and ending with (but
|
starting with (and including) the first element, and ending with (but
|
not including) the last element: [beginning,end). See, I
|
not including) the last element: [beginning,end). See, I
|
told you it would be simple in the end.
|
told you it would be simple in the end.
|
|
|
Iterators, and everything working with iterators, follows this same
|
Iterators, and everything working with iterators, follows this same
|
time-honored tradition. A container's begin() method returns
|
time-honored tradition. A container's begin() method returns
|
an iterator referring to the first element, and its end()
|
an iterator referring to the first element, and its end()
|
method returns a past-the-end iterator, which is guaranteed to be
|
method returns a past-the-end iterator, which is guaranteed to be
|
unique and comparable against any other iterator pointing into the
|
unique and comparable against any other iterator pointing into the
|
middle of the container.
|
middle of the container.
|
|
|
Container constructors, container methods, and algorithms, all take
|
Container constructors, container methods, and algorithms, all take
|
pairs of iterators describing a range of values on which to operate.
|
pairs of iterators describing a range of values on which to operate.
|
All of these ranges are half-open ranges, so you pass the beginning
|
All of these ranges are half-open ranges, so you pass the beginning
|
iterator as the starting parameter, and the one-past-the-end iterator
|
iterator as the starting parameter, and the one-past-the-end iterator
|
as the finishing parameter.
|
as the finishing parameter.
|
|
|
This generalizes very well. You can operate on sub-ranges quite
|
This generalizes very well. You can operate on sub-ranges quite
|
easily this way; functions accepting a [first,last) range
|
easily this way; functions accepting a [first,last) range
|
don't know or care whether they are the boundaries of an entire {array,
|
don't know or care whether they are the boundaries of an entire {array,
|
sequence, container, whatever}, or whether they only enclose a few
|
sequence, container, whatever}, or whether they only enclose a few
|
elements from the center. This approach also makes zero-length
|
elements from the center. This approach also makes zero-length
|
sequences very simple to recognize: if the two endpoints compare
|
sequences very simple to recognize: if the two endpoints compare
|
equal, then the {array, sequence, container, whatever} is empty.
|
equal, then the {array, sequence, container, whatever} is empty.
|
|
|
Just don't dereference end().
|
Just don't dereference end().
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
