libs/range/doc/html/range/reference/adaptors/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="../adaptors.html" title="Range Adaptors">
   9 <link rel="prev" href="../adaptors.html" title="Range Adaptors">
  10 <link rel="next" href="general_requirements.html" title="General Requirements">
  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="../adaptors.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../adaptors.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="general_requirements.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.adaptors.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           A <span class="bold"><strong>Range Adaptor</strong></span> is a class that wraps
  32           an existing Range to provide a new Range with different behaviour. Since
  33           the behaviour of Ranges is determined by their associated iterators, a
  34           Range Adaptor simply wraps the underlying iterators with new special iterators.
  35           In this example
  36         </p>
  37 <p>
  38 </p>
  39 <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">adaptors</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">&gt;</span>
  40 <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>
  41 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">iostream</span><span class="special">&gt;</span>
  42 <span class="preprocessor">#include</span> <span class="special">&lt;</span><span class="identifier">vector</span><span class="special">&gt;</span>
  43
  44 <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>
  45 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy</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">adaptors</span><span class="special">::</span><span class="identifier">reversed</span><span class="special">,</span>
  46              <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> <span class="special">);</span>
  47 </pre>
  48 <p>
  49         </p>
  50 <p>
  51           the iterators from <code class="computeroutput"><span class="identifier">vec</span></code>
  52           are wrapped <code class="computeroutput"><span class="identifier">reverse_iterator</span></code>s.
  53           The type of the underlying Range Adapter is not documented because you
  54           do not need to know it. All that is relevant is that the expression
  55         </p>
  56 <p>
  57 </p>
  58 <pre class="programlisting"><span class="identifier">vec</span> <span class="special">|</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">reversed</span>
  59 </pre>
  60 <p>
  61         </p>
  62 <p>
  63           returns a Range Adaptor where the iterator type is now the iterator type
  64           of the range <code class="computeroutput"><span class="identifier">vec</span></code> wrapped
  65           in <code class="computeroutput"><span class="identifier">reverse_iterator</span></code>. The
  66           expression <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">reversed</span></code> is called an <span class="bold"><strong>Adaptor
  67           Generator</strong></span>.
  68         </p>
  69 <p>
  70           There are two ways of constructing a range adaptor. The first is by using
  71           <code class="computeroutput"><span class="keyword">operator</span><span class="special">|()</span></code>.
  72           This is my preferred technique, however while discussing range adaptors
  73           with others it became clear that some users of the library strongly prefer
  74           a more familiar function syntax, so equivalent functions of the present
  75           tense form have been added as an alternative syntax. The equivalent to
  76           <code class="computeroutput"><span class="identifier">rng</span> <span class="special">|</span>
  77           <span class="identifier">reversed</span></code> is <code class="computeroutput"><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">reverse</span><span class="special">(</span><span class="identifier">rng</span><span class="special">)</span></code> for example.
  78         </p>
  79 <p>
  80           Why do I prefer the <code class="computeroutput"><span class="keyword">operator</span><span class="special">|</span></code> syntax? The answer is readability:
  81         </p>
  82 <p>
  83 </p>
  84 <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>
  85 <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">adaptors</span><span class="special">::</span><span class="identifier">reverse</span><span class="special">(</span><span class="identifier">vec</span><span class="special">),</span>
  86              <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> <span class="special">);</span>
  87 </pre>
  88 <p>
  89         </p>
  90 <p>
  91           This might not look so bad, but when we apply several adaptors, it becomes
  92           much worse. Just compare
  93         </p>
  94 <p>
  95 </p>
  96 <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>
  97 <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">adaptors</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">adaptors</span><span class="special">::</span><span class="identifier">reverse</span><span class="special">(</span> <span class="identifier">vec</span> <span class="special">)</span> <span class="special">),</span>
  98              <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> <span class="special">);</span>
  99 </pre>
 100 <p>
 101         </p>
 102 <p>
 103           to
 104         </p>
 105 <p>
 106 </p>
 107 <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>
 108 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy</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">adaptors</span><span class="special">::</span><span class="identifier">reversed</span>
 109                  <span class="special">|</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">uniqued</span><span class="special">,</span>
 110              <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> <span class="special">);</span>
 111 </pre>
 112 <p>
 113         </p>
 114 <p>
 115           Furthermore, some of the adaptor generators take arguments themselves and
 116           these arguments are expressed with function call notation too. In those
 117           situations, you will really appreciate the succinctness of <code class="computeroutput"><span class="keyword">operator</span><span class="special">|()</span></code>.
 118         </p>
 119 <h6>
 120 <a name="range.reference.adaptors.introduction.h0"></a>
 121           <span class="phrase"><a name="range.reference.adaptors.introduction.composition_of_adaptors"></a></span><a class="link" href="introduction.html#range.reference.adaptors.introduction.composition_of_adaptors">Composition
 122           of Adaptors</a>
 123         </h6>
 124 <p>
 125           Range Adaptors are a powerful complement to Range algorithms. The reason
 126           is that adaptors are <span class="emphasis"><em><span class="bold"><strong>orthogonal</strong></span></em></span>
 127           to algorithms. For example, consider these Range algorithms:
 128         </p>
 129 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 130 <li class="listitem">
 131               <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy</span><span class="special">(</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">)</span></code>
 132             </li>
 133 <li class="listitem">
 134               <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">count</span><span class="special">(</span>
 135               <span class="identifier">rng</span><span class="special">,</span>
 136               <span class="identifier">pred</span> <span class="special">)</span></code>
 137             </li>
 138 </ul></div>
 139 <p>
 140           What should we do if we only want to copy an element <code class="computeroutput"><span class="identifier">a</span></code>
 141           if it satisfies some predicate, say <code class="computeroutput"><span class="identifier">pred</span><span class="special">(</span><span class="identifier">a</span><span class="special">)</span></code>?
 142           And what if we only want to count the elements that satisfy the same predicate?
 143           The naive answer would be to use these algorithms:
 144         </p>
 145 <div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
 146 <li class="listitem">
 147               <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy_if</span><span class="special">(</span>
 148               <span class="identifier">rng</span><span class="special">,</span>
 149               <span class="identifier">pred</span><span class="special">,</span>
 150               <span class="identifier">out</span> <span class="special">)</span></code>
 151             </li>
 152 <li class="listitem">
 153               <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">count_if</span><span class="special">(</span>
 154               <span class="identifier">rng</span><span class="special">,</span>
 155               <span class="identifier">pred</span> <span class="special">)</span></code>
 156             </li>
 157 </ul></div>
 158 <p>
 159           These algorithms are only defined to maintain a one to one relationship
 160           with the standard library algorithms. This approach of adding algorithm
 161           suffers a combinatorial explosion. Inevitably many algorithms are missing
 162           <code class="computeroutput"><span class="identifier">_if</span></code> variants and there
 163           is redundant development overhead for each new algorithm. The Adaptor Generator
 164           is the design solution to this problem. It is conceivable that some algorithms
 165           are capable of optimization by tightly coupling the filter with the algorithm.
 166           The adaptors provide a more general solution with superior separation of
 167           orthogonal concerns.
 168         </p>
 169 <h6>
 170 <a name="range.reference.adaptors.introduction.h1"></a>
 171           <span class="phrase"><a name="range.reference.adaptors.introduction.range_adaptor_alternative_to_copy_if_algorithm"></a></span><a class="link" href="introduction.html#range.reference.adaptors.introduction.range_adaptor_alternative_to_copy_if_algorithm">Range
 172           Adaptor alternative to copy_if algorithm</a>
 173         </h6>
 174 <p>
 175 </p>
 176 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy_if</span><span class="special">(</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">pred</span><span class="special">,</span> <span class="identifier">out</span> <span class="special">);</span>
 177 </pre>
 178 <p>
 179           can be expressed as
 180 </p>
 181 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">copy</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">adaptors</span><span class="special">::</span><span class="identifier">filtered</span><span class="special">(</span><span class="identifier">pred</span><span class="special">),</span> <span class="identifier">out</span> <span class="special">);</span>
 182 </pre>
 183 <p>
 184         </p>
 185 <h6>
 186 <a name="range.reference.adaptors.introduction.h2"></a>
 187           <span class="phrase"><a name="range.reference.adaptors.introduction.range_adaptor_alternative_to_count_if_algorithm"></a></span><a class="link" href="introduction.html#range.reference.adaptors.introduction.range_adaptor_alternative_to_count_if_algorithm">Range
 188           Adaptor alternative to count_if algorithm</a>
 189         </h6>
 190 <p>
 191 </p>
 192 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">count_if</span><span class="special">(</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">pred</span> <span class="special">);</span>
 193 </pre>
 194 <p>
 195           can be expressed as
 196 </p>
 197 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">size</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">adaptors</span><span class="special">::</span><span class="identifier">filtered</span><span class="special">(</span><span class="identifier">pred</span><span class="special">)</span> <span class="special">);</span>
 198 </pre>
 199 <p>
 200         </p>
 201 <p>
 202           What this means is that many algorithms no longer require nor benefit from
 203           an optimized implementation with an <code class="computeroutput"><span class="identifier">_if</span></code>
 204           suffix. Furthermore, it turns out that algorithms with the <code class="computeroutput"><span class="identifier">_copy</span></code> suffix are often not needed either.
 205           Consider <code class="computeroutput"><span class="identifier">replace_copy_if</span><span class="special">()</span></code> which may be used as
 206         </p>
 207 <p>
 208 </p>
 209 <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>
 210 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">replace_copy_if</span><span class="special">(</span> <span class="identifier">rng</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span><span class="special">(</span><span class="identifier">vec</span><span class="special">),</span> <span class="identifier">pred</span><span class="special">,</span> <span class="identifier">new_value</span> <span class="special">);</span>
 211 </pre>
 212 <p>
 213         </p>
 214 <p>
 215           With adaptors and algorithms we can express this as
 216         </p>
 217 <p>
 218 </p>
 219 <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>
 220 <span class="identifier">boost</span><span class="special">::</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">vec</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">adaptors</span><span class="special">::</span><span class="identifier">replaced_if</span><span class="special">(</span><span class="identifier">pred</span><span class="special">,</span> <span class="identifier">new_value</span><span class="special">));</span>
 221 </pre>
 222 <p>
 223         </p>
 224 <p>
 225           The latter code has several benefits:
 226         </p>
 227 <p>
 228           1. it is more <span class="emphasis"><em><span class="bold"><strong>efficient</strong></span></em></span>
 229           because we avoid extra allocations as might happen with <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">back_inserter</span></code>
 230         </p>
 231 <p>
 232           2. it is <span class="emphasis"><em><span class="bold"><strong>flexible</strong></span></em></span>
 233           as we can subsequently apply even more adaptors, for example:
 234 </p>
 235 <pre class="programlisting"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">push_back</span><span class="special">(</span><span class="identifier">vec</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">adaptors</span><span class="special">::</span><span class="identifier">replaced_if</span><span class="special">(</span><span class="identifier">pred</span><span class="special">,</span> <span class="identifier">new_value</span><span class="special">)</span>
 236                           <span class="special">|</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">adaptors</span><span class="special">::</span><span class="identifier">reversed</span><span class="special">);</span>
 237 </pre>
 238 <p>
 239         </p>
 240 <p>
 241           3. it is <span class="emphasis"><em><span class="bold"><strong>safer</strong></span></em></span> because
 242           there is no use of an unbounded output iterator.
 243         </p>
 244 <p>
 245           In this manner, the <span class="emphasis"><em><span class="bold"><strong>composition</strong></span></em></span>
 246           of Range Adaptors has the following consequences:
 247         </p>
 248 <p>
 249           1. we no longer need many of the <code class="computeroutput"><span class="identifier">_if</span></code>,
 250           <code class="computeroutput"><span class="identifier">_copy</span></code>, <code class="computeroutput"><span class="identifier">_copy_if</span></code>
 251           and <code class="computeroutput"><span class="identifier">_n</span></code> variants of algorithms.
 252         </p>
 253 <p>
 254           2. we can generate a multitude of new algorithms on the fly, for example,
 255           above we generated <code class="computeroutput"><span class="identifier">reverse_replace_copy_if</span><span class="special">()</span></code>
 256         </p>
 257 <p>
 258           In other words:
 259         </p>
 260 <p>
 261           <span class="bold"><strong>Range Adaptors are to algorithms what algorithms
 262           are to containers</strong></span>
 263         </p>
 264 </div>
 265 <table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr>
 266 <td align="left"></td>
 267 <td align="right"><div class="copyright-footer">Copyright &#169; 2003-2010 Thorsten Ottosen,
 268       Neil Groves<p>
 269         Distributed under the Boost Software License, Version 1.0. (See accompanying
 270         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>)
 271       </p>
 272 </div></td>
 273 </tr></table>
 274 <hr>
 275 <div class="spirit-nav">
 276 <a accesskey="p" href="../adaptors.html"><img src="../../../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../adaptors.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="general_requirements.html"><img src="../../../../../../../doc/src/images/next.png" alt="Next"></a>
 277 </div>
 278 </body>
 279 </html>