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