ceph/src/boost/libs/iterator/doc/zip_iterator.html

   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>Zip Iterator</title>
   8 <meta name="author" content="David Abrahams, Thomas Becker" />
   9 <meta name="organization" content="Boost Consulting, Zephyr Associates, Inc." />
  10 <meta name="date" content="2006-09-11" />
  11 <meta name="copyright" content="Copyright David Abrahams and Thomas Becker 2003." />
  12 <link rel="stylesheet" href="../../../rst.css" type="text/css" />
  13 </head>
  14 <body>
  15 <div class="document" id="zip-iterator">
  16 <h1 class="title">Zip 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, Thomas Becker</td></tr>
  23 <tr><th class="docinfo-name">Contact:</th>
  24 <td><a class="first reference external" href="mailto:dave&#64;boost-consulting.com">dave&#64;boost-consulting.com</a>, <a class="last reference external" href="mailto:thomas&#64;styleadvisor.com">thomas&#64;styleadvisor.com</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>, <a class="last reference external" href="http://www.styleadvisor.com">Zephyr Associates, Inc.</a></td></tr>
  27 <tr><th class="docinfo-name">Date:</th>
  28 <td>2006-09-11</td></tr>
  29 <tr><th class="docinfo-name">Copyright:</th>
  30 <td>Copyright David Abrahams and Thomas Becker 2003.</td></tr>
  31 </tbody>
  32 </table>
  33 <!-- Distributed under the Boost -->
  34 <!-- Software License, Version 1.0. (See accompanying -->
  35 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  36 <table class="docutils field-list" frame="void" rules="none">
  37 <col class="field-name" />
  38 <col class="field-body" />
  39 <tbody valign="top">
  40 <tr class="field"><th class="field-name">abstract:</th><td class="field-body"><!-- Copyright David Abrahams 2006. Distributed under the Boost -->
  41 <!-- Software License, Version 1.0. (See accompanying -->
  42 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  43 The zip iterator provides the ability to parallel-iterate
  44 over several controlled sequences simultaneously. A zip
  45 iterator is constructed from a tuple of iterators. Moving
  46 the zip iterator moves all the iterators in parallel.
  47 Dereferencing the zip iterator returns a tuple that contains
  48 the results of dereferencing the individual iterators.</td>
  49 </tr>
  50 </tbody>
  51 </table>
  52 <div class="contents topic" id="table-of-contents">
  53 <p class="topic-title first">Table of Contents</p>
  54 <ul class="simple">
  55 <li><a class="reference internal" href="#zip-iterator-synopsis" id="id1"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> synopsis</a></li>
  56 <li><a class="reference internal" href="#zip-iterator-requirements" id="id2"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> requirements</a></li>
  57 <li><a class="reference internal" href="#zip-iterator-models" id="id3"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> models</a></li>
  58 <li><a class="reference internal" href="#zip-iterator-operations" id="id4"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> operations</a></li>
  59 <li><a class="reference internal" href="#examples" id="id5">Examples</a></li>
  60 </ul>
  61 </div>
  62 <div class="section" id="zip-iterator-synopsis">
  63 <h1><a class="toc-backref" href="#id1"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> synopsis</a></h1>
  64 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
  65 <!-- Software License, Version 1.0. (See accompanying -->
  66 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  67 <pre class="literal-block">
  68 template&lt;typename IteratorTuple&gt;
  69 class zip_iterator
  70 {
  71
  72 public:
  73   typedef /* see below */ reference;
  74   typedef reference value_type;
  75   typedef value_type* pointer;
  76   typedef /* see below */ difference_type;
  77   typedef /* see below */ iterator_category;
  78
  79   zip_iterator();
  80   zip_iterator(IteratorTuple iterator_tuple);
  81
  82   template&lt;typename OtherIteratorTuple&gt;
  83   zip_iterator(
  84         const zip_iterator&lt;OtherIteratorTuple&gt;&amp; other
  85       , typename enable_if_convertible&lt;
  86               OtherIteratorTuple
  87             , IteratorTuple&gt;::type* = 0     // exposition only
  88   );
  89
  90   const IteratorTuple&amp; get_iterator_tuple() const;
  91
  92 private:
  93   IteratorTuple m_iterator_tuple;     // exposition only
  94 };
  95
  96 template&lt;typename IteratorTuple&gt;
  97 zip_iterator&lt;IteratorTuple&gt;
  98 make_zip_iterator(IteratorTuple t);
  99 </pre>
 100 <p>The <tt class="docutils literal"><span class="pre">reference</span></tt> member of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> is the type of the tuple
 101 made of the reference types of the iterator types in the <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt>
 102 argument.</p>
 103 <p>The <tt class="docutils literal"><span class="pre">difference_type</span></tt> member of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> is the <tt class="docutils literal"><span class="pre">difference_type</span></tt>
 104 of the first of the iterator types in the <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt> argument.</p>
 105 <p>The <tt class="docutils literal"><span class="pre">iterator_category</span></tt> member of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> is convertible to the
 106 minimum of the traversal categories of the iterator types in the <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt>
 107 argument. For example, if the <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> holds only vector
 108 iterators, then <tt class="docutils literal"><span class="pre">iterator_category</span></tt> is convertible to
 109 <tt class="docutils literal"><span class="pre">boost::random_access_traversal_tag</span></tt>. If you add a list iterator, then
 110 <tt class="docutils literal"><span class="pre">iterator_category</span></tt> will be convertible to <tt class="docutils literal"><span class="pre">boost::bidirectional_traversal_tag</span></tt>,
 111 but no longer to <tt class="docutils literal"><span class="pre">boost::random_access_traversal_tag</span></tt>.</p>
 112 </div>
 113 <div class="section" id="zip-iterator-requirements">
 114 <h1><a class="toc-backref" href="#id2"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> requirements</a></h1>
 115 <p>All iterator types in the argument <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt> shall model Readable Iterator.</p>
 116 </div>
 117 <div class="section" id="zip-iterator-models">
 118 <h1><a class="toc-backref" href="#id3"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> models</a></h1>
 119 <p>The resulting <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> models Readable Iterator.</p>
 120 <p>The fact that the <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> models only Readable Iterator does not
 121 prevent you from modifying the values that the individual iterators point
 122 to. The tuple returned by the <tt class="docutils literal"><span class="pre">zip_iterator</span></tt>'s <tt class="docutils literal"><span class="pre">operator*</span></tt> is a tuple
 123 constructed from the reference types of the individual iterators, not
 124 their value types. For example, if <tt class="docutils literal"><span class="pre">zip_it</span></tt> is a <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> whose
 125 first member iterator is an <tt class="docutils literal"><span class="pre">std::vector&lt;double&gt;::iterator</span></tt>, then the
 126 following line will modify the value which the first member iterator of
 127 <tt class="docutils literal"><span class="pre">zip_it</span></tt> currently points to:</p>
 128 <pre class="literal-block">
 129 zip_it-&gt;get&lt;0&gt;() = 42.0;
 130 </pre>
 131 <p>Consider the set of standard traversal concepts obtained by taking
 132 the most refined standard traversal concept modeled by each individual
 133 iterator type in the <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt> argument.The <tt class="docutils literal"><span class="pre">zip_iterator</span></tt>
 134 models the least refined standard traversal concept in this set.</p>
 135 <p><tt class="docutils literal"><span class="pre">zip_iterator&lt;IteratorTuple1&gt;</span></tt> is interoperable with
 136 <tt class="docutils literal"><span class="pre">zip_iterator&lt;IteratorTuple2&gt;</span></tt> if and only if <tt class="docutils literal"><span class="pre">IteratorTuple1</span></tt>
 137 is interoperable with <tt class="docutils literal"><span class="pre">IteratorTuple2</span></tt>.</p>
 138 </div>
 139 <div class="section" id="zip-iterator-operations">
 140 <h1><a class="toc-backref" href="#id4"><tt class="docutils literal"><span class="pre">zip_iterator</span></tt> operations</a></h1>
 141 <p>In addition to the operations required by the concepts modeled by
 142 <tt class="docutils literal"><span class="pre">zip_iterator</span></tt>, <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> provides the following
 143 operations.</p>
 144 <p><tt class="docutils literal"><span class="pre">zip_iterator();</span></tt></p>
 145 <table class="docutils field-list" frame="void" rules="none">
 146 <col class="field-name" />
 147 <col class="field-body" />
 148 <tbody valign="top">
 149 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>
 150 default constructed.</td>
 151 </tr>
 152 </tbody>
 153 </table>
 154 <p><tt class="docutils literal"><span class="pre">zip_iterator(IteratorTuple</span> <span class="pre">iterator_tuple);</span></tt></p>
 155 <table class="docutils field-list" frame="void" rules="none">
 156 <col class="field-name" />
 157 <col class="field-body" />
 158 <tbody valign="top">
 159 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> with <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>
 160 initialized to <tt class="docutils literal"><span class="pre">iterator_tuple</span></tt>.</td>
 161 </tr>
 162 </tbody>
 163 </table>
 164 <pre class="literal-block">
 165 template&lt;typename OtherIteratorTuple&gt;
 166 zip_iterator(
 167       const zip_iterator&lt;OtherIteratorTuple&gt;&amp; other
 168     , typename enable_if_convertible&lt;
 169             OtherIteratorTuple
 170           , IteratorTuple&gt;::type* = 0     // exposition only
 171 );
 172 </pre>
 173 <table class="docutils field-list" frame="void" rules="none">
 174 <col class="field-name" />
 175 <col class="field-body" />
 176 <tbody valign="top">
 177 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> that is a copy of <tt class="docutils literal"><span class="pre">other</span></tt>.</td>
 178 </tr>
 179 <tr class="field"><th class="field-name">Requires:</th><td class="field-body"><tt class="docutils literal"><span class="pre">OtherIteratorTuple</span></tt> is implicitly convertible to <tt class="docutils literal"><span class="pre">IteratorTuple</span></tt>.</td>
 180 </tr>
 181 </tbody>
 182 </table>
 183 <p><tt class="docutils literal"><span class="pre">const</span> <span class="pre">IteratorTuple&amp;</span> <span class="pre">get_iterator_tuple()</span> <span class="pre">const;</span></tt></p>
 184 <table class="docutils field-list" frame="void" rules="none">
 185 <col class="field-name" />
 186 <col class="field-body" />
 187 <tbody valign="top">
 188 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt></td>
 189 </tr>
 190 </tbody>
 191 </table>
 192 <p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
 193 <table class="docutils field-list" frame="void" rules="none">
 194 <col class="field-name" />
 195 <col class="field-body" />
 196 <tbody valign="top">
 197 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">A tuple consisting of the results of dereferencing all iterators in
 198 <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>.</td>
 199 </tr>
 200 </tbody>
 201 </table>
 202 <p><tt class="docutils literal"><span class="pre">zip_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
 203 <table class="docutils field-list" frame="void" rules="none">
 204 <col class="field-name" />
 205 <col class="field-body" />
 206 <tbody valign="top">
 207 <tr class="field"><th class="field-name">Effects:</th><td class="field-body">Increments each iterator in <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>.</td>
 208 </tr>
 209 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
 210 </tr>
 211 </tbody>
 212 </table>
 213 <p><tt class="docutils literal"><span class="pre">zip_iterator&amp;</span> <span class="pre">operator--();</span></tt></p>
 214 <table class="docutils field-list" frame="void" rules="none">
 215 <col class="field-name" />
 216 <col class="field-body" />
 217 <tbody valign="top">
 218 <tr class="field"><th class="field-name">Effects:</th><td class="field-body">Decrements each iterator in <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>.</td>
 219 </tr>
 220 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
 221 </tr>
 222 </tbody>
 223 </table>
 224 <pre class="literal-block">
 225 template&lt;typename IteratorTuple&gt;
 226 zip_iterator&lt;IteratorTuple&gt;
 227 make_zip_iterator(IteratorTuple t);
 228 </pre>
 229 <table class="docutils field-list" frame="void" rules="none">
 230 <col class="field-name" />
 231 <col class="field-body" />
 232 <tbody valign="top">
 233 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">zip_iterator&lt;IteratorTuple&gt;</span></tt> with <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>
 234 initialized to <tt class="docutils literal"><span class="pre">t</span></tt>.</td>
 235 </tr>
 236 </tbody>
 237 </table>
 238 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
 239 <!-- Software License, Version 1.0. (See accompanying -->
 240 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
 241 <pre class="literal-block">
 242 template&lt;typename IteratorTuple&gt;
 243 zip_iterator&lt;IteratorTuple&gt;
 244 make_zip_iterator(IteratorTuple t);
 245 </pre>
 246 <table class="docutils field-list" frame="void" rules="none">
 247 <col class="field-name" />
 248 <col class="field-body" />
 249 <tbody valign="top">
 250 <tr class="field"><th class="field-name">Returns:</th><td class="field-body">An instance of <tt class="docutils literal"><span class="pre">zip_iterator&lt;IteratorTuple&gt;</span></tt> with <tt class="docutils literal"><span class="pre">m_iterator_tuple</span></tt>
 251 initialized to <tt class="docutils literal"><span class="pre">t</span></tt>.</td>
 252 </tr>
 253 </tbody>
 254 </table>
 255 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
 256 <!-- Software License, Version 1.0. (See accompanying -->
 257 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
 258 </div>
 259 <div class="section" id="examples">
 260 <h1><a class="toc-backref" href="#id5">Examples</a></h1>
 261 <p>There are two main types of applications of the <tt class="docutils literal"><span class="pre">zip_iterator</span></tt>. The first
 262 one concerns runtime efficiency: If one has several controlled sequences
 263 of the same length that must be somehow processed, e.g., with the
 264 <tt class="docutils literal"><span class="pre">for_each</span></tt> algorithm, then it is more efficient to perform just
 265 one parallel-iteration rather than several individual iterations. For an
 266 example, assume that <tt class="docutils literal"><span class="pre">vect_of_doubles</span></tt> and <tt class="docutils literal"><span class="pre">vect_of_ints</span></tt>
 267 are two vectors of equal length containing doubles and ints, respectively,
 268 and consider the following two iterations:</p>
 269 <pre class="literal-block">
 270 std::vector&lt;double&gt;::const_iterator beg1 = vect_of_doubles.begin();
 271 std::vector&lt;double&gt;::const_iterator end1 = vect_of_doubles.end();
 272 std::vector&lt;int&gt;::const_iterator beg2 = vect_of_ints.begin();
 273 std::vector&lt;int&gt;::const_iterator end2 = vect_of_ints.end();
 274
 275 std::for_each(beg1, end1, func_0());
 276 std::for_each(beg2, end2, func_1());
 277 </pre>
 278 <p>These two iterations can now be replaced with a single one as follows:</p>
 279 <pre class="literal-block">
 280 std::for_each(
 281   boost::make_zip_iterator(
 282     boost::make_tuple(beg1, beg2)
 283     ),
 284   boost::make_zip_iterator(
 285     boost::make_tuple(end1, end2)
 286     ),
 287   zip_func()
 288   );
 289 </pre>
 290 <p>A non-generic implementation of <tt class="docutils literal"><span class="pre">zip_func</span></tt> could look as follows:</p>
 291 <pre class="literal-block">
 292 struct zip_func :
 293   public std::unary_function&lt;const boost::tuple&lt;const double&amp;, const int&amp;&gt;&amp;, void&gt;
 294 {
 295   void operator()(const boost::tuple&lt;const double&amp;, const int&amp;&gt;&amp; t) const
 296   {
 297     m_f0(t.get&lt;0&gt;());
 298     m_f1(t.get&lt;1&gt;());
 299   }
 300
 301 private:
 302   func_0 m_f0;
 303   func_1 m_f1;
 304 };
 305 </pre>
 306 <p>The second important application of the <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> is as a building block
 307 to make combining iterators. A combining iterator is an iterator
 308 that parallel-iterates over several controlled sequences and, upon
 309 dereferencing, returns the result of applying a functor to the values of the
 310 sequences at the respective positions. This can now be achieved by using the
 311 <tt class="docutils literal"><span class="pre">zip_iterator</span></tt> in conjunction with the <tt class="docutils literal"><span class="pre">transform_iterator</span></tt>.</p>
 312 <p>Suppose, for example, that you have two vectors of doubles, say
 313 <tt class="docutils literal"><span class="pre">vect_1</span></tt> and <tt class="docutils literal"><span class="pre">vect_2</span></tt>, and you need to expose to a client
 314 a controlled sequence containing the products of the elements of
 315 <tt class="docutils literal"><span class="pre">vect_1</span></tt> and <tt class="docutils literal"><span class="pre">vect_2</span></tt>. Rather than placing these products
 316 in a third vector, you can use a combining iterator that calculates the
 317 products on the fly. Let us assume that <tt class="docutils literal"><span class="pre">tuple_multiplies</span></tt> is a
 318 functor that works like <tt class="docutils literal"><span class="pre">std::multiplies</span></tt>, except that it takes
 319 its two arguments packaged in a tuple. Then the two iterators
 320 <tt class="docutils literal"><span class="pre">it_begin</span></tt> and <tt class="docutils literal"><span class="pre">it_end</span></tt> defined below delimit a controlled
 321 sequence containing the products of the elements of <tt class="docutils literal"><span class="pre">vect_1</span></tt> and
 322 <tt class="docutils literal"><span class="pre">vect_2</span></tt>:</p>
 323 <pre class="literal-block">
 324 typedef boost::tuple&lt;
 325   std::vector&lt;double&gt;::const_iterator,
 326   std::vector&lt;double&gt;::const_iterator
 327   &gt; the_iterator_tuple;
 328
 329 typedef boost::zip_iterator&lt;
 330   the_iterator_tuple
 331   &gt; the_zip_iterator;
 332
 333 typedef boost::transform_iterator&lt;
 334   tuple_multiplies&lt;double&gt;,
 335   the_zip_iterator
 336   &gt; the_transform_iterator;
 337
 338 the_transform_iterator it_begin(
 339   the_zip_iterator(
 340     the_iterator_tuple(
 341       vect_1.begin(),
 342       vect_2.begin()
 343       )
 344     ),
 345   tuple_multiplies&lt;double&gt;()
 346   );
 347
 348 the_transform_iterator it_end(
 349   the_zip_iterator(
 350     the_iterator_tuple(
 351       vect_1.end(),
 352       vect_2.end()
 353       )
 354     ),
 355   tuple_multiplies&lt;double&gt;()
 356   );
 357 </pre>
 358 </div>
 359 </div>
 360 <div class="footer">
 361 <hr class="footer" />
 362 <a class="reference external" href="zip_iterator.rst">View document source</a>.
 363 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.
 364
 365 </div>
 366 </body>
 367 </html>