libstdc++-v3/doc/html/manual/iterators.html

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