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>
101See <a href="../17_intro/license.html">license.html</a> for copying conditions.
102Comments 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>
109