|
|
|
|
"http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
|
"http://www.oasis-open.org/docbook/xml/4.5/docbookx.dtd"
|
[ ]>
|
[ ]>
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
ISO C++
|
ISO C++
|
|
|
|
|
library
|
library
|
|
|
|
|
algorithm
|
algorithm
|
|
|
|
|
|
|
|
|
</code></pre></td>
<td class="diff"><pre><code><title></code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code> Algorithms</code></pre></td>
<td class="diff"><pre><code> Algorithms</code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code> <indexterm><primary>Algorithms</primary></indexterm></code></pre></td>
<td class="diff"><pre><code> <indexterm><primary>Algorithms</primary></indexterm></code></pre></td>
</tr>
<tr class="diffcode">
<td class="diff"><pre><code>
|
|
|
|
|
|
The neatest accomplishment of the algorithms sect1 is that all the
|
The neatest accomplishment of the algorithms sect1 is that all the
|
work is done via iterators, not containers directly. This means two
|
work is done via iterators, not containers directly. This means two
|
important things:
|
important things:
|
|
|
|
|
|
|
|
|
Anything that behaves like an iterator can be used in one of
|
Anything that behaves like an iterator can be used in one of
|
these algorithms. Raw pointers make great candidates, thus
|
these algorithms. Raw pointers make great candidates, thus
|
built-in arrays are fine containers, as well as your own
|
built-in arrays are fine containers, as well as your own
|
iterators.
|
iterators.
|
|
|
|
|
|
|
|
|
The algorithms do not (and cannot) affect the container as a
|
The algorithms do not (and cannot) affect the container as a
|
whole; only the things between the two iterator endpoints. If
|
whole; only the things between the two iterator endpoints. If
|
you pass a range of iterators only enclosing the middle third of
|
you pass a range of iterators only enclosing the middle third of
|
a container, then anything outside that range is inviolate.
|
a container, then anything outside that range is inviolate.
|
|
|
|
|
|
|
|
|
Even strings can be fed through the algorithms here, although the
|
Even strings can be fed through the algorithms here, although the
|
string class has specialized versions of many of these functions
|
string class has specialized versions of many of these functions
|
(for example, string::find()). Most of the examples
|
(for example, string::find()). Most of the examples
|
on this page will use simple arrays of integers as a playground
|
on this page will use simple arrays of integers as a playground
|
for algorithms, just to keep things simple. The use of
|
for algorithms, just to keep things simple. The use of
|
N as a size in the examples is to keep things
|
N as a size in the examples is to keep things
|
easy to read but probably won't be valid code. You can use wrappers
|
easy to read but probably won't be valid code. You can use wrappers
|
such as those described in
|
such as those described in
|
the containers sect1 to keep
|
the containers sect1 to keep
|
real code readable.
|
real code readable.
|
|
|
|
|
The single thing that trips people up the most is the definition
|
The single thing that trips people up the most is the definition
|
of range used with iterators; the famous
|
of range used with iterators; the famous
|
"past-the-end" rule that everybody loves to hate. The
|
"past-the-end" rule that everybody loves to hate. The
|
iterators sect1 of this
|
iterators sect1 of this
|
document has a complete explanation of this simple rule that seems
|
document has a complete explanation of this simple rule that seems
|
to cause so much confusion. Once you
|
to cause so much confusion. Once you
|
get range into your head (it's not that hard,
|
get range into your head (it's not that hard,
|
honest!), then the algorithms are a cakewalk.
|
honest!), then the algorithms are a cakewalk.
|
|
|
|
|
|
|
|
|
|
|
|
|
Mutating
|
Mutating
|
|
|
|
|
<function>swap</function>
|
<function>swap</function>
|
|
|
|
|
Specializations
|
Specializations
|
|
|
If you call std::swap(x,y); where x and y are standard
|
If you call std::swap(x,y); where x and y are standard
|
containers, then the call will automatically be replaced by a call to
|
containers, then the call will automatically be replaced by a call to
|
x.swap(y); instead.
|
x.swap(y); instead.
|
|
|
This allows member functions of each container class to take over, and
|
This allows member functions of each container class to take over, and
|
containers' swap functions should have O(1) complexity according to
|
containers' swap functions should have O(1) complexity according to
|
the standard. (And while "should" allows implementations to
|
the standard. (And while "should" allows implementations to
|
behave otherwise and remain compliant, this implementation does in
|
behave otherwise and remain compliant, this implementation does in
|
fact use constant-time swaps.) This should not be surprising, since
|
fact use constant-time swaps.) This should not be surprising, since
|
for two containers of the same type to swap contents, only some
|
for two containers of the same type to swap contents, only some
|
internal pointers to storage need to be exchanged.
|
internal pointers to storage need to be exchanged.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
