libstdc++-v3/doc/html/manual/algorithms.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8"><title>Chapter 11.  Algorithms</title><meta name="generator" content="DocBook XSL-NS Stylesheets V1.76.1"><meta name="keywords" content="
   2       ISO C++
   3     ,
   4       library
   5     ,
   6       algorithm
   7     "><meta name="keywords" content="
   8       ISO C++
   9     ,
  10       runtime
  11     ,
  12       library
  13     "><link rel="home" href="../index.html" title="The GNU C++ Library"><link rel="up" href="bk01pt02.html" title="Part II.  Standard Contents"><link rel="prev" href="iterators.html" title="Chapter 10.  Iterators"><link rel="next" href="numerics.html" title="Chapter 12.  Numerics"></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 11.
  14   Algorithms
  15
  16 </th></tr><tr><td width="20%" align="left"><a accesskey="p" href="iterators.html">Prev</a> </td><th width="60%" align="center">Part II.
  17     Standard Contents
  18   </th><td width="20%" align="right"> <a accesskey="n" href="numerics.html">Next</a></td></tr></table><hr></div><div class="chapter" title="Chapter 11.  Algorithms"><div class="titlepage"><div><div><h2 class="title"><a name="std.algorithms"></a>Chapter 11.
  19   Algorithms
  20   <a class="indexterm" name="id628522"></a>
  21 </h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="algorithms.html#std.algorithms.mutating">Mutating</a></span></dt><dd><dl><dt><span class="section"><a href="algorithms.html#algorithms.mutating.swap"><code class="function">swap</code></a></span></dt><dd><dl><dt><span class="section"><a href="algorithms.html#algorithms.swap.specializations">Specializations</a></span></dt></dl></dd></dl></dd></dl></div><p>
  22   The neatest accomplishment of the algorithms section is that all the
  23   work is done via iterators, not containers directly.  This means two
  24   important things:
  25 </p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p>
  26       Anything that behaves like an iterator can be used in one of
  27       these algorithms.  Raw pointers make great candidates, thus
  28       built-in arrays are fine containers, as well as your own
  29       iterators.
  30     </p></li><li class="listitem"><p>
  31       The algorithms do not (and cannot) affect the container as a
  32       whole; only the things between the two iterator endpoints.  If
  33       you pass a range of iterators only enclosing the middle third of
  34       a container, then anything outside that range is inviolate.
  35     </p></li></ol></div><p>
  36   Even strings can be fed through the algorithms here, although the
  37   string class has specialized versions of many of these functions
  38   (for example, <code class="code">string::find()</code>).  Most of the examples
  39   on this page will use simple arrays of integers as a playground
  40   for algorithms, just to keep things simple.  The use of
  41   <span class="emphasis"><em>N</em></span> as a size in the examples is to keep things
  42   easy to read but probably won't be valid code.  You can use wrappers
  43   such as those described in
  44   the <a class="link" href="containers.html" title="Chapter 9.  Containers">containers section</a> to keep
  45   real code readable.
  46 </p><p>
  47   The single thing that trips people up the most is the definition
  48   of <span class="emphasis"><em>range</em></span> used with iterators; the famous
  49   "past-the-end" rule that everybody loves to hate.  The
  50   <a class="link" href="iterators.html" title="Chapter 10.  Iterators">iterators section</a> of this
  51     document has a complete explanation of this simple rule that seems
  52     to cause so much confusion.  Once you
  53     get <span class="emphasis"><em>range</em></span> into your head (it's not that hard,
  54     honest!), then the algorithms are a cakewalk.
  55 </p><div class="section" title="Mutating"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="std.algorithms.mutating"></a>Mutating</h2></div></div></div><div class="section" title="swap"><div class="titlepage"><div><div><h3 class="title"><a name="algorithms.mutating.swap"></a><code class="function">swap</code></h3></div></div></div><div class="section" title="Specializations"><div class="titlepage"><div><div><h4 class="title"><a name="algorithms.swap.specializations"></a>Specializations</h4></div></div></div><p>If you call <code class="code"> std::swap(x,y); </code> where x and y are standard
  56       containers, then the call will automatically be replaced by a call to
  57       <code class="code"> x.swap(y); </code> instead.
  58    </p><p>This allows member functions of each container class to take over, and
  59       containers' swap functions should have O(1) complexity according to
  60       the standard.  (And while "should" allows implementations to
  61       behave otherwise and remain compliant, this implementation does in
  62       fact use constant-time swaps.)  This should not be surprising, since
  63       for two containers of the same type to swap contents, only some
  64       internal pointers to storage need to be exchanged.
  65    </p></div></div></div></div><div class="navfooter"><hr><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="iterators.html">Prev</a> </td><td width="20%" align="center"><a accesskey="u" href="bk01pt02.html">Up</a></td><td width="40%" align="right"> <a accesskey="n" href="numerics.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 10.
  66   Iterators
  67
  68  </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 12.
  69   Numerics
  70
  71 </td></tr></table></div></body></html>