2008-01-18 Benjamin Kosnik <bkoz@redhat.com>

* docs/*: To... * doc/*: ...here. * testsuite/Makefile.am: Move doc-performance to... * Makefile.am: Add doc to SUBDIRS, move doxygen-* rules to... * doc/Makefile.am: Consolidate documentation creation here. (doc-doxygen-html): New. (doc-doxygen-man): New. (doc-performance): New. * doc/Makefile.in: New. * acinclude.m4 (glibcxx_SUBDIRS): Add doc directory. * doc/doxygen/guide.html: Edit for unified html configuration. * doc/doxygen/mainpage.html: Same. * doc/doxygen/run_doxygen: Same, more namespace fixups for man generation. * doc/doxygen/user.cfg.in: Update for doxygen 1.5.4. * include/tr1_impl/random: Remove maint from doxygen markup. * include/tr1_impl/functional: Same. * include/std/tuple: Same. * include/std/streambuf: Same. * include/std/bitset: Same. * include/std/limits: Same. * include/std/fstream: Same. * include/std/istream: Same. * include/std/sstream: Same. * include/ext/pool_allocator.h: Same. * include/ext/rc_string_base.h: Same. * include/bits/basic_ios.h: Same. * include/bits/stl_list.h: Same. * include/bits/stl_map.h: Same. * include/bits/locale_classes.h: Same. * include/bits/stl_set.h: Same. * include/bits/stl_iterator_base_types.h: Same. * include/bits/basic_string.h: Same. * include/bits/stl_multimap.h: Same. * include/bits/stl_vector.h: Same. * include/bits/ios_base.h: Same. * include/bits/stl_deque.h: Same. * include/bits/postypes.h: Same. * include/bits/stl_multiset.h: Same. * include/bits/stl_algo.h: Same. * include/bits/stl_iterator.h: Same. * include/bits/stl_tempbuf.h: Same. * include/bits/stl_construct.h: Same. * include/bits/stl_relops.h: Same. * include/tr1/tuple: Same. * include/backward/auto_ptr.h: Same. * testsuite/23_containers/vector/requirements/dr438/assign_neg.cc: Fixups for line number changes. * testsuite/23_containers/vector/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/vector/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/vector/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/assign_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/deque/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/ constructor_1_neg.cc: Same. * testsuite/23_containers/list/requirements/dr438/ constructor_2_neg.cc: Same. * testsuite/20_util/auto_ptr/assign_neg.cc: Same. * aclocal.m4: Regenerate. * config.h.in: Regenerate. * configure: Regenerate. * Makefile.in: Regenerate. * src/Makefile.in: Regenerate. * po/Makefile.in: Regenerate. * libmath/Makefile.in: Regenerate. * include/Makefile.in: Regenerate. * libsupc++/Makefile.in: Regenerate. * testsuite/Makefile.in: Regenerate. * scripts/make_graphs.py: Correct paths for new layout. 2008-01-17 Benjamin Kosnik <bkoz@redhat.com> * acinclude.m4 (AC_LC_MESSAGES): Remove serial. * linkage.m4 (AC_REPLACE_MATHFUNCS): Same. * configure: Regenerate. * aclocal.m4: Regenerate. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@131625 138bc75d-0d04-0410-961f-82ee72b054a4
author: bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4> 2008-01-18 08:16:51 +0000
committer: bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4> 2008-01-18 08:16:51 +0000
commit: 0aeadebf36eab6d537b67b38c5dcacf648f2f69f (patch)
tree: 0fd3dc60ac26e2ec9502783b72d38867bcb418d8 /libstdc++-v3/doc/html/24_iterators/howto.html
parent: 9e61be0719e3f9d3bda483eaaf71ee67f02e81ae (diff)
download: ppe42-gcc-0aeadebf36eab6d537b67b38c5dcacf648f2f69f.tar.gz
ppe42-gcc-0aeadebf36eab6d537b67b38c5dcacf648f2f69f.zip
1 files changed, 200 insertions, 0 deletions
diff --git a/libstdc++-v3/doc/html/24_iterators/howto.html b/libstdc++-v3/doc/html/24_iterators/howto.html
new file mode 100644
index 00000000000..7c2f106ac31
--- /dev/null
+++ b/libstdc++-v3/doc/html/24_iterators/howto.html
@@ -0,0 +1,200 @@
+<?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++ 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++ 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 &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>
author	bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>	2008-01-18 08:16:51 +0000
committer	bkoz <bkoz@138bc75d-0d04-0410-961f-82ee72b054a4>	2008-01-18 08:16:51 +0000
commit	0aeadebf36eab6d537b67b38c5dcacf648f2f69f (patch)
tree	0fd3dc60ac26e2ec9502783b72d38867bcb418d8 /libstdc++-v3/doc/html/24_iterators/howto.html
parent	9e61be0719e3f9d3bda483eaaf71ee67f02e81ae (diff)
download	ppe42-gcc-0aeadebf36eab6d537b67b38c5dcacf648f2f69f.tar.gz ppe42-gcc-0aeadebf36eab6d537b67b38c5dcacf648f2f69f.zip