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