libstdc++-v3/docs/html/25_algorithms/howto.html

   1 <?xml version="1.0" encoding="ISO-8859-1"?>
   2 <!DOCTYPE html
   3           PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
   4           "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   5
   6 <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
   7 <head>
   8    <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1" />
   9    <meta name="AUTHOR" content="pme@gcc.gnu.org (Phil Edwards)" />
  10    <meta name="KEYWORDS" content="HOWTO, libstdc++, GCC, g++, libg++, STL" />
  11    <meta name="DESCRIPTION" content="HOWTO for the libstdc++ chapter 25." />
  12    <meta name="GENERATOR" content="vi and eight fingers" />
  13    <title>libstdc++-v3 HOWTO:  Chapter 25: Algorithms</title>
  14 <link rel="StyleSheet" href="../lib3styles.css" type="text/css" />
  15 <link rel="Start" href="../documentation.html" type="text/html"
  16   title="GNU C++ Standard Library" />
  17 <link rel="Prev" href="../24_iterators/howto.html" type="text/html"
  18   title="Iterators" />
  19 <link rel="Next" href="../26_numerics/howto.html" type="text/html"
  20   title="Numerics" />
  21 <link rel="Copyright" href="../17_intro/license.html" type="text/html" />
  22 <link rel="Help" href="../faq/index.html" type="text/html" title="F.A.Q." />
  23 </head>
  24 <body>
  25
  26 <h1 class="centered"><a name="top">Chapter 25:  Algorithms</a></h1>
  27
  28 <p>Chapter 25 deals with the generalized subroutines for automatically
  29    transforming lemmings into gold.
  30 </p>
  31
  32
  33 <!-- ####################################################### -->
  34 <hr />
  35 <h1>Contents</h1>
  36 <ul>
  37    <li><a href="#1">Prerequisites</a></li>
  38    <li><a href="#2">Special <code>swap</code>s</a></li>
  39 </ul>
  40
  41 <hr />
  42
  43 <!-- ####################################################### -->
  44
  45 <h2><a name="1">Prerequisites</a></h2>
  46    <p>The neatest accomplishment of the algorithms chapter is that all the
  47       work is done via iterators, not containers directly.  This means two
  48       important things:
  49    </p>
  50    <ol>
  51       <li>Anything that behaves like an iterator can be used in one of
  52           these algorithms.  Raw pointers make great candidates, thus
  53           built-in arrays are fine containers, as well as your own iterators.
  54       </li>
  55       <li>The algorithms do not (and cannot) affect the container as a
  56           whole; only the things between the two iterator endpoints.  If
  57           you pass a range of iterators only enclosing the middle third of
  58           a container, then anything outside that range is inviolate.
  59       </li>
  60    </ol>
  61    <p>Even strings can be fed through the algorithms here, although the
  62       string class has specialized versions of many of these functions (for
  63       example, <code>string::find()</code>).  Most of the examples on this
  64       page will use simple arrays of integers as a playground for
  65       algorithms, just to keep things simple.
  66       <a name="Nsize">The use of <strong>N</strong></a> as a size in the
  67       examples is to keep things easy to read but probably won't be valid
  68       code.  You can use wrappers such as those described in the
  69       <a href="../23_containers/howto.html">containers chapter</a> to keep
  70       real code readable.
  71    </p>
  72    <p>The single thing that trips people up the most is the definition of
  73       <em>range</em> used with iterators; the famous
  74       &quot;past-the-end&quot; rule that everybody loves to hate.  The
  75       <a href="../24_iterators/howto.html#2">iterators chapter</a> of this
  76       document has a complete explanation of this simple rule that seems to
  77       cause so much confusion.  Once you get <em>range</em> into your head
  78       (it's not that hard, honest!), then the algorithms are a cakewalk.
  79    </p>
  80    <p>Return <a href="#top">to top of page</a> or
  81       <a href="../faq/index.html">to the FAQ</a>.
  82    </p>
  83
  84 <hr />
  85 <h2><a name="2">Special <code>swap</code>s</a></h2>
  86    <p>If you call <code> std::swap(x,y); </code> where x and y are standard
  87       containers, then the call will automatically be replaced by a call to
  88       <code> x.swap(y); </code> instead.
  89    </p>
  90    <p>This allows member functions of each container class to take over, and
  91       containers' swap functions should have O(1) complexity according to
  92       the standard.  (And while &quot;should&quot; allows implementations to
  93       behave otherwise and remain compliant, this implementation does in
  94       fact use constant-time swaps.)  This should not be surprising, since
  95       for two containers of the same type to swap contents, only some
  96       internal pointers to storage need to be exchanged.
  97    </p>
  98    <p>Return <a href="#top">to top of page</a> or
  99       <a href="../faq/index.html">to the FAQ</a>.
 100    </p>
 101
 102
 103
 104
 105 <!-- ####################################################### -->
 106
 107 <hr />
 108 <p class="fineprint"><em>
 109 See <a href="../17_intro/license.html">license.html</a> for copying conditions.
 110 Comments and suggestions are welcome, and may be sent to
 111 <a href="mailto:libstdc++@gcc.gnu.org">the libstdc++ mailing list</a>.
 112 </em></p>
 113
 114
 115 </body>
 116 </html>