1<?xml version="1.0" encoding="utf-8" ?> 2<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 3<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en"> 4<head> 5<meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> 6<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" /> 7<title>Filter Iterator</title> 8<meta name="author" content="David Abrahams, Jeremy Siek, Thomas Witt" /> 9<meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab, University of Hanover Institute for Transport Railway Operation and Construction" /> 10<meta name="date" content="2006-09-11" /> 11<meta name="copyright" content="Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003." /> 12<link rel="stylesheet" href="../../../rst.css" type="text/css" /> 13</head> 14<body> 15<div class="document" id="filter-iterator"> 16<h1 class="title">Filter Iterator</h1> 17<table class="docinfo" frame="void" rules="none"> 18<col class="docinfo-name" /> 19<col class="docinfo-content" /> 20<tbody valign="top"> 21<tr><th class="docinfo-name">Author:</th> 22<td>David Abrahams, Jeremy Siek, Thomas Witt</td></tr> 23<tr><th class="docinfo-name">Contact:</th> 24<td><a class="first reference external" href="mailto:dave@boost-consulting.com">dave@boost-consulting.com</a>, <a class="reference external" href="mailto:jsiek@osl.iu.edu">jsiek@osl.iu.edu</a>, <a class="last reference external" href="mailto:witt@ive.uni-hannover.de">witt@ive.uni-hannover.de</a></td></tr> 25<tr><th class="docinfo-name">Organization:</th> 26<td><a class="first reference external" href="http://www.boost-consulting.com">Boost Consulting</a>, Indiana University <a class="reference external" href="http://www.osl.iu.edu">Open Systems 27Lab</a>, University of Hanover <a class="last reference external" href="http://www.ive.uni-hannover.de">Institute for Transport 28Railway Operation and Construction</a></td></tr> 29<tr><th class="docinfo-name">Date:</th> 30<td>2006-09-11</td></tr> 31<tr><th class="docinfo-name">Copyright:</th> 32<td>Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.</td></tr> 33</tbody> 34</table> 35<!-- Distributed under the Boost --> 36<!-- Software License, Version 1.0. (See accompanying --> 37<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 38<table class="docutils field-list" frame="void" rules="none"> 39<col class="field-name" /> 40<col class="field-body" /> 41<tbody valign="top"> 42<tr class="field"><th class="field-name">abstract:</th><td class="field-body"><!-- Copyright David Abrahams 2006. Distributed under the Boost --> 43<!-- Software License, Version 1.0. (See accompanying --> 44<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 45The filter iterator adaptor creates a view of an iterator range in 46which some elements of the range are skipped. A predicate function 47object controls which elements are skipped. When the predicate is 48applied to an element, if it returns <tt class="docutils literal"><span class="pre">true</span></tt> then the element is 49retained and if it returns <tt class="docutils literal"><span class="pre">false</span></tt> then the element is skipped 50over. When skipping over elements, it is necessary for the filter 51adaptor to know when to stop so as to avoid going past the end of the 52underlying range. A filter iterator is therefore constructed with pair 53of iterators indicating the range of elements in the unfiltered 54sequence to be traversed.</td> 55</tr> 56</tbody> 57</table> 58<div class="contents topic" id="table-of-contents"> 59<p class="topic-title first">Table of Contents</p> 60<ul class="simple"> 61<li><a class="reference internal" href="#filter-iterator-synopsis" id="id2"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> synopsis</a></li> 62<li><a class="reference internal" href="#filter-iterator-requirements" id="id3"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> requirements</a></li> 63<li><a class="reference internal" href="#filter-iterator-models" id="id4"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</a></li> 64<li><a class="reference internal" href="#filter-iterator-operations" id="id5"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> operations</a></li> 65<li><a class="reference internal" href="#example" id="id6">Example</a></li> 66</ul> 67</div> 68<div class="section" id="filter-iterator-synopsis"> 69<h1><a class="toc-backref" href="#id2"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> synopsis</a></h1> 70<!-- Copyright David Abrahams, Jeremy Siek, and Thomas Witt --> 71<!-- 2004. Use, modification and distribution is subject to the Boost --> 72<!-- Software License, Version 1.0. (See accompanying file --> 73<!-- LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 74<pre class="literal-block"> 75template <class Predicate, class Iterator> 76class filter_iterator 77{ 78 public: 79 typedef iterator_traits<Iterator>::value_type value_type; 80 typedef iterator_traits<Iterator>::reference reference; 81 typedef iterator_traits<Iterator>::pointer pointer; 82 typedef iterator_traits<Iterator>::difference_type difference_type; 83 typedef /* see below */ iterator_category; 84 85 filter_iterator(); 86 filter_iterator(Predicate f, Iterator x, Iterator end = Iterator()); 87 filter_iterator(Iterator x, Iterator end = Iterator()); 88 template<class OtherIterator> 89 filter_iterator( 90 filter_iterator<Predicate, OtherIterator> const& t 91 , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition 92 ); 93 Predicate predicate() const; 94 Iterator end() const; 95 Iterator const& base() const; 96 reference operator*() const; 97 filter_iterator& operator++(); 98private: 99 Predicate m_pred; // exposition only 100 Iterator m_iter; // exposition only 101 Iterator m_end; // exposition only 102}; 103</pre> 104<p>If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Readable Lvalue Iterator and Bidirectional Traversal 105Iterator then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to 106<tt class="docutils literal"><span class="pre">std::bidirectional_iterator_tag</span></tt>. 107Otherwise, if <tt class="docutils literal"><span class="pre">Iterator</span></tt> models Readable Lvalue Iterator and Forward Traversal 108Iterator then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to 109<tt class="docutils literal"><span class="pre">std::forward_iterator_tag</span></tt>. 110Otherwise <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is 111convertible to <tt class="docutils literal"><span class="pre">std::input_iterator_tag</span></tt>.</p> 112</div> 113<div class="section" id="filter-iterator-requirements"> 114<h1><a class="toc-backref" href="#id3"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> requirements</a></h1> 115<p>The <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument shall meet the requirements of Readable 116Iterator and Single Pass Iterator or it shall meet the requirements of 117Input Iterator.</p> 118<p>The <tt class="docutils literal"><span class="pre">Predicate</span></tt> argument must be Assignable, Copy Constructible, and 119the expression <tt class="docutils literal"><span class="pre">p(x)</span></tt> must be valid where <tt class="docutils literal"><span class="pre">p</span></tt> is an object of type 120<tt class="docutils literal"><span class="pre">Predicate</span></tt>, <tt class="docutils literal"><span class="pre">x</span></tt> is an object of type 121<tt class="docutils literal"><span class="pre">iterator_traits<Iterator>::value_type</span></tt>, and where the type of 122<tt class="docutils literal"><span class="pre">p(x)</span></tt> must be convertible to <tt class="docutils literal"><span class="pre">bool</span></tt>.</p> 123</div> 124<div class="section" id="filter-iterator-models"> 125<h1><a class="toc-backref" href="#id4"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</a></h1> 126<p>The concepts that <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models are dependent on which 127concepts the <tt class="docutils literal"><span class="pre">Iterator</span></tt> argument models, as specified in the 128following tables.</p> 129<table border="1" class="docutils"> 130<colgroup> 131<col width="44%" /> 132<col width="56%" /> 133</colgroup> 134<thead valign="bottom"> 135<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th> 136<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th> 137</tr> 138</thead> 139<tbody valign="top"> 140<tr><td>Single Pass Iterator</td> 141<td>Single Pass Iterator</td> 142</tr> 143<tr><td>Forward Traversal Iterator</td> 144<td>Forward Traversal Iterator</td> 145</tr> 146<tr><td>Bidirectional Traversal Iterator</td> 147<td>Bidirectional Traversal Iterator</td> 148</tr> 149</tbody> 150</table> 151<table border="1" class="docutils"> 152<colgroup> 153<col width="41%" /> 154<col width="59%" /> 155</colgroup> 156<thead valign="bottom"> 157<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th> 158<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th> 159</tr> 160</thead> 161<tbody valign="top"> 162<tr><td>Readable Iterator</td> 163<td>Readable Iterator</td> 164</tr> 165<tr><td>Writable Iterator</td> 166<td>Writable Iterator</td> 167</tr> 168<tr><td>Lvalue Iterator</td> 169<td>Lvalue Iterator</td> 170</tr> 171</tbody> 172</table> 173<table border="1" class="docutils"> 174<colgroup> 175<col width="63%" /> 176<col width="38%" /> 177</colgroup> 178<thead valign="bottom"> 179<tr><th class="head">If <tt class="docutils literal"><span class="pre">Iterator</span></tt> models</th> 180<th class="head">then <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models</th> 181</tr> 182</thead> 183<tbody valign="top"> 184<tr><td>Readable Iterator, Single Pass Iterator</td> 185<td>Input Iterator</td> 186</tr> 187<tr><td>Readable Lvalue Iterator, Forward Traversal Iterator</td> 188<td>Forward Iterator</td> 189</tr> 190<tr><td>Writable Lvalue Iterator, Forward Traversal Iterator</td> 191<td>Mutable Forward Iterator</td> 192</tr> 193<tr><td>Writable Lvalue Iterator, Bidirectional Iterator</td> 194<td>Mutable Bidirectional Iterator</td> 195</tr> 196</tbody> 197</table> 198<p><tt class="docutils literal"><span class="pre">filter_iterator<P1,</span> <span class="pre">X></span></tt> is interoperable with <tt class="docutils literal"><span class="pre">filter_iterator<P2,</span> <span class="pre">Y></span></tt> 199if and only if <tt class="docutils literal"><span class="pre">X</span></tt> is interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt>.</p> 200</div> 201<div class="section" id="filter-iterator-operations"> 202<h1><a class="toc-backref" href="#id5"><tt class="docutils literal"><span class="pre">filter_iterator</span></tt> operations</a></h1> 203<p>In addition to those operations required by the concepts that 204<tt class="docutils literal"><span class="pre">filter_iterator</span></tt> models, <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> provides the following 205operations.</p> 206<p><tt class="docutils literal"><span class="pre">filter_iterator();</span></tt></p> 207<table class="docutils field-list" frame="void" rules="none"> 208<col class="field-name" /> 209<col class="field-body" /> 210<tbody valign="top"> 211<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Predicate</span></tt> and <tt class="docutils literal"><span class="pre">Iterator</span></tt> must be Default Constructible.</td> 212</tr> 213<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> whose``m_pred``, <tt class="docutils literal"><span class="pre">m_iter</span></tt>, and <tt class="docutils literal"><span class="pre">m_end</span></tt> 214members are a default constructed.</td> 215</tr> 216</tbody> 217</table> 218<p><tt class="docutils literal"><span class="pre">filter_iterator(Predicate</span> <span class="pre">f,</span> <span class="pre">Iterator</span> <span class="pre">x,</span> <span class="pre">Iterator</span> <span class="pre">end</span> <span class="pre">=</span> <span class="pre">Iterator());</span></tt></p> 219<table class="docutils field-list" frame="void" rules="none"> 220<col class="field-name" /> 221<col class="field-body" /> 222<tbody valign="top"> 223<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> where <tt class="docutils literal"><span class="pre">m_iter</span></tt> is either 224the first position in the range <tt class="docutils literal"><span class="pre">[x,end)</span></tt> such that <tt class="docutils literal"><span class="pre">f(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt> 225or else``m_iter == end``. The member <tt class="docutils literal"><span class="pre">m_pred</span></tt> is constructed from 226<tt class="docutils literal"><span class="pre">f</span></tt> and <tt class="docutils literal"><span class="pre">m_end</span></tt> from <tt class="docutils literal"><span class="pre">end</span></tt>.</td> 227</tr> 228</tbody> 229</table> 230<p><tt class="docutils literal"><span class="pre">filter_iterator(Iterator</span> <span class="pre">x,</span> <span class="pre">Iterator</span> <span class="pre">end</span> <span class="pre">=</span> <span class="pre">Iterator());</span></tt></p> 231<table class="docutils field-list" frame="void" rules="none"> 232<col class="field-name" /> 233<col class="field-body" /> 234<tbody valign="top"> 235<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">Predicate</span></tt> must be Default Constructible and 236<tt class="docutils literal"><span class="pre">Predicate</span></tt> is a class type (not a function pointer).</td> 237</tr> 238<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> where <tt class="docutils literal"><span class="pre">m_iter</span></tt> is either 239the first position in the range <tt class="docutils literal"><span class="pre">[x,end)</span></tt> such that <tt class="docutils literal"><span class="pre">m_pred(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt> 240or else``m_iter == end``. The member <tt class="docutils literal"><span class="pre">m_pred</span></tt> is default constructed.</td> 241</tr> 242</tbody> 243</table> 244<pre class="literal-block"> 245template <class OtherIterator> 246filter_iterator( 247 filter_iterator<Predicate, OtherIterator> const& t 248 , typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition 249 );`` 250</pre> 251<table class="docutils field-list" frame="void" rules="none"> 252<col class="field-name" /> 253<col class="field-body" /> 254<tbody valign="top"> 255<tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">OtherIterator</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">Iterator</span></tt>.</td> 256</tr> 257<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs a filter iterator whose members are copied from <tt class="docutils literal"><span class="pre">t</span></tt>.</td> 258</tr> 259</tbody> 260</table> 261<p><tt class="docutils literal"><span class="pre">Predicate</span> <span class="pre">predicate()</span> <span class="pre">const;</span></tt></p> 262<table class="docutils field-list" frame="void" rules="none"> 263<col class="field-name" /> 264<col class="field-body" /> 265<tbody valign="top"> 266<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_pred</span></tt></td> 267</tr> 268</tbody> 269</table> 270<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">end()</span> <span class="pre">const;</span></tt></p> 271<table class="docutils field-list" frame="void" rules="none"> 272<col class="field-name" /> 273<col class="field-body" /> 274<tbody valign="top"> 275<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_end</span></tt></td> 276</tr> 277</tbody> 278</table> 279<p><tt class="docutils literal"><span class="pre">Iterator</span> <span class="pre">const&</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p> 280<table class="docutils field-list" frame="void" rules="none"> 281<col class="field-name" /> 282<col class="field-body" /> 283<tbody valign="top"> 284<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator</span></tt></td> 285</tr> 286</tbody> 287</table> 288<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p> 289<table class="docutils field-list" frame="void" rules="none"> 290<col class="field-name" /> 291<col class="field-body" /> 292<tbody valign="top"> 293<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*m_iter</span></tt></td> 294</tr> 295</tbody> 296</table> 297<p><tt class="docutils literal"><span class="pre">filter_iterator&</span> <span class="pre">operator++();</span></tt></p> 298<table class="docutils field-list" frame="void" rules="none"> 299<col class="field-name" /> 300<col class="field-body" /> 301<tbody valign="top"> 302<tr class="field"><th class="field-name">Effects:</th><td class="field-body">Increments <tt class="docutils literal"><span class="pre">m_iter</span></tt> and then continues to 303increment <tt class="docutils literal"><span class="pre">m_iter</span></tt> until either <tt class="docutils literal"><span class="pre">m_iter</span> <span class="pre">==</span> <span class="pre">m_end</span></tt> 304or <tt class="docutils literal"><span class="pre">m_pred(*m_iter)</span> <span class="pre">==</span> <span class="pre">true</span></tt>.</td> 305</tr> 306<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td> 307</tr> 308</tbody> 309</table> 310<!-- Copyright David Abrahams 2006. Distributed under the Boost --> 311<!-- Software License, Version 1.0. (See accompanying --> 312<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 313<pre class="literal-block"> 314template <class Predicate, class Iterator> 315filter_iterator<Predicate,Iterator> 316make_filter_iterator(Predicate f, Iterator x, Iterator end = Iterator()); 317</pre> 318<table class="docutils field-list" frame="void" rules="none"> 319<col class="field-name" /> 320<col class="field-body" /> 321<tbody valign="top"> 322<tr class="field"><th class="field-name">Returns:</th><td class="field-body">filter_iterator<Predicate,Iterator>(f, x, end)</td> 323</tr> 324</tbody> 325</table> 326<pre class="literal-block"> 327template <class Predicate, class Iterator> 328filter_iterator<Predicate,Iterator> 329make_filter_iterator(Iterator x, Iterator end = Iterator()); 330</pre> 331<table class="docutils field-list" frame="void" rules="none"> 332<col class="field-name" /> 333<col class="field-body" /> 334<tbody valign="top"> 335<tr class="field"><th class="field-name">Returns:</th><td class="field-body">filter_iterator<Predicate,Iterator>(x, end)</td> 336</tr> 337</tbody> 338</table> 339<!-- Copyright David Abrahams 2006. Distributed under the Boost --> 340<!-- Software License, Version 1.0. (See accompanying --> 341<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) --> 342</div> 343<div class="section" id="example"> 344<h1><a class="toc-backref" href="#id6">Example</a></h1> 345<p>This example uses <tt class="docutils literal"><span class="pre">filter_iterator</span></tt> and then 346<tt class="docutils literal"><span class="pre">make_filter_iterator</span></tt> to output only the positive integers from an 347array of integers. Then <tt class="docutils literal"><span class="pre">make_filter_iterator</span></tt> is is used to output 348the integers greater than <tt class="docutils literal"><span class="pre">-2</span></tt>.</p> 349<pre class="literal-block"> 350struct is_positive_number { 351 bool operator()(int x) { return 0 < x; } 352}; 353 354int main() 355{ 356 int numbers_[] = { 0, -1, 4, -3, 5, 8, -2 }; 357 const int N = sizeof(numbers_)/sizeof(int); 358 359 typedef int* base_iterator; 360 base_iterator numbers(numbers_); 361 362 // Example using filter_iterator 363 typedef boost::filter_iterator<is_positive_number, base_iterator> 364 FilterIter; 365 366 is_positive_number predicate; 367 FilterIter filter_iter_first(predicate, numbers, numbers + N); 368 FilterIter filter_iter_last(predicate, numbers + N, numbers + N); 369 370 std::copy(filter_iter_first, filter_iter_last, std::ostream_iterator<int>(std::cout, " ")); 371 std::cout << std::endl; 372 373 // Example using make_filter_iterator() 374 std::copy(boost::make_filter_iterator<is_positive_number>(numbers, numbers + N), 375 boost::make_filter_iterator<is_positive_number>(numbers + N, numbers + N), 376 std::ostream_iterator<int>(std::cout, " ")); 377 std::cout << std::endl; 378 379 // Another example using make_filter_iterator() 380 std::copy( 381 boost::make_filter_iterator( 382 std::bind2nd(std::greater<int>(), -2) 383 , numbers, numbers + N) 384 385 , boost::make_filter_iterator( 386 std::bind2nd(std::greater<int>(), -2) 387 , numbers + N, numbers + N) 388 389 , std::ostream_iterator<int>(std::cout, " ") 390 ); 391 392 std::cout << std::endl; 393 394 return boost::exit_success; 395} 396</pre> 397<p>The output is:</p> 398<pre class="literal-block"> 3994 5 8 4004 5 8 4010 -1 4 5 8 402</pre> 403<p>The source code for this example can be found <a class="reference external" href="../example/filter_iterator_example.cpp">here</a>.</p> 404</div> 405</div> 406<div class="footer"> 407<hr class="footer" /> 408<a class="reference external" href="filter_iterator.rst">View document source</a>. 409Generated by <a class="reference external" href="http://docutils.sourceforge.net/">Docutils</a> from <a class="reference external" href="http://docutils.sourceforge.net/rst.html">reStructuredText</a> source. 410 411</div> 412</body> 413</html> 414