+++ /dev/null
-<?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</title>
-<link rel="StyleSheet" href="../lib3styles.css" />
-</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>
projects / msp430-gcc.git / blobdiff