libstdc++-v3/doc/html/manual/bk01pt08ch19s02.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>One Past the End</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="bk01pt08ch19.html" title="Chapter 19. Predefined" /><link rel="prev" href="bk01pt08ch19.html" title="Chapter 19. Predefined" /><link rel="next" href="algorithms.html" title="Part IX.  Algorithms" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">One Past the End</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="bk01pt08ch19.html">Prev</a> </td><th width="60%" align="center">Chapter 19. Predefined</th><td width="20%" align="right"> <a accesskey="n" href="algorithms.html">Next</a></td></tr></table><hr /></div><div class="sect1" title="One Past the End"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="iterators.predefined.end"></a>One Past the End</h2></div></div></div><p>This starts off sounding complicated, but is actually very easy,
   4       especially towards the end.  Trust me.
   5    </p><p>Beginners usually have a little trouble understand the whole
   6       'past-the-end' thing, until they remember their early algebra classes
   7       (see, they <span class="emphasis"><em>told</em></span> you that stuff would come in handy!) and
   8       the concept of half-open ranges.
   9    </p><p>First, some history, and a reminder of some of the funkier rules in
  10       C and C++ for builtin arrays.  The following rules have always been
  11       true for both languages:
  12    </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
  13           past the end of the array</em></span>.  A pointer that points to one
  14           past the end of the array is guaranteed to be as unique as a
  15           pointer to somewhere inside the array, so that you can compare
  16           such pointers safely.
  17         </p></li><li class="listitem"><p>You can only dereference a pointer that points into an array.
  18           If your array pointer points outside the array -- even to just
  19           one past the end -- and you dereference it, Bad Things happen.
  20         </p></li><li class="listitem"><p>Strictly speaking, simply pointing anywhere else invokes
  21           undefined behavior.  Most programs won't puke until such a
  22           pointer is actually dereferenced, but the standards leave that
  23           up to the platform.
  24         </p></li></ol></div><p>The reason this past-the-end addressing was allowed is to make it
  25       easy to write a loop to go over an entire array, e.g.,
  26       while (*d++ = *s++);.
  27    </p><p>So, when you think of two pointers delimiting an array, don't think
  28       of them as indexing 0 through n-1.  Think of them as <span class="emphasis"><em>boundary
  29       markers</em></span>:
  30    </p><pre class="programlisting">
  31
  32    beginning            end
  33      |                   |
  34      |                   |               This is bad.  Always having to
  35      |                   |               remember to add or subtract one.
  36      |                   |               Off-by-one bugs very common here.
  37      V                   V
  38         array of N elements
  39      |---|---|--...--|---|---|
  40      | 0 | 1 |  ...  |N-2|N-1|
  41      |---|---|--...--|---|---|
  42
  43      ^                       ^
  44      |                       |
  45      |                       |           This is good.  This is safe.  This
  46      |                       |           is guaranteed to work.  Just don't
  47      |                       |           dereference 'end'.
  48    beginning                end
  49
  50    </pre><p>See?  Everything between the boundary markers is part of the array.
  51       Simple.
  52    </p><p>Now think back to your junior-high school algebra course, when you
  53       were learning how to draw graphs.  Remember that a graph terminating
  54       with a solid dot meant, "Everything up through this point,"
  55       and a graph terminating with an open dot meant, "Everything up
  56       to, but not including, this point," respectively called closed
  57       and open ranges?  Remember how closed ranges were written with
  58       brackets, <span class="emphasis"><em>[a,b]</em></span>, and open ranges were written with parentheses,
  59       <span class="emphasis"><em>(a,b)</em></span>?
  60    </p><p>The boundary markers for arrays describe a <span class="emphasis"><em>half-open range</em></span>,
  61       starting with (and including) the first element, and ending with (but
  62       not including) the last element:  <span class="emphasis"><em>[beginning,end)</em></span>.  See, I
  63       told you it would be simple in the end.
  64    </p><p>Iterators, and everything working with iterators, follows this same
  65       time-honored tradition.  A container's <code class="code">begin()</code> method returns
  66       an iterator referring to the first element, and its <code class="code">end()</code>
  67       method returns a past-the-end iterator, which is guaranteed to be
  68       unique and comparable against any other iterator pointing into the
  69       middle of the container.
  70    </p><p>Container constructors, container methods, and algorithms, all take
  71       pairs of iterators describing a range of values on which to operate.
  72       All of these ranges are half-open ranges, so you pass the beginning
  73       iterator as the starting parameter, and the one-past-the-end iterator
  74       as the finishing parameter.
  75    </p><p>This generalizes very well.  You can operate on sub-ranges quite
  76       easily this way; functions accepting a <span class="emphasis"><em>[first,last)</em></span> range
  77       don't know or care whether they are the boundaries of an entire {array,
  78       sequence, container, whatever}, or whether they only enclose a few
  79       elements from the center.  This approach also makes zero-length
  80       sequences very simple to recognize:  if the two endpoints compare
  81       equal, then the {array, sequence, container, whatever} is empty.
  82    </p><p>Just don't dereference <code class="code">end()</code>.
  83    </p></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="bk01pt08ch19.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="bk01pt08ch19.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">Chapter 19. Predefined </td><td width="20%" align="center"><a accesskey="h" href="../spine.html">Home</a></td><td width="40%" align="right" valign="top"> Part IX.
  84   Algorithms
  85
  86 </td></tr></table></div></body></html>