llvm-gcc-4.0/libstdc++-v3/docs/html/24_iterators/howto.html - llvm-archive - Git at Google

 <?xml version="1.0" encoding="ISO-8859-1"?>
 <!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" xml:lang="en" lang="en">
 <head>
    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
    <meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" />
    <meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" />
    <meta name="DESCRIPTION" content="HOWTO for the libstdc++ chapter 24." />
    <meta name="GENERATOR" content="vi and eight fingers" />
    <title>libstdc++-v3 HOWTO:  Chapter 24: Iterators</title>
 <link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
 <link rel="Start" href="../documentation.html" type="text/html"
   title="GNU C++ Standard Library" />
 <link rel="Prev" href="../23_containers/howto.html" type="text/html"
   title="Containers" />
 <link rel="Next" href="../25_algorithms/howto.html" type="text/html"
   title="Algorithms" />
 <link rel="Copyright" href="../17_intro/license.html" type="text/html" />
 <link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." />
 </head>
 <body>

 <h1 class="centered"><a name="top">Chapter 24:  Iterators</a></h1>

 <p>Chapter 24 deals with the FORTRAN subroutines for automatically
    transforming lemmings into gold.
 </p>


 <!-- ####################################################### -->
 <hr />
 <h1>Contents</h1>
 <ul>
    <li><a href="#1">They ain't pointers!</a></li>
    <li><a href="#2">It ends <em>where?</em></a></li>
 </ul>

 <hr />

 <!-- ####################################################### -->

 <h2><a name="1">They ain't pointers!</a></h2>
    <p><a href="../faq/index.html#5_1">FAQ 5.1</a> points out that iterators
       are not implemented as pointers.  They are a generalization of
       pointers, but they are implemented in libstdc++-v3 as separate classes.
    </p>
    <p>Keeping that simple fact in mind as you design your code will
       prevent a whole lot of difficult-to-understand bugs.
    </p>
    <p>You can think of it the other way 'round, even.  Since iterators
       are a generalization, that means that <em>pointers</em> are
       <em>iterators</em>, and that pointers can be used whenever an
       iterator would be.  All those functions in the Algorithms chapter
       of the Standard will work just as well on plain arrays and their
       pointers.
    </p>
    <p>That doesn't mean that when you pass in a pointer, it gets wrapped
       into some special delegating iterator-to-pointer class with a layer
       of overhead.  (If you think that's the case anywhere, you don't
       understand templates to begin with...)  Oh, no; if you pass
       in a pointer, then the compiler will instantiate that template
       using T* as a type, and good old high-speed pointer arithmetic as
       its operations, so the resulting code will be doing exactly the same
       things as it would be doing if you had hand-coded it yourself (for
       the 273rd time).
    </p>
    <p>How much overhead <em>is</em> there when using an interator class?
       Very little.  Most of the layering classes contain nothing but
       typedefs, and typedefs are &quot;meta-information&quot; that simply
       tell the compiler some nicknames; they don't create code.  That
       information gets passed down through inheritance, so while the
       compiler has to do work looking up all the names, your runtime code
       does not.  (This has been a prime concern from the beginning.)
    </p>
    <p>Return <a href="#top">to top of page</a> or
       <a href="../faq/index.html">to the FAQ</a>.
    </p>

 <hr />
 <h2><a name="2">It ends <em>where?</em></a></h2>
    <p>This starts off sounding complicated, but is actually very easy,
       especially towards the end.  Trust me.
    </p>
    <p>Beginners usually have a little trouble understand the whole
       'past-the-end' thing, until they remember their early algebra classes
       (see, they <em>told</em> you that stuff would come in handy!) and
       the concept of half-open ranges.
    </p>
    <p>First, some history, and a reminder of some of the funkier rules in
       C and C++ for builtin arrays.  The following rules have always been
       true for both languages:
    </p>
    <ol>
       <li>You can point anywhere in the array, <em>or to the first element
           past the end of the array</em>.  A pointer that points to one
           past the end of the array is guaranteed to be as unique as a
           pointer to somewhere inside the array, so that you can compare
           such pointers safely.
       </li>
       <li>You can only dereference a pointer that points into an array.
           If your array pointer points outside the array -- even to just
           one past the end -- and you dereference it, Bad Things happen.
       </li>
       <li>Strictly speaking, simply pointing anywhere else invokes
           undefined behavior.  Most programs won't puke until such a
           pointer is actually dereferenced, but the standards leave that
           up to the platform.
       </li>
    </ol>
    <p>The reason this past-the-end addressing was allowed is to make it
       easy to write a loop to go over an entire array, e.g.,
       while (*d++ = *s++);.
    </p>
    <p>So, when you think of two pointers delimiting an array, don't think
       of them as indexing 0 through n-1.  Think of them as <em>boundary
       markers</em>:
    </p>
    <pre>

    beginning            end
      |                   |
      |                   |               This is bad.  Always having to
      |                   |               remember to add or subtract one.
      |                   |               Off-by-one bugs very common here.
      V                   V
         array of N elements
      |---|---|--...--|---|---|
      | 0 | 1 |  ...  |N-2|N-1|
      |---|---|--...--|---|---|

      ^                       ^
      |                       |
      |                       |           This is good.  This is safe.  This
      |                       |           is guaranteed to work.  Just don't
      |                       |           dereference 'end'.
    beginning                end

    </pre>
    <p>See?  Everything between the boundary markers is part of the array.
       Simple.
    </p>
    <p>Now think back to your junior-high school algebra course, when you
       were learning how to draw graphs.  Remember that a graph terminating
       with a solid dot meant, &quot;Everything up through this point,&quot;
       and a graph terminating with an open dot meant, &quot;Everything up
       to, but not including, this point,&quot; respectively called closed
       and open ranges?  Remember how closed ranges were written with
       brackets, <em>[a,b]</em>, and open ranges were written with parentheses,
       <em>(a,b)</em>?
    </p>
    <p>The boundary markers for arrays describe a <em>half-open range</em>,
       starting with (and including) the first element, and ending with (but
       not including) the last element:  <em>[beginning,end)</em>.  See, I
       told you it would be simple in the end.
    </p>
    <p>Iterators, and everything working with iterators, follows this same
       time-honored tradition.  A container's <code>begin()</code> method returns
       an iterator referring to the first element, and its <code>end()</code>
       method returns a past-the-end iterator, which is guaranteed to be
       unique and comparable against any other iterator pointing into the
       middle of the container.
    </p>
    <p>Container constructors, container methods, and algorithms, all take
       pairs of iterators describing a range of values on which to operate.
       All of these ranges are half-open ranges, so you pass the beginning
       iterator as the starting parameter, and the one-past-the-end iterator
       as the finishing parameter.
    </p>
    <p>This generalizes very well.  You can operate on sub-ranges quite
       easily this way; functions accepting a <em>[first,last)</em> range
       don't know or care whether they are the boundaries of an entire {array,
       sequence, container, whatever}, or whether they only enclose a few
       elements from the center.  This approach also makes zero-length
       sequences very simple to recognize:  if the two endpoints compare
       equal, then the {array, sequence, container, whatever} is empty.
    </p>
    <p>Just don't dereference <code>end()</code>.
    </p>
    <p>Return <a href="#top">to top of page</a> or
       <a href="../faq/index.html">to the FAQ</a>.
    </p>


 <!-- ####################################################### -->

 <hr />
 <p class="fineprint"><em>
 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
 Comments and suggestions are welcome, and may be sent to
 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
 </em></p>


 </body>
 </html>
	<?xml version="1.0" encoding="ISO-8859-1"?>
	<!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" xml:lang="en" lang="en">
	<head>
	<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
	<meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" />
	<meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" />
	<meta name="DESCRIPTION" content="HOWTO for the libstdc++ chapter 24." />
	<meta name="GENERATOR" content="vi and eight fingers" />
	<title>libstdc++-v3 HOWTO: Chapter 24: Iterators</title>
	<link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
	<link rel="Start" href="../documentation.html" type="text/html"
	title="GNU C++ Standard Library" />
	<link rel="Prev" href="../23_containers/howto.html" type="text/html"
	title="Containers" />
	<link rel="Next" href="../25_algorithms/howto.html" type="text/html"
	title="Algorithms" />
	<link rel="Copyright" href="../17_intro/license.html" type="text/html" />
	<link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." />
	</head>
	<body>

	<h1 class="centered"><a name="top">Chapter 24: Iterators</a></h1>

	<p>Chapter 24 deals with the FORTRAN subroutines for automatically
	transforming lemmings into gold.
	</p>


	<!-- ####################################################### -->
	<hr />
	<h1>Contents</h1>
	<ul>
	<li><a href="#1">They ain't pointers!</a></li>
	<li><a href="#2">It ends <em>where?</em></a></li>
	</ul>

	<hr />

	<!-- ####################################################### -->

	<h2><a name="1">They ain't pointers!</a></h2>
	<p><a href="../faq/index.html#5_1">FAQ 5.1</a> points out that iterators
	are not implemented as pointers. They are a generalization of
	pointers, but they are implemented in libstdc++-v3 as separate classes.
	</p>
	<p>Keeping that simple fact in mind as you design your code will
	prevent a whole lot of difficult-to-understand bugs.
	</p>
	<p>You can think of it the other way 'round, even. Since iterators
	are a generalization, that means that <em>pointers</em> are
	<em>iterators</em>, and that pointers can be used whenever an
	iterator would be. All those functions in the Algorithms chapter
	of the Standard will work just as well on plain arrays and their
	pointers.
	</p>
	<p>That doesn't mean that when you pass in a pointer, it gets wrapped
	into some special delegating iterator-to-pointer class with a layer
	of overhead. (If you think that's the case anywhere, you don't
	understand templates to begin with...) Oh, no; if you pass
	in a pointer, then the compiler will instantiate that template
	using T* as a type, and good old high-speed pointer arithmetic as
	its operations, so the resulting code will be doing exactly the same
	things as it would be doing if you had hand-coded it yourself (for
	the 273rd time).
	</p>
	<p>How much overhead <em>is</em> there when using an interator class?
	Very little. Most of the layering classes contain nothing but
	typedefs, and typedefs are "meta-information" that simply
	tell the compiler some nicknames; they don't create code. That
	information gets passed down through inheritance, so while the
	compiler has to do work looking up all the names, your runtime code
	does not. (This has been a prime concern from the beginning.)
	</p>
	<p>Return <a href="#top">to top of page</a> or
	<a href="../faq/index.html">to the FAQ</a>.
	</p>

	<hr />
	<h2><a name="2">It ends <em>where?</em></a></h2>
	<p>This starts off sounding complicated, but is actually very easy,
	especially towards the end. Trust me.
	</p>
	<p>Beginners usually have a little trouble understand the whole
	'past-the-end' thing, until they remember their early algebra classes
	(see, they <em>told</em> you that stuff would come in handy!) and
	the concept of half-open ranges.
	</p>
	<p>First, some history, and a reminder of some of the funkier rules in
	C and C++ for builtin arrays. The following rules have always been
	true for both languages:
	</p>
	<ol>
	<li>You can point anywhere in the array, <em>or to the first element
	past the end of the array</em>. A pointer that points to one
	past the end of the array is guaranteed to be as unique as a
	pointer to somewhere inside the array, so that you can compare
	such pointers safely.
	</li>
	<li>You can only dereference a pointer that points into an array.
	If your array pointer points outside the array -- even to just
	one past the end -- and you dereference it, Bad Things happen.
	</li>
	<li>Strictly speaking, simply pointing anywhere else invokes
	undefined behavior. Most programs won't puke until such a
	pointer is actually dereferenced, but the standards leave that
	up to the platform.
	</li>
	</ol>
	<p>The reason this past-the-end addressing was allowed is to make it
	easy to write a loop to go over an entire array, e.g.,
	while (d++ = s++);.
	</p>
	<p>So, when you think of two pointers delimiting an array, don't think
	of them as indexing 0 through n-1. Think of them as <em>boundary
	markers</em>:
	</p>
	<pre>

	beginning end
	\| \|
	\| \| This is bad. Always having to
	\| \| remember to add or subtract one.
	\| \| Off-by-one bugs very common here.
	V V
	array of N elements
	\|---\|---\|--...--\|---\|---\|
	\| 0 \| 1 \| ... \|N-2\|N-1\|
	\|---\|---\|--...--\|---\|---\|

	^ ^
	\| \|
	\| \| This is good. This is safe. This
	\| \| is guaranteed to work. Just don't
	\| \| dereference 'end'.
	beginning end

	</pre>
	<p>See? Everything between the boundary markers is part of the array.
	Simple.
	</p>
	<p>Now think back to your junior-high school algebra course, when you
	were learning how to draw graphs. Remember that a graph terminating
	with a solid dot meant, "Everything up through this point,"
	and a graph terminating with an open dot meant, "Everything up
	to, but not including, this point," respectively called closed
	and open ranges? Remember how closed ranges were written with
	brackets, <em>[a,b]</em>, and open ranges were written with parentheses,
	<em>(a,b)</em>?
	</p>
	<p>The boundary markers for arrays describe a <em>half-open range</em>,
	starting with (and including) the first element, and ending with (but
	not including) the last element: <em>[beginning,end)</em>. See, I
	told you it would be simple in the end.
	</p>
	<p>Iterators, and everything working with iterators, follows this same
	time-honored tradition. A container's <code>begin()</code> method returns
	an iterator referring to the first element, and its <code>end()</code>
	method returns a past-the-end iterator, which is guaranteed to be
	unique and comparable against any other iterator pointing into the
	middle of the container.
	</p>
	<p>Container constructors, container methods, and algorithms, all take
	pairs of iterators describing a range of values on which to operate.
	All of these ranges are half-open ranges, so you pass the beginning
	iterator as the starting parameter, and the one-past-the-end iterator
	as the finishing parameter.
	</p>
	<p>This generalizes very well. You can operate on sub-ranges quite
	easily this way; functions accepting a <em>[first,last)</em> range
	don't know or care whether they are the boundaries of an entire {array,
	sequence, container, whatever}, or whether they only enclose a few
	elements from the center. This approach also makes zero-length
	sequences very simple to recognize: if the two endpoints compare
	equal, then the {array, sequence, container, whatever} is empty.
	</p>
	<p>Just don't dereference <code>end()</code>.
	</p>
	<p>Return <a href="#top">to top of page</a> or
	<a href="../faq/index.html">to the FAQ</a>.
	</p>




	<!-- ####################################################### -->

	<hr />
	<p class="fineprint"><em>
	See <a href="../17_intro/license.html">license.html</a> for copying conditions.
	Comments and suggestions are welcome, and may be sent to
	<a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
	</em></p>


	</body>
	</html>