14fee23f9Smrg<?xml version="1.0" encoding="UTF-8" standalone="no"?> 2*d79abf08Smrg<!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>Chapter 11. 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="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><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 11. 34fee23f9Smrg Algorithms 44fee23f9Smrg 548fb7bfaSmrg</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="iterators.html">Prev</a> </td><th width="60%" align="center">Part II. 648fb7bfaSmrg Standard Contents 748fb7bfaSmrg </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>Chapter 11. 84fee23f9Smrg Algorithms 94d5abbe8Smrg <a id="id-1.3.4.9.1.1.1" class="indexterm"></a> 1048fb7bfaSmrg</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> 1148fb7bfaSmrg The neatest accomplishment of the algorithms section is that all the 1248fb7bfaSmrg work is done via iterators, not containers directly. This means two 1348fb7bfaSmrg important things: 1448fb7bfaSmrg</p><div class="orderedlist"><ol class="orderedlist" type="1"><li class="listitem"><p> 1548fb7bfaSmrg Anything that behaves like an iterator can be used in one of 1648fb7bfaSmrg these algorithms. Raw pointers make great candidates, thus 1748fb7bfaSmrg built-in arrays are fine containers, as well as your own 1848fb7bfaSmrg iterators. 1948fb7bfaSmrg </p></li><li class="listitem"><p> 2048fb7bfaSmrg The algorithms do not (and cannot) affect the container as a 2148fb7bfaSmrg whole; only the things between the two iterator endpoints. If 2248fb7bfaSmrg you pass a range of iterators only enclosing the middle third of 2348fb7bfaSmrg a container, then anything outside that range is inviolate. 2448fb7bfaSmrg </p></li></ol></div><p> 2548fb7bfaSmrg Even strings can be fed through the algorithms here, although the 2648fb7bfaSmrg string class has specialized versions of many of these functions 2748fb7bfaSmrg (for example, <code class="code">string::find()</code>). Most of the examples 2848fb7bfaSmrg on this page will use simple arrays of integers as a playground 2948fb7bfaSmrg for algorithms, just to keep things simple. The use of 3048fb7bfaSmrg <span class="emphasis"><em>N</em></span> as a size in the examples is to keep things 3148fb7bfaSmrg easy to read but probably won't be valid code. You can use wrappers 3248fb7bfaSmrg such as those described in 3348fb7bfaSmrg the <a class="link" href="containers.html" title="Chapter 9. Containers">containers section</a> to keep 3448fb7bfaSmrg real code readable. 3548fb7bfaSmrg</p><p> 3648fb7bfaSmrg The single thing that trips people up the most is the definition 3748fb7bfaSmrg of <span class="emphasis"><em>range</em></span> used with iterators; the famous 3848fb7bfaSmrg "past-the-end" rule that everybody loves to hate. The 3948fb7bfaSmrg <a class="link" href="iterators.html" title="Chapter 10. Iterators">iterators section</a> of this 4048fb7bfaSmrg document has a complete explanation of this simple rule that seems 4148fb7bfaSmrg to cause so much confusion. Once you 4248fb7bfaSmrg get <span class="emphasis"><em>range</em></span> into your head (it's not that hard, 4348fb7bfaSmrg honest!), then the algorithms are a cakewalk. 4448fb7bfaSmrg</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 4548fb7bfaSmrg containers, then the call will automatically be replaced by a call to 4648fb7bfaSmrg <code class="code"> x.swap(y); </code> instead. 4748fb7bfaSmrg </p><p>This allows member functions of each container class to take over, and 4848fb7bfaSmrg containers' swap functions should have O(1) complexity according to 4948fb7bfaSmrg the standard. (And while "should" allows implementations to 5048fb7bfaSmrg behave otherwise and remain compliant, this implementation does in 5148fb7bfaSmrg fact use constant-time swaps.) This should not be surprising, since 5248fb7bfaSmrg for two containers of the same type to swap contents, only some 5348fb7bfaSmrg internal pointers to storage need to be exchanged. 5448fb7bfaSmrg </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">Chapter 10. 5548fb7bfaSmrg Iterators 5648fb7bfaSmrg 5748fb7bfaSmrg </td><td width="20%" align="center"><a accesskey="h" href="../index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 12. 5848fb7bfaSmrg Numerics 5948fb7bfaSmrg 6048fb7bfaSmrg</td></tr></table></div></body></html>