1<?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 iterator 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> 193See <a href="../17_intro/license.html">license.html</a> for copying conditions. 194Comments 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> 201