| <?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 iterator 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> |