1 <?xml version="1.0" encoding="UTF-8" standalone="no"?> 2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter10. Iterators</title><meta name="generator" content="DocBook XSL Stylesheets Vsnapshot" /><meta name="keywords" content="ISO C++, library" /><meta name="keywords" content="ISO C++, runtime, library" /><link rel="home" href="../index.html" title="The GNU C++ Library" /><link rel="up" href="std_contents.html" title="PartII. Standard Contents" /><link rel="prev" href="containers_and_c.html" title="Interacting with C" /><link rel="next" href="algorithms.html" title="Chapter11. Algorithms" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter10. 3 Iterators 4 5 </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="containers_and_c.html">Prev</a></td><th width="60%" align="center">PartII. 6 Standard Contents 7 </th><td width="20%" align="right"><a accesskey="n" href="algorithms.html">Next</a></td></tr></table><hr /></div><div class="chapter"><div class="titlepage"><div><div><h2 class="title"><a id="std.iterators"></a>Chapter10. 8 Iterators 9 <a id="id-1.3.4.8.1.1.1" class="indexterm"></a> 10 </h2></div></div></div><div class="toc"><p><strong>Table of Contents</strong></p><dl class="toc"><dt><span class="section"><a href="iterators.html#std.iterators.predefined">Predefined</a></span></dt><dd><dl><dt><span class="section"><a href="iterators.html#iterators.predefined.vs_pointers">Iterators vs. Pointers</a></span></dt><dt><span class="section"><a href="iterators.html#iterators.predefined.end">One Past the End</a></span></dt></dl></dd></dl></div><div class="section"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="std.iterators.predefined"></a>Predefined</h2></div></div></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="iterators.predefined.vs_pointers"></a>Iterators vs. Pointers</h3></div></div></div><p> 11 The following 12 FAQ <a class="link" href="../faq.html#faq.iterator_as_pod" title="7.1.">entry</a> points out that 13 iterators are not implemented as pointers. They are a generalization 14 of pointers, but they are implemented in libstdc++ as separate 15 classes. 16 </p><p> 17 Keeping that simple fact in mind as you design your code will 18 prevent a whole lot of difficult-to-understand bugs. 19 </p><p> 20 You can think of it the other way 'round, even. Since iterators 21 are a generalization, that means 22 that <span class="emphasis"><em>pointers</em></span> are 23 <span class="emphasis"><em>iterators</em></span>, and that pointers can be used 24 whenever an iterator would be. All those functions in the 25 Algorithms section of the Standard will work just as well on plain 26 arrays and their pointers. 27 </p><p> 28 That doesn't mean that when you pass in a pointer, it gets 29 wrapped into some special delegating iterator-to-pointer class 30 with a layer of overhead. (If you think that's the case 31 anywhere, you don't understand templates to begin with...) Oh, 32 no; if you pass in a pointer, then the compiler will instantiate 33 that template using T* as a type, and good old high-speed 34 pointer arithmetic as its operations, so the resulting code will 35 be doing exactly the same things as it would be doing if you had 36 hand-coded it yourself (for the 273rd time). 37 </p><p> 38 How much overhead <span class="emphasis"><em>is</em></span> there when using an 39 iterator class? Very little. Most of the layering classes 40 contain nothing but typedefs, and typedefs are 41 "meta-information" that simply tell the compiler some 42 nicknames; they don't create code. That information gets passed 43 down through inheritance, so while the compiler has to do work 44 looking up all the names, your runtime code does not. (This has 45 been a prime concern from the beginning.) 46 </p></div><div class="section"><div class="titlepage"><div><div><h3 class="title"><a id="iterators.predefined.end"></a>One Past the End</h3></div></div></div><p>This starts off sounding complicated, but is actually very easy, 47 especially towards the end. Trust me. 48 </p><p>Beginners usually have a little trouble understand the whole 49 'past-the-end' thing, until they remember their early algebra classes 50 (see, they <span class="emphasis"><em>told</em></span> you that stuff would come in handy!) and 51 the concept of half-open ranges. 52 </p><p>First, some history, and a reminder of some of the funkier rules in 53 C and C++ for builtin arrays. The following rules have always been 54 true for both languages: 55 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>You can point anywhere in the array, <span class="emphasis"><em>or to the first element 56 past the end of the array</em></span>. A pointer that points to one 57 past the end of the array is guaranteed to be as unique as a 58 pointer to somewhere inside the array, so that you can compare 59 such pointers safely. 60 </p></li><li class="listitem"><p>You can only dereference a pointer that points into an array. 61 If your array pointer points outside the array -- even to just 62 one past the end -- and you dereference it, Bad Things happen. 63 </p></li><li class="listitem"><p>Strictly speaking, simply pointing anywhere else invokes 64 undefined behavior. Most programs won't puke until such a 65 pointer is actually dereferenced, but the standards leave that 66 up to the platform. 67 </p></li></ol></div><p>The reason this past-the-end addressing was allowed is to make it 68 easy to write a loop to go over an entire array, e.g., 69 while (*d++ = *s++);. 70 </p><p>So, when you think of two pointers delimiting an array, don't think 71 of them as indexing 0 through n-1. Think of them as <span class="emphasis"><em>boundary 72 markers</em></span>: 73 </p><pre class="programlisting"> 74 75 beginning end 76 | | 77 | | This is bad. Always having to 78 | | remember to add or subtract one. 79 | | Off-by-one bugs very common here. 80 V V 81 array of N elements 82 |---|---|--...--|---|---| 83 | 0 | 1 | ... |N-2|N-1| 84 |---|---|--...--|---|---| 85 86 ^ ^ 87 | | 88 | | This is good. This is safe. This 89 | | is guaranteed to work. Just don't 90 | | dereference 'end'. 91 beginning end 92 93 </pre><p>See? Everything between the boundary markers is chapter of the array. 94 Simple. 95 </p><p>Now think back to your junior-high school algebra course, when you 96 were learning how to draw graphs. Remember that a graph terminating 97 with a solid dot meant, "Everything up through this point," 98 and a graph terminating with an open dot meant, "Everything up 99 to, but not including, this point," respectively called closed 100 and open ranges? Remember how closed ranges were written with 101 brackets, <span class="emphasis"><em>[a,b]</em></span>, and open ranges were written with parentheses, 102 <span class="emphasis"><em>(a,b)</em></span>? 103 </p><p>The boundary markers for arrays describe a <span class="emphasis"><em>half-open range</em></span>, 104 starting with (and including) the first element, and ending with (but 105 not including) the last element: <span class="emphasis"><em>[beginning,end)</em></span>. See, I 106 told you it would be simple in the end. 107 </p><p>Iterators, and everything working with iterators, follows this same 108 time-honored tradition. A container's <code class="code">begin()</code> method returns 109 an iterator referring to the first element, and its <code class="code">end()</code> 110 method returns a past-the-end iterator, which is guaranteed to be 111 unique and comparable against any other iterator pointing into the 112 middle of the container. 113 </p><p>Container constructors, container methods, and algorithms, all take 114 pairs of iterators describing a range of values on which to operate. 115 All of these ranges are half-open ranges, so you pass the beginning 116 iterator as the starting parameter, and the one-past-the-end iterator 117 as the finishing parameter. 118 </p><p>This generalizes very well. You can operate on sub-ranges quite 119 easily this way; functions accepting a <span class="emphasis"><em>[first,last)</em></span> range 120 don't know or care whether they are the boundaries of an entire {array, 121 sequence, container, whatever}, or whether they only enclose a few 122 elements from the center. This approach also makes zero-length 123 sequences very simple to recognize: if the two endpoints compare 124 equal, then the {array, sequence, container, whatever} is empty. 125 </p><p>Just don't dereference <code class="code">end()</code>. 126 </p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="containers_and_c.html">Prev</a></td><td width="20%" align="center"><a accesskey="u" href="std_contents.html">Up</a></td><td width="40%" align="right"><a accesskey="n" href="algorithms.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Interacting with C</td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top">Chapter11. 127 Algorithms 128 129 </td></tr></table></div></body></html>
Indexes created Thu Jul 16 00:26:27 UTC 2026