libstdc++-v3/docs/html/24_iterators/howto.html

   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++ 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++ 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 &quot;meta-information&quot; 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, &quot;Everything up through this point,&quot;
 148       and a graph terminating with an open dot meant, &quot;Everything up
 149       to, but not including, this point,&quot; 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>