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@boost-consulting.com">dave@boost-consulting.com</a>, <a class="last reference external" href="mailto:jsiek@osl.iu.edu">jsiek@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 27Lab</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) --> 44The permutation iterator adaptor provides a permuted view of a given 45range. That is, the view includes every element of the given range but 46in 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 72will be applied</li> 73<li>the reindexing scheme that defines how the 74elements of V will be permuted.</li> 75</ul> 76</blockquote> 77<p>Note that the permutation iterator is not limited to strict 78permutations of the given range V. The distance between begin and end 79of the reindexing iterators is allowed to be smaller compared to the 80size of the range V, in which case the permutation iterator only 81provides a permutation of a subrange of V. The indexes neither need 82to be unique. In this same context, it must be noted that the past the 83end permutation iterator is completely defined by means of the 84past-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"> 92template< 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 > 98class permutation_iterator 99{ 100public: 101 permutation_iterator(); 102 explicit permutation_iterator(ElementIterator x, IndexIterator y); 103 104 template< class OEIter, class OIIter, class V, class C, class R, class D > 105 permutation_iterator( 106 permutation_iterator<OEIter, OIIter, V, C, R, D> const& r 107 , typename enable_if_convertible<OEIter, ElementIterator>::type* = 0 108 , typename enable_if_convertible<OIIter, IndexIterator>::type* = 0 109 ); 110 reference operator*() const; 111 permutation_iterator& operator++(); 112 ElementIterator const& base() const; 113private: 114 ElementIterator m_elt; // exposition only 115 IndexIterator m_order; // exposition only 116}; 117 118template <class ElementIterator, class IndexIterator> 119permutation_iterator<ElementIterator, IndexIterator> 120make_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 126the <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 132as <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<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></span></tt> is interoperable 147with <tt class="docutils literal"><span class="pre">permutation_iterator<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></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 149to <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 155following 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"> 175template< class OEIter, class OIIter, class V, class C, class R, class D > 176permutation_iterator( 177 permutation_iterator<OEIter, OIIter, V, C, R, D> const& r 178 , typename enable_if_convertible<OEIter, ElementIterator>::type* = 0 179 , typename enable_if_convertible<OIIter, IndexIterator>::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&</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&</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"> 221template <class ElementIterator, class IndexIterator> 222permutation_iterator<ElementIterator, IndexIterator> 223make_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<ElementIterator,</span> <span class="pre">IndexIterator>(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"> 241using namespace boost; 242int i = 0; 243 244typedef std::vector< int > element_range_type; 245typedef std::list< int > index_type; 246 247static const int element_range_size = 10; 248static const int index_size = 4; 249 250element_range_type elements( element_range_size ); 251for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it) 252 *el_it = std::distance(elements.begin(), el_it); 253 254index_type indices( index_size ); 255for(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); 257std::reverse( indices.begin(), indices.end() ); 258 259typedef permutation_iterator< element_range_type::iterator, index_type::iterator > permutation_type; 260permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() ); 261permutation_type it = begin; 262permutation_type end = make_permutation_iterator( elements.begin(), indices.end() ); 263 264std::cout << "The original range is : "; 265std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) ); 266std::cout << "\n"; 267 268std::cout << "The reindexing scheme is : "; 269std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) ); 270std::cout << "\n"; 271 272std::cout << "The permutated range is : "; 273std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) ); 274std::cout << "\n"; 275 276std::cout << "Elements at even indices in the permutation : "; 277it = begin; 278for(i = 0; i < index_size / 2 ; ++i, it+=2 ) std::cout << *it << " "; 279std::cout << "\n"; 280 281std::cout << "Permutation backwards : "; 282it = begin + (index_size); 283assert( it != begin ); 284for( ; it-- != begin ; ) std::cout << *it << " "; 285std::cout << "\n"; 286 287std::cout << "Iterate backward with stride 2 : "; 288it = begin + (index_size - 1); 289for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " "; 290std::cout << "\n"; 291</pre> 292<p>The output is:</p> 293<pre class="literal-block"> 294The original range is : 0 1 2 3 4 5 6 7 8 9 295The reindexing scheme is : 9 8 7 6 296The permutated range is : 9 8 7 6 297Elements at even indices in the permutation : 9 7 298Permutation backwards : 6 7 8 9 299Iterate 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>. 307Generated 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> 312