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 "past-the-end" 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 "should" 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> 109See <a href="../17_intro/license.html">license.html</a> for copying conditions. 110Comments 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> 117