| 1 |
20 |
jlechner |
<?xml version="1.0" encoding="ISO-8859-1"?>
|
| 2 |
|
|
<!DOCTYPE html
|
| 3 |
|
|
PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
|
| 4 |
|
|
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
|
| 5 |
|
|
|
| 6 |
|
|
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
|
| 7 |
|
|
<head>
|
| 8 |
|
|
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
|
| 9 |
|
|
<meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" />
|
| 10 |
|
|
<meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" />
|
| 11 |
|
|
<meta name="DESCRIPTION" content="HOWTO for the libstdc++ chapter 24." />
|
| 12 |
|
|
<meta name="GENERATOR" content="vi and eight fingers" />
|
| 13 |
|
|
<title>libstdc++-v3 HOWTO: Chapter 24: Iterators</title>
|
| 14 |
|
|
<link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
|
| 15 |
|
|
<link rel="Start" href="../documentation.html" type="text/html"
|
| 16 |
|
|
title="GNU C++ Standard Library" />
|
| 17 |
|
|
<link rel="Prev" href="../23_containers/howto.html" type="text/html"
|
| 18 |
|
|
title="Containers" />
|
| 19 |
|
|
<link rel="Next" href="../25_algorithms/howto.html" type="text/html"
|
| 20 |
|
|
title="Algorithms" />
|
| 21 |
|
|
<link rel="Copyright" href="../17_intro/license.html" type="text/html" />
|
| 22 |
|
|
<link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." />
|
| 23 |
|
|
</head>
|
| 24 |
|
|
<body>
|
| 25 |
|
|
|
| 26 |
|
|
<h1 class="centered"><a name="top">Chapter 24: Iterators</a></h1>
|
| 27 |
|
|
|
| 28 |
|
|
<p>Chapter 24 deals with the FORTRAN subroutines for automatically
|
| 29 |
|
|
transforming lemmings into gold.
|
| 30 |
|
|
</p>
|
| 31 |
|
|
|
| 32 |
|
|
|
| 33 |
|
|
<!-- ####################################################### -->
|
| 34 |
|
|
<hr />
|
| 35 |
|
|
<h1>Contents</h1>
|
| 36 |
|
|
<ul>
|
| 37 |
|
|
<li><a href="#1">They ain't pointers!</a></li>
|
| 38 |
|
|
<li><a href="#2">It ends <em>where?</em></a></li>
|
| 39 |
|
|
</ul>
|
| 40 |
|
|
|
| 41 |
|
|
<hr />
|
| 42 |
|
|
|
| 43 |
|
|
<!-- ####################################################### -->
|
| 44 |
|
|
|
| 45 |
|
|
<h2><a name="1">They ain't pointers!</a></h2>
|
| 46 |
|
|
<p><a href="../faq/index.html#5_1">FAQ 5.1</a> points out that iterators
|
| 47 |
|
|
are not implemented as pointers. They are a generalization of
|
| 48 |
|
|
pointers, but they are implemented in libstdc++-v3 as separate classes.
|
| 49 |
|
|
</p>
|
| 50 |
|
|
<p>Keeping that simple fact in mind as you design your code will
|
| 51 |
|
|
prevent a whole lot of difficult-to-understand bugs.
|
| 52 |
|
|
</p>
|
| 53 |
|
|
<p>You can think of it the other way 'round, even. Since iterators
|
| 54 |
|
|
are a generalization, that means that <em>pointers</em> are
|
| 55 |
|
|
<em>iterators</em>, and that pointers can be used whenever an
|
| 56 |
|
|
iterator would be. All those functions in the Algorithms chapter
|
| 57 |
|
|
of the Standard will work just as well on plain arrays and their
|
| 58 |
|
|
pointers.
|
| 59 |
|
|
</p>
|
| 60 |
|
|
<p>That doesn't mean that when you pass in a pointer, it gets wrapped
|
| 61 |
|
|
into some special delegating iterator-to-pointer class with a layer
|
| 62 |
|
|
of overhead. (If you think that's the case anywhere, you don't
|
| 63 |
|
|
understand templates to begin with...) Oh, no; if you pass
|
| 64 |
|
|
in a pointer, then the compiler will instantiate that template
|
| 65 |
|
|
using T* as a type, and good old high-speed pointer arithmetic as
|
| 66 |
|
|
its operations, so the resulting code will be doing exactly the same
|
| 67 |
|
|
things as it would be doing if you had hand-coded it yourself (for
|
| 68 |
|
|
the 273rd time).
|
| 69 |
|
|
</p>
|
| 70 |
|
|
<p>How much overhead <em>is</em> there when using an interator class?
|
| 71 |
|
|
Very little. Most of the layering classes contain nothing but
|
| 72 |
|
|
typedefs, and typedefs are "meta-information" that simply
|
| 73 |
|
|
tell the compiler some nicknames; they don't create code. That
|
| 74 |
|
|
information gets passed down through inheritance, so while the
|
| 75 |
|
|
compiler has to do work looking up all the names, your runtime code
|
| 76 |
|
|
does not. (This has been a prime concern from the beginning.)
|
| 77 |
|
|
</p>
|
| 78 |
|
|
<p>Return <a href="#top">to top of page</a> or
|
| 79 |
|
|
<a href="../faq/index.html">to the FAQ</a>.
|
| 80 |
|
|
</p>
|
| 81 |
|
|
|
| 82 |
|
|
<hr />
|
| 83 |
|
|
<h2><a name="2">It ends <em>where?</em></a></h2>
|
| 84 |
|
|
<p>This starts off sounding complicated, but is actually very easy,
|
| 85 |
|
|
especially towards the end. Trust me.
|
| 86 |
|
|
</p>
|
| 87 |
|
|
<p>Beginners usually have a little trouble understand the whole
|
| 88 |
|
|
'past-the-end' thing, until they remember their early algebra classes
|
| 89 |
|
|
(see, they <em>told</em> you that stuff would come in handy!) and
|
| 90 |
|
|
the concept of half-open ranges.
|
| 91 |
|
|
</p>
|
| 92 |
|
|
<p>First, some history, and a reminder of some of the funkier rules in
|
| 93 |
|
|
C and C++ for builtin arrays. The following rules have always been
|
| 94 |
|
|
true for both languages:
|
| 95 |
|
|
</p>
|
| 96 |
|
|
<ol>
|
| 97 |
|
|
<li>You can point anywhere in the array, <em>or to the first element
|
| 98 |
|
|
past the end of the array</em>. A pointer that points to one
|
| 99 |
|
|
past the end of the array is guaranteed to be as unique as a
|
| 100 |
|
|
pointer to somewhere inside the array, so that you can compare
|
| 101 |
|
|
such pointers safely.
|
| 102 |
|
|
</li>
|
| 103 |
|
|
<li>You can only dereference a pointer that points into an array.
|
| 104 |
|
|
If your array pointer points outside the array -- even to just
|
| 105 |
|
|
one past the end -- and you dereference it, Bad Things happen.
|
| 106 |
|
|
</li>
|
| 107 |
|
|
<li>Strictly speaking, simply pointing anywhere else invokes
|
| 108 |
|
|
undefined behavior. Most programs won't puke until such a
|
| 109 |
|
|
pointer is actually dereferenced, but the standards leave that
|
| 110 |
|
|
up to the platform.
|
| 111 |
|
|
</li>
|
| 112 |
|
|
</ol>
|
| 113 |
|
|
<p>The reason this past-the-end addressing was allowed is to make it
|
| 114 |
|
|
easy to write a loop to go over an entire array, e.g.,
|
| 115 |
|
|
while (*d++ = *s++);.
|
| 116 |
|
|
</p>
|
| 117 |
|
|
<p>So, when you think of two pointers delimiting an array, don't think
|
| 118 |
|
|
of them as indexing 0 through n-1. Think of them as <em>boundary
|
| 119 |
|
|
markers</em>:
|
| 120 |
|
|
</p>
|
| 121 |
|
|
<pre>
|
| 122 |
|
|
|
| 123 |
|
|
beginning end
|
| 124 |
|
|
| |
|
| 125 |
|
|
| | This is bad. Always having to
|
| 126 |
|
|
| | remember to add or subtract one.
|
| 127 |
|
|
| | Off-by-one bugs very common here.
|
| 128 |
|
|
V V
|
| 129 |
|
|
array of N elements
|
| 130 |
|
|
|---|---|--...--|---|---|
|
| 131 |
|
|
| 0 | 1 | ... |N-2|N-1|
|
| 132 |
|
|
|---|---|--...--|---|---|
|
| 133 |
|
|
|
| 134 |
|
|
^ ^
|
| 135 |
|
|
| |
|
| 136 |
|
|
| | This is good. This is safe. This
|
| 137 |
|
|
| | is guaranteed to work. Just don't
|
| 138 |
|
|
| | dereference 'end'.
|
| 139 |
|
|
beginning end
|
| 140 |
|
|
|
| 141 |
|
|
</pre>
|
| 142 |
|
|
<p>See? Everything between the boundary markers is part of the array.
|
| 143 |
|
|
Simple.
|
| 144 |
|
|
</p>
|
| 145 |
|
|
<p>Now think back to your junior-high school algebra course, when you
|
| 146 |
|
|
were learning how to draw graphs. Remember that a graph terminating
|
| 147 |
|
|
with a solid dot meant, "Everything up through this point,"
|
| 148 |
|
|
and a graph terminating with an open dot meant, "Everything up
|
| 149 |
|
|
to, but not including, this point," respectively called closed
|
| 150 |
|
|
and open ranges? Remember how closed ranges were written with
|
| 151 |
|
|
brackets, <em>[a,b]</em>, and open ranges were written with parentheses,
|
| 152 |
|
|
<em>(a,b)</em>?
|
| 153 |
|
|
</p>
|
| 154 |
|
|
<p>The boundary markers for arrays describe a <em>half-open range</em>,
|
| 155 |
|
|
starting with (and including) the first element, and ending with (but
|
| 156 |
|
|
not including) the last element: <em>[beginning,end)</em>. See, I
|
| 157 |
|
|
told you it would be simple in the end.
|
| 158 |
|
|
</p>
|
| 159 |
|
|
<p>Iterators, and everything working with iterators, follows this same
|
| 160 |
|
|
time-honored tradition. A container's <code>begin()</code> method returns
|
| 161 |
|
|
an iterator referring to the first element, and its <code>end()</code>
|
| 162 |
|
|
method returns a past-the-end iterator, which is guaranteed to be
|
| 163 |
|
|
unique and comparable against any other iterator pointing into the
|
| 164 |
|
|
middle of the container.
|
| 165 |
|
|
</p>
|
| 166 |
|
|
<p>Container constructors, container methods, and algorithms, all take
|
| 167 |
|
|
pairs of iterators describing a range of values on which to operate.
|
| 168 |
|
|
All of these ranges are half-open ranges, so you pass the beginning
|
| 169 |
|
|
iterator as the starting parameter, and the one-past-the-end iterator
|
| 170 |
|
|
as the finishing parameter.
|
| 171 |
|
|
</p>
|
| 172 |
|
|
<p>This generalizes very well. You can operate on sub-ranges quite
|
| 173 |
|
|
easily this way; functions accepting a <em>[first,last)</em> range
|
| 174 |
|
|
don't know or care whether they are the boundaries of an entire {array,
|
| 175 |
|
|
sequence, container, whatever}, or whether they only enclose a few
|
| 176 |
|
|
elements from the center. This approach also makes zero-length
|
| 177 |
|
|
sequences very simple to recognize: if the two endpoints compare
|
| 178 |
|
|
equal, then the {array, sequence, container, whatever} is empty.
|
| 179 |
|
|
</p>
|
| 180 |
|
|
<p>Just don't dereference <code>end()</code>.
|
| 181 |
|
|
</p>
|
| 182 |
|
|
<p>Return <a href="#top">to top of page</a> or
|
| 183 |
|
|
<a href="../faq/index.html">to the FAQ</a>.
|
| 184 |
|
|
</p>
|
| 185 |
|
|
|
| 186 |
|
|
|
| 187 |
|
|
|
| 188 |
|
|
|
| 189 |
|
|
<!-- ####################################################### -->
|
| 190 |
|
|
|
| 191 |
|
|
<hr />
|
| 192 |
|
|
<p class="fineprint"><em>
|
| 193 |
|
|
See <a href="../17_intro/license.html">license.html</a> for copying conditions.
|
| 194 |
|
|
Comments and suggestions are welcome, and may be sent to
|
| 195 |
|
|
<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
|
| 196 |
|
|
</em></p>
|
| 197 |
|
|
|
| 198 |
|
|
|
| 199 |
|
|
</body>
|
| 200 |
|
|
</html>
|
