ceph/src/boost/libs/iterator/doc/permutation_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>Permutation Iterator</title>
   8 <meta name="author" content="Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek" />
   9 <meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab" />
  10 <meta name="date" content="2006-09-11" />
  11 <meta name="copyright" content="Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003." />
  12 <link rel="stylesheet" href="../../../rst.css" type="text/css" />
  13 </head>
  14 <body>
  15 <div class="document" id="permutation-iterator">
  16 <h1 class="title">Permutation 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>Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek</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:jsiek&#64;osl.iu.edu">jsiek&#64;osl.iu.edu</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="last reference external" href="http://www.osl.iu.edu">Open Systems
  27 Lab</a></td></tr>
  28 <tr><th class="docinfo-name">Date:</th>
  29 <td>2006-09-11</td></tr>
  30 <tr><th class="docinfo-name">Copyright:</th>
  31 <td>Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003.</td></tr>
  32 </tbody>
  33 </table>
  34 <!-- Distributed under the Boost -->
  35 <!-- Software License, Version 1.0. (See accompanying -->
  36 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  37 <table class="docutils field-list" frame="void" rules="none">
  38 <col class="field-name" />
  39 <col class="field-body" />
  40 <tbody valign="top">
  41 <tr class="field"><th class="field-name">abstract:</th><td class="field-body"><!-- Copyright David Abrahams 2006. Distributed under the Boost -->
  42 <!-- Software License, Version 1.0. (See accompanying -->
  43 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  44 The permutation iterator adaptor provides a permuted view of a given
  45 range. That is, the view includes every element of the given range but
  46 in a potentially different order.</td>
  47 </tr>
  48 </tbody>
  49 </table>
  50 <div class="contents topic" id="table-of-contents">
  51 <p class="topic-title first">Table of Contents</p>
  52 <ul class="simple">
  53 <li><a class="reference internal" href="#introduction" id="id2">Introduction</a></li>
  54 <li><a class="reference internal" href="#reference" id="id3">Reference</a><ul>
  55 <li><a class="reference internal" href="#permutation-iterator-requirements" id="id4"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> requirements</a></li>
  56 <li><a class="reference internal" href="#permutation-iterator-models" id="id5"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models</a></li>
  57 <li><a class="reference internal" href="#permutation-iterator-operations" id="id6"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> operations</a></li>
  58 </ul>
  59 </li>
  60 <li><a class="reference internal" href="#example" id="id7">Example</a></li>
  61 </ul>
  62 </div>
  63 <div class="section" id="introduction">
  64 <h1><a class="toc-backref" href="#id2">Introduction</a></h1>
  65 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
  66 <!-- Software License, Version 1.0. (See accompanying -->
  67 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  68 <p>The adaptor takes two arguments:</p>
  69 <blockquote>
  70 <ul class="simple">
  71 <li>an iterator to the range V on which the permutation
  72 will be applied</li>
  73 <li>the reindexing scheme that defines how the
  74 elements of V will be permuted.</li>
  75 </ul>
  76 </blockquote>
  77 <p>Note that the permutation iterator is not limited to strict
  78 permutations of the given range V.  The distance between begin and end
  79 of the reindexing iterators is allowed to be smaller compared to the
  80 size of the range V, in which case the permutation iterator only
  81 provides a permutation of a subrange of V.  The indexes neither need
  82 to be unique. In this same context, it must be noted that the past the
  83 end permutation iterator is completely defined by means of the
  84 past-the-end iterator to the indices.</p>
  85 </div>
  86 <div class="section" id="reference">
  87 <h1><a class="toc-backref" href="#id3">Reference</a></h1>
  88 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
  89 <!-- Software License, Version 1.0. (See accompanying -->
  90 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
  91 <pre class="literal-block">
  92 template&lt; class ElementIterator
  93         , class IndexIterator
  94         , class ValueT        = use_default
  95         , class CategoryT     = use_default
  96         , class ReferenceT    = use_default
  97         , class DifferenceT   = use_default &gt;
  98 class permutation_iterator
  99 {
 100 public:
 101   permutation_iterator();
 102   explicit permutation_iterator(ElementIterator x, IndexIterator y);
 103
 104   template&lt; class OEIter, class OIIter, class V, class C, class R, class D &gt;
 105   permutation_iterator(
 106       permutation_iterator&lt;OEIter, OIIter, V, C, R, D&gt; const&amp; r
 107       , typename enable_if_convertible&lt;OEIter, ElementIterator&gt;::type* = 0
 108       , typename enable_if_convertible&lt;OIIter, IndexIterator&gt;::type* = 0
 109       );
 110   reference operator*() const;
 111   permutation_iterator&amp; operator++();
 112   ElementIterator const&amp; base() const;
 113 private:
 114   ElementIterator m_elt;      // exposition only
 115   IndexIterator m_order;      // exposition only
 116 };
 117
 118 template &lt;class ElementIterator, class IndexIterator&gt;
 119 permutation_iterator&lt;ElementIterator, IndexIterator&gt;
 120 make_permutation_iterator( ElementIterator e, IndexIterator i);
 121 </pre>
 122 <div class="section" id="permutation-iterator-requirements">
 123 <h2><a class="toc-backref" href="#id4"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> requirements</a></h2>
 124 <p><tt class="docutils literal"><span class="pre">ElementIterator</span></tt> shall model Random Access Traversal Iterator.
 125 <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> shall model Readable Iterator.  The value type of
 126 the <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> must be convertible to the difference type of
 127 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt>.</p>
 128 </div>
 129 <div class="section" id="permutation-iterator-models">
 130 <h2><a class="toc-backref" href="#id5"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models</a></h2>
 131 <p><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models the same iterator traversal concepts
 132 as <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> and the same iterator access concepts as
 133 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt>.</p>
 134 <p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Single Pass Iterator and
 135 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Iterator then
 136 <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Input Iterator.</p>
 137 <p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Forward Traversal Iterator and
 138 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
 139 <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Forward Iterator.</p>
 140 <p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Bidirectional Traversal Iterator and
 141 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
 142 <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Bidirectional Iterator.</p>
 143 <p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Random Access Traversal Iterator and
 144 <tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
 145 <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Random Access Iterator.</p>
 146 <p><tt class="docutils literal"><span class="pre">permutation_iterator&lt;E1,</span> <span class="pre">X,</span> <span class="pre">V1,</span> <span class="pre">C2,</span> <span class="pre">R1,</span> <span class="pre">D1&gt;</span></tt> is interoperable
 147 with <tt class="docutils literal"><span class="pre">permutation_iterator&lt;E2,</span> <span class="pre">Y,</span> <span class="pre">V2,</span> <span class="pre">C2,</span> <span class="pre">R2,</span> <span class="pre">D2&gt;</span></tt> if and only if
 148 <tt class="docutils literal"><span class="pre">X</span></tt> is interoperable with <tt class="docutils literal"><span class="pre">Y</span></tt> and <tt class="docutils literal"><span class="pre">E1</span></tt> is convertible
 149 to <tt class="docutils literal"><span class="pre">E2</span></tt>.</p>
 150 </div>
 151 <div class="section" id="permutation-iterator-operations">
 152 <h2><a class="toc-backref" href="#id6"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> operations</a></h2>
 153 <p>In addition to those operations required by the concepts that
 154 <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models, <tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> provides the
 155 following operations.</p>
 156 <p><tt class="docutils literal"><span class="pre">permutation_iterator();</span></tt></p>
 157 <table class="docutils field-list" frame="void" rules="none">
 158 <col class="field-name" />
 159 <col class="field-body" />
 160 <tbody valign="top">
 161 <tr class="field"><th class="field-name">Effects:</th><td class="field-body">Default constructs <tt class="docutils literal"><span class="pre">m_elt</span></tt> and <tt class="docutils literal"><span class="pre">m_order</span></tt>.</td>
 162 </tr>
 163 </tbody>
 164 </table>
 165 <p><tt class="docutils literal"><span class="pre">explicit</span> <span class="pre">permutation_iterator(ElementIterator</span> <span class="pre">x,</span> <span class="pre">IndexIterator</span> <span class="pre">y);</span></tt></p>
 166 <table class="docutils field-list" frame="void" rules="none">
 167 <col class="field-name" />
 168 <col class="field-body" />
 169 <tbody valign="top">
 170 <tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs <tt class="docutils literal"><span class="pre">m_elt</span></tt> from <tt class="docutils literal"><span class="pre">x</span></tt> and <tt class="docutils literal"><span class="pre">m_order</span></tt> from <tt class="docutils literal"><span class="pre">y</span></tt>.</td>
 171 </tr>
 172 </tbody>
 173 </table>
 174 <pre class="literal-block">
 175 template&lt; class OEIter, class OIIter, class V, class C, class R, class D &gt;
 176 permutation_iterator(
 177     permutation_iterator&lt;OEIter, OIIter, V, C, R, D&gt; const&amp; r
 178     , typename enable_if_convertible&lt;OEIter, ElementIterator&gt;::type* = 0
 179     , typename enable_if_convertible&lt;OIIter, IndexIterator&gt;::type* = 0
 180     );
 181 </pre>
 182 <table class="docutils field-list" frame="void" rules="none">
 183 <col class="field-name" />
 184 <col class="field-body" />
 185 <tbody valign="top">
 186 <tr class="field"><th class="field-name">Effects:</th><td class="field-body">Constructs <tt class="docutils literal"><span class="pre">m_elt</span></tt> from <tt class="docutils literal"><span class="pre">r.m_elt</span></tt> and
 187 <tt class="docutils literal"><span class="pre">m_order</span></tt> from <tt class="docutils literal"><span class="pre">y.m_order</span></tt>.</td>
 188 </tr>
 189 </tbody>
 190 </table>
 191 <p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
 192 <table class="docutils field-list" frame="void" rules="none">
 193 <col class="field-name" />
 194 <col class="field-body" />
 195 <tbody valign="top">
 196 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*(m_elt</span> <span class="pre">+</span> <span class="pre">*m_order)</span></tt></td>
 197 </tr>
 198 </tbody>
 199 </table>
 200 <p><tt class="docutils literal"><span class="pre">permutation_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
 201 <table class="docutils field-list" frame="void" rules="none">
 202 <col class="field-name" />
 203 <col class="field-body" />
 204 <tbody valign="top">
 205 <tr class="field"><th class="field-name">Effects:</th><td class="field-body"><tt class="docutils literal"><span class="pre">++m_order</span></tt></td>
 206 </tr>
 207 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
 208 </tr>
 209 </tbody>
 210 </table>
 211 <p><tt class="docutils literal"><span class="pre">ElementIterator</span> <span class="pre">const&amp;</span> <span class="pre">base()</span> <span class="pre">const;</span></tt></p>
 212 <table class="docutils field-list" frame="void" rules="none">
 213 <col class="field-name" />
 214 <col class="field-body" />
 215 <tbody valign="top">
 216 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">m_order</span></tt></td>
 217 </tr>
 218 </tbody>
 219 </table>
 220 <pre class="literal-block">
 221 template &lt;class ElementIterator, class IndexIterator&gt;
 222 permutation_iterator&lt;ElementIterator, IndexIterator&gt;
 223 make_permutation_iterator(ElementIterator e, IndexIterator i);
 224 </pre>
 225 <table class="docutils field-list" frame="void" rules="none">
 226 <col class="field-name" />
 227 <col class="field-body" />
 228 <tbody valign="top">
 229 <tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">permutation_iterator&lt;ElementIterator,</span> <span class="pre">IndexIterator&gt;(e,</span> <span class="pre">i)</span></tt></td>
 230 </tr>
 231 </tbody>
 232 </table>
 233 </div>
 234 </div>
 235 <div class="section" id="example">
 236 <h1><a class="toc-backref" href="#id7">Example</a></h1>
 237 <!-- Copyright David Abrahams 2006. Distributed under the Boost -->
 238 <!-- Software License, Version 1.0. (See accompanying -->
 239 <!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
 240 <pre class="literal-block">
 241 using namespace boost;
 242 int i = 0;
 243
 244 typedef std::vector&lt; int &gt; element_range_type;
 245 typedef std::list&lt; int &gt; index_type;
 246
 247 static const int element_range_size = 10;
 248 static const int index_size = 4;
 249
 250 element_range_type elements( element_range_size );
 251 for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it)
 252   *el_it = std::distance(elements.begin(), el_it);
 253
 254 index_type indices( index_size );
 255 for(index_type::iterator i_it = indices.begin() ; i_it != indices.end() ; ++i_it )
 256   *i_it = element_range_size - index_size + std::distance(indices.begin(), i_it);
 257 std::reverse( indices.begin(), indices.end() );
 258
 259 typedef permutation_iterator&lt; element_range_type::iterator, index_type::iterator &gt; permutation_type;
 260 permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() );
 261 permutation_type it = begin;
 262 permutation_type end = make_permutation_iterator( elements.begin(), indices.end() );
 263
 264 std::cout &lt;&lt; &quot;The original range is : &quot;;
 265 std::copy( elements.begin(), elements.end(), std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
 266 std::cout &lt;&lt; &quot;\n&quot;;
 267
 268 std::cout &lt;&lt; &quot;The reindexing scheme is : &quot;;
 269 std::copy( indices.begin(), indices.end(), std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
 270 std::cout &lt;&lt; &quot;\n&quot;;
 271
 272 std::cout &lt;&lt; &quot;The permutated range is : &quot;;
 273 std::copy( begin, end, std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
 274 std::cout &lt;&lt; &quot;\n&quot;;
 275
 276 std::cout &lt;&lt; &quot;Elements at even indices in the permutation : &quot;;
 277 it = begin;
 278 for(i = 0; i &lt; index_size / 2 ; ++i, it+=2 ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
 279 std::cout &lt;&lt; &quot;\n&quot;;
 280
 281 std::cout &lt;&lt; &quot;Permutation backwards : &quot;;
 282 it = begin + (index_size);
 283 assert( it != begin );
 284 for( ; it-- != begin ; ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
 285 std::cout &lt;&lt; &quot;\n&quot;;
 286
 287 std::cout &lt;&lt; &quot;Iterate backward with stride 2 : &quot;;
 288 it = begin + (index_size - 1);
 289 for(i = 0 ; i &lt; index_size / 2 ; ++i, it-=2 ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
 290 std::cout &lt;&lt; &quot;\n&quot;;
 291 </pre>
 292 <p>The output is:</p>
 293 <pre class="literal-block">
 294 The original range is : 0 1 2 3 4 5 6 7 8 9
 295 The reindexing scheme is : 9 8 7 6
 296 The permutated range is : 9 8 7 6
 297 Elements at even indices in the permutation : 9 7
 298 Permutation backwards : 6 7 8 9
 299 Iterate backward with stride 2 : 6 8
 300 </pre>
 301 <p>The source code for this example can be found <a class="reference external" href="../example/permutation_iter_example.cpp">here</a>.</p>
 302 </div>
 303 </div>
 304 <div class="footer">
 305 <hr class="footer" />
 306 <a class="reference external" href="permutation_iterator.rst">View document source</a>.
 307 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.
 308
 309 </div>
 310 </body>
 311 </html>