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">
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" />
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" />
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
27 Lab
</a>, University of Hanover
<a class=
"last reference external" href=
"http://www.ive.uni-hannover.de">Institute for Transport
28 Railway 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>
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" />
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) -->
45 The filter iterator adaptor creates a view of an iterator range in
46 which some elements of the range are skipped. A predicate function
47 object controls which elements are skipped. When the predicate is
48 applied to an element, if it returns
<tt class=
"docutils literal"><span class=
"pre">true
</span></tt> then the element is
49 retained and if it returns
<tt class=
"docutils literal"><span class=
"pre">false
</span></tt> then the element is skipped
50 over. When skipping over elements, it is necessary for the filter
51 adaptor to know when to stop so as to avoid going past the end of the
52 underlying range. A filter iterator is therefore constructed with pair
53 of iterators indicating the range of elements in the unfiltered
54 sequence to be traversed.
</td>
58 <div class=
"contents topic" id=
"table-of-contents">
59 <p class=
"topic-title first">Table of Contents
</p>
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>
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">
75 template
<class Predicate, class Iterator
>
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;
86 filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
87 filter_iterator(Iterator x, Iterator end = Iterator());
88 template
<class OtherIterator
>
90 filter_iterator
<Predicate, OtherIterator
> const
& t
91 , typename enable_if_convertible
<OtherIterator, Iterator
>::type* =
0 // exposition
93 Predicate predicate() const;
95 Iterator const
& base() const;
96 reference operator*() const;
97 filter_iterator
& operator++();
99 Predicate m_pred; // exposition only
100 Iterator m_iter; // exposition only
101 Iterator m_end; // exposition only
104 <p>If
<tt class=
"docutils literal"><span class=
"pre">Iterator
</span></tt> models Readable Lvalue Iterator and Bidirectional Traversal
105 Iterator 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>.
107 Otherwise, if
<tt class=
"docutils literal"><span class=
"pre">Iterator
</span></tt> models Readable Lvalue Iterator and Forward Traversal
108 Iterator 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>.
110 Otherwise
<tt class=
"docutils literal"><span class=
"pre">iterator_category
</span></tt> is
111 convertible to
<tt class=
"docutils literal"><span class=
"pre">std::input_iterator_tag
</span></tt>.
</p>
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
116 Iterator and Single Pass Iterator or it shall meet the requirements of
118 <p>The
<tt class=
"docutils literal"><span class=
"pre">Predicate
</span></tt> argument must be Assignable, Copy Constructible, and
119 the 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>
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
127 concepts the
<tt class=
"docutils literal"><span class=
"pre">Iterator
</span></tt> argument models, as specified in the
128 following tables.
</p>
129 <table border=
"1" class=
"docutils">
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>
140 <tr><td>Single Pass Iterator
</td>
141 <td>Single Pass Iterator
</td>
143 <tr><td>Forward Traversal Iterator
</td>
144 <td>Forward Traversal Iterator
</td>
146 <tr><td>Bidirectional Traversal Iterator
</td>
147 <td>Bidirectional Traversal Iterator
</td>
151 <table border=
"1" class=
"docutils">
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>
162 <tr><td>Readable Iterator
</td>
163 <td>Readable Iterator
</td>
165 <tr><td>Writable Iterator
</td>
166 <td>Writable Iterator
</td>
168 <tr><td>Lvalue Iterator
</td>
169 <td>Lvalue Iterator
</td>
173 <table border=
"1" class=
"docutils">
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>
184 <tr><td>Readable Iterator, Single Pass Iterator
</td>
185 <td>Input Iterator
</td>
187 <tr><td>Readable Lvalue Iterator, Forward Traversal Iterator
</td>
188 <td>Forward Iterator
</td>
190 <tr><td>Writable Lvalue Iterator, Forward Traversal Iterator
</td>
191 <td>Mutable Forward Iterator
</td>
193 <tr><td>Writable Lvalue Iterator, Bidirectional Iterator
</td>
194 <td>Mutable Bidirectional Iterator
</td>
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>
199 if 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>
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
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" />
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>
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>
214 members are a default constructed.
</td>
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" />
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
224 the 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>
225 or 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>
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" />
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>
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
239 the 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>
240 or else``m_iter == end``. The member
<tt class=
"docutils literal"><span class=
"pre">m_pred
</span></tt> is default constructed.
</td>
244 <pre class=
"literal-block">
245 template
<class OtherIterator
>
247 filter_iterator
<Predicate, OtherIterator
> const
& t
248 , typename enable_if_convertible
<OtherIterator, Iterator
>::type* =
0 // exposition
251 <table class=
"docutils field-list" frame=
"void" rules=
"none">
252 <col class=
"field-name" />
253 <col class=
"field-body" />
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>
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>
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" />
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>
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" />
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>
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" />
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>
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" />
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>
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" />
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
303 increment
<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>
304 or
<tt class=
"docutils literal"><span class=
"pre">m_pred(*m_iter)
</span> <span class=
"pre">==
</span> <span class=
"pre">true
</span></tt>.
</td>
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>
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">
314 template
<class Predicate, class Iterator
>
315 filter_iterator
<Predicate,Iterator
>
316 make_filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
318 <table class=
"docutils field-list" frame=
"void" rules=
"none">
319 <col class=
"field-name" />
320 <col class=
"field-body" />
322 <tr class=
"field"><th class=
"field-name">Returns:
</th><td class=
"field-body">filter_iterator
<Predicate,Iterator
>(f, x, end)
</td>
326 <pre class=
"literal-block">
327 template
<class Predicate, class Iterator
>
328 filter_iterator
<Predicate,Iterator
>
329 make_filter_iterator(Iterator x, Iterator end = Iterator());
331 <table class=
"docutils field-list" frame=
"void" rules=
"none">
332 <col class=
"field-name" />
333 <col class=
"field-body" />
335 <tr class=
"field"><th class=
"field-name">Returns:
</th><td class=
"field-body">filter_iterator
<Predicate,Iterator
>(x, end)
</td>
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) -->
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
347 array of integers. Then
<tt class=
"docutils literal"><span class=
"pre">make_filter_iterator
</span></tt> is is used to output
348 the integers greater than
<tt class=
"docutils literal"><span class=
"pre">-
2</span></tt>.
</p>
349 <pre class=
"literal-block">
350 struct is_positive_number {
351 bool operator()(int x) { return
0 < x; }
356 int numbers_[] = {
0, -
1,
4, -
3,
5,
8, -
2 };
357 const int N = sizeof(numbers_)/sizeof(int);
359 typedef int* base_iterator;
360 base_iterator numbers(numbers_);
362 // Example using filter_iterator
363 typedef boost::filter_iterator
<is_positive_number, base_iterator
>
366 is_positive_number predicate;
367 FilterIter filter_iter_first(predicate, numbers, numbers + N);
368 FilterIter filter_iter_last(predicate, numbers + N, numbers + N);
370 std::copy(filter_iter_first, filter_iter_last, std::ostream_iterator
<int
>(std::cout,
" "));
371 std::cout
<< std::endl;
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;
379 // Another example using make_filter_iterator()
381 boost::make_filter_iterator(
382 std::bind2nd(std::greater
<int
>(), -
2)
383 , numbers, numbers + N)
385 , boost::make_filter_iterator(
386 std::bind2nd(std::greater
<int
>(), -
2)
387 , numbers + N, numbers + N)
389 , std::ostream_iterator
<int
>(std::cout,
" ")
392 std::cout
<< std::endl;
394 return boost::exit_success;
397 <p>The output is:
</p>
398 <pre class=
"literal-block">
403 <p>The source code for this example can be found
<a class=
"reference external" href=
"../example/filter_iterator_example.cpp">here
</a>.
</p>
407 <hr class=
"footer" />
408 <a class=
"reference external" href=
"filter_iterator.rst">View document source
</a>.
409 Generated 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.