1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 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.79.1"> 7<link rel="home" href="../../../index.html" title="Chapter 1. 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"><</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">></span> 40<span class="preprocessor">#include</span> <span class="special"><</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">></span> 41<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span> 42<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">vector</span><span class="special">></span> 43 44<span class="identifier">std</span><span class="special">::</span><span class="identifier">vector</span><span class="special"><</span><span class="keyword">int</span><span class="special">></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"><</span><span class="keyword">int</span><span class="special">>(</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"><</span><span class="keyword">int</span><span class="special">></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"><</span><span class="keyword">int</span><span class="special">>(</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"><</span><span class="keyword">int</span><span class="special">></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"><</span><span class="keyword">int</span><span class="special">>(</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"><</span><span class="keyword">int</span><span class="special">></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"><</span><span class="keyword">int</span><span class="special">>(</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"><</span><span class="keyword">int</span><span class="special">></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"><</span><span class="keyword">int</span><span class="special">></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 © 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> 280