2 <!DOCTYPE part PUBLIC "-//OASIS//DTD DocBook XML V4.5//EN"
3 "http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
6 <part id="manual.algorithms" xreflabel="Algorithms">
7 <?dbhtml filename="algorithms.html"?>
23 <title>Algorithms</title>
28 The neatest accomplishment of the algorithms chapter is that all the
29 work is done via iterators, not containers directly. This means two
35 Anything that behaves like an iterator can be used in one of
36 these algorithms. Raw pointers make great candidates, thus
37 built-in arrays are fine containers, as well as your own iterators.
42 The algorithms do not (and cannot) affect the container as a
43 whole; only the things between the two iterator endpoints. If
44 you pass a range of iterators only enclosing the middle third of
45 a container, then anything outside that range is inviolate.
50 Even strings can be fed through the algorithms here, although the
51 string class has specialized versions of many of these functions
52 (for example, <code>string::find()</code>). Most of the examples
53 on this page will use simple arrays of integers as a playground
54 for algorithms, just to keep things simple. The use of
55 <emphasis>N</emphasis> as a size in the examples is to keep
56 things easy to read but probably won't be valid code. You can
57 use wrappers such as those described in the <ulink
58 url="../23_containers/howto.html">containers chapter</ulink> to
59 keep real code readable.
62 The single thing that trips people up the most is the definition
63 of <emphasis>range</emphasis> used with iterators; the famous
64 "past-the-end" rule that everybody loves to hate. The
65 <ulink url="../24_iterators/howto.html#2">iterators
66 chapter</ulink> of this document has a complete explanation of
67 this simple rule that seems to cause so much confusion. Once you
68 get <emphasis>range</emphasis> into your head (it's not that
69 hard, honest!), then the algorithms are a cakewalk.
73 <!-- Chapter 01 : Non Modifying -->
75 <!-- Chapter 02 : Mutating -->
76 <chapter id="manual.algorithms.mutating" xreflabel="Mutating">
77 <title>Mutating</title>
79 <sect1 id="algorithms.mutating.swap" xreflabel="swap">
80 <title><function>swap</function></title>
82 <sect2 id="algorithms.swap.specializations" xreflabel="Specializations">
83 <title>Specializations</title>
85 <para>If you call <code> std::swap(x,y); </code> where x and y are standard
86 containers, then the call will automatically be replaced by a call to
87 <code> x.swap(y); </code> instead.
89 <para>This allows member functions of each container class to take over, and
90 containers' swap functions should have O(1) complexity according to
91 the standard. (And while "should" allows implementations to
92 behave otherwise and remain compliant, this implementation does in
93 fact use constant-time swaps.) This should not be surprising, since
94 for two containers of the same type to swap contents, only some
95 internal pointers to storage need to be exchanged.
102 <!-- Chapter 03 : Sorting -->