libs/range/doc/html/range/reference/algorithms/introduction.html

   1 <html>
   2 <head>
   3 <meta http-equiv="Content-Type" content="text/html; charset=US-ASCII">
   4 <title>Introduction and motivation</title>
   5 <link rel="stylesheet" href="../../../../../../../doc/src/boostbook.css" type="text/css">
   6 <meta name="generator" content="DocBook XSL Stylesheets V1.78.1">
   7 <link rel="home" href="../../../index.html" title="Chapter&#160;1.&#160;Range 2.0">
   8 <link rel="up" href="../algorithms.html" title="Range Algorithms">
   9 <link rel="prev" href="../algorithms.html" title="Range Algorithms">
  10 <link rel="next" href="mutating.html" title="Mutating algorithms">
  11 </head>
  12 <body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
  13 <table cellpadding="2" width="100%"><tr>
  14 <td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../../../boost.png"></td>
  15 <td align="center"><a href="../../../../../../../index.html">Home</a></td>
  16 <td align="center"><a href="../../../../../../../libs/libraries.htm">Libraries</a></td>
  17 <td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
  18 <td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
  19 <td align="center"><a href="../../../../../../../more/index.htm">More</a></td>
  20 </tr></table>
  21 <hr>
  22 <div class="spirit-nav">
  23 <a accesskey="p" href="../algorithms.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../algorithms.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="mutating.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
  24 </div>
  25 <div class="section">
  26 <div class="titlepage"><div><div><h4 class="title">
  27 <a name="range.reference.algorithms.introduction"></a><a class="link" href="introduction.html" title="Introduction and motivation">Introduction
  28         and motivation</a>
  29 </h4></div></div></div>
  30 <p>
  31           In its most simple form a <span class="bold"><strong>Range Algorithm</strong></span>
  32           (or range-based algorithm) is simply an iterator-based algorithm where
  33           the <span class="emphasis"><em>two</em></span> iterator arguments have been replaced by
  34           <span class="emphasis"><em>one</em></span> range argument. For example, we may write
  35         </p>
  36 <p>
  37 </p>
  38 <pre class="programlisting"><span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">range</span><span class="special">/</span><span class="identifier">algorithm</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  39 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
  40
  41 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">vec</span> <span class="special">=</span> <span class="special">...;</span>
  42 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">vec</span><span class="special">);</span>
  43 </pre>
  44 <p>
  45         </p>
  46 <p>
  47           instead of
  48         </p>
  49 <p>
  50 </p>
  51 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">vec</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
  52 </pre>
  53 <p>
  54         </p>
  55 <p>
  56           However, the return type of range algorithms is almost always different
  57           from that of existing iterator-based algorithms.
  58         </p>
  59 <p>
  60           One group of algorithms, like <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">()</span></code>, will simply return the same range so
  61           that we can continue to pass the range around and/or further modify it.
  62           Because of this we may write
  63 </p>
  64 <pre class="programlisting"><span class="identifier">boost</span><span class="special">:</span><span class="identifier">unique</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">vec</span><span class="special">));</span>
  65 </pre>
  66 <p>
  67           to first sort the range and then run <code class="computeroutput"><span class="identifier">unique</span><span class="special">()</span></code> on the sorted range.
  68         </p>
  69 <p>
  70           Algorithms like <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">()</span></code>
  71           fall into another group of algorithms that return (potentially) narrowed
  72           views of the original range. By default <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">(</span><span class="identifier">rng</span><span class="special">)</span></code> returns the range <code class="computeroutput"><span class="special">[</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">rng</span><span class="special">),</span> <span class="identifier">found</span><span class="special">)</span></code>
  73           where <code class="computeroutput"><span class="identifier">found</span></code> denotes the
  74           iterator returned by <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">rng</span><span class="special">),</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">rng</span><span class="special">))</span></code>
  75         </p>
  76 <p>
  77           Therefore exactly the unique values can be copied by writing
  78 </p>
  79 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">vec</span><span class="special">)),</span>
  80             <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream_iterator</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;(</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">));</span>
  81 </pre>
  82 <p>
  83         </p>
  84 <p>
  85           Algorithms like <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span></code> usually return the range: <code class="computeroutput"><span class="special">[</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">rng</span><span class="special">),</span> <span class="identifier">found</span><span class="special">)</span></code>. However, this behaviour may be changed
  86           by supplying a <code class="computeroutput"><span class="identifier">range_return_value</span></code>
  87           as a template parameter to the algorithm:
  88         </p>
  89 <div class="informaltable"><table class="table">
  90 <colgroup>
  91 <col>
  92 <col>
  93 </colgroup>
  94 <thead><tr>
  95 <th>
  96                   <p>
  97                     Expression
  98                   </p>
  99                 </th>
 100 <th>
 101                   <p>
 102                     Return
 103                   </p>
 104                 </th>
 105 </tr></thead>
 106 <tbody>
 107 <tr>
 108 <td>
 109                   <p>
 110                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_found</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 111                   </p>
 112                 </td>
 113 <td>
 114                   <p>
 115                     returns a single iterator like <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">unique</span></code>
 116                   </p>
 117                 </td>
 118 </tr>
 119 <tr>
 120 <td>
 121                   <p>
 122                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_begin_found</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 123                   </p>
 124                 </td>
 125 <td>
 126                   <p>
 127                     returns the range <code class="computeroutput"><span class="special">[</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">rng</span><span class="special">),</span>
 128                     <span class="identifier">found</span><span class="special">)</span></code>
 129                     (this is the default)
 130                   </p>
 131                 </td>
 132 </tr>
 133 <tr>
 134 <td>
 135                   <p>
 136                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_begin_next</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 137                   </p>
 138                 </td>
 139 <td>
 140                   <p>
 141                     returns the range <code class="computeroutput"><span class="special">[</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">begin</span><span class="special">(</span><span class="identifier">rng</span><span class="special">),</span>
 142                     <span class="identifier">boost</span><span class="special">::</span><span class="identifier">next</span><span class="special">(</span><span class="identifier">found</span><span class="special">))</span></code>
 143                   </p>
 144                 </td>
 145 </tr>
 146 <tr>
 147 <td>
 148                   <p>
 149                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_found_end</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 150                   </p>
 151                 </td>
 152 <td>
 153                   <p>
 154                     returns the range <code class="computeroutput"><span class="special">[</span><span class="identifier">found</span><span class="special">,</span>
 155                     <span class="identifier">boost</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">rng</span><span class="special">))</span></code>
 156                   </p>
 157                 </td>
 158 </tr>
 159 <tr>
 160 <td>
 161                   <p>
 162                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_next_end</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 163                   </p>
 164                 </td>
 165 <td>
 166                   <p>
 167                     returns the range <code class="computeroutput"><span class="special">[</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">next</span><span class="special">(</span><span class="identifier">found</span><span class="special">),</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">end</span><span class="special">(</span><span class="identifier">rng</span><span class="special">))</span></code>
 168                   </p>
 169                 </td>
 170 </tr>
 171 <tr>
 172 <td>
 173                   <p>
 174                     <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_begin_end</span><span class="special">&gt;(</span><span class="identifier">rng</span><span class="special">)</span></code>
 175                   </p>
 176                 </td>
 177 <td>
 178                   <p>
 179                     returns the entire original range.
 180                   </p>
 181                 </td>
 182 </tr>
 183 </tbody>
 184 </table></div>
 185 <p>
 186           This functionality has the following advantages:
 187         </p>
 188 <div class="orderedlist"><ol class="orderedlist" type="1">
 189 <li class="listitem">
 190               it allows for <span class="emphasis"><em><span class="bold"><strong>seamless functional-style
 191               programming</strong></span></em></span> where you do not need to use named
 192               local variables to store intermediate results
 193             </li>
 194 <li class="listitem">
 195               it is very <span class="emphasis"><em><span class="bold"><strong>safe</strong></span></em></span>
 196               because the algorithm can verify out-of-bounds conditions and handle
 197               tricky conditions that lead to empty ranges
 198             </li>
 199 </ol></div>
 200 <p>
 201           For example, consider how easy we may erase the duplicates in a sorted
 202           container:
 203         </p>
 204 <p>
 205 </p>
 206 <pre class="programlisting"><span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;</span> <span class="identifier">vec</span> <span class="special">=</span> <span class="special">...;</span>
 207 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">vec</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_found_end</span><span class="special">&gt;(</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">sort</span><span class="special">(</span><span class="identifier">vec</span><span class="special">)));</span>
 208 </pre>
 209 <p>
 210         </p>
 211 <p>
 212           Notice the use of <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_found_end</span></code>.
 213           What if we wanted to erase all the duplicates except one of them? In old-fashined
 214           STL-programming we might write
 215         </p>
 216 <p>
 217 </p>
 218 <pre class="programlisting"><span class="comment">// assume 'vec' is already sorted</span>
 219 <span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special">&lt;</span><span class="keyword">int</span><span class="special">&gt;::</span><span class="identifier">iterator</span> <span class="identifier">i</span> <span class="special">=</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">unique</span><span class="special">(</span><span class="identifier">vec</span><span class="special">.</span><span class="identifier">begin</span><span class="special">(),</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
 220
 221 <span class="comment">// remember this check or you get into problems</span>
 222 <span class="keyword">if</span> <span class="special">(</span><span class="identifier">i</span> <span class="special">!=</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">())</span>
 223     <span class="special">++</span><span class="identifier">i</span><span class="special">;</span>
 224
 225 <span class="identifier">vec</span><span class="special">.</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">i</span><span class="special">,</span> <span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">());</span>
 226 </pre>
 227 <p>
 228         </p>
 229 <p>
 230           The same task may be accomplished simply with
 231 </p>
 232 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">erase</span><span class="special">(</span><span class="identifier">vec</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">unique</span><span class="special">&lt;</span><span class="identifier">boost</span><span class="special">::</span><span class="identifier">return_next_end</span><span class="special">&gt;(</span><span class="identifier">vec</span><span class="special">));</span>
 233 </pre>
 234 <p>
 235           and there is no need to worry about generating an invalid range. Furthermore,
 236           if the container is complex, calling <code class="computeroutput"><span class="identifier">vec</span><span class="special">.</span><span class="identifier">end</span><span class="special">()</span></code> several times will be more expensive
 237           than using a range algorithm.
 238         </p>
 239 </div>
 240 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 241 <td align="left"></td>
 242 <td align="right"><div class="copyright-footer">Copyright &#169; 2003-2010 Thorsten Ottosen,
 243       Neil Groves<p>
 244         Distributed under the Boost Software License, Version 1.0. (See accompanying
 245         file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
 246       </p>
 247 </div></td>
 248 </tr></table>
 249 <hr>
 250 <div class="spirit-nav">
 251 <a accesskey="p" href="../algorithms.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../algorithms.html"><img src="../../../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../../../index.html"><img src="../../../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="mutating.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
 252 </div>
 253 </body>
 254 </html>