[ceph.git] / ceph / src / boost / libs / iterator / doc / permutation_iterator.html

<?xml version="1.0" encoding="utf-8" ?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<meta name="generator" content="Docutils 0.5: http://docutils.sourceforge.net/" />
<title>Permutation Iterator</title>
<meta name="author" content="Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek" />
<meta name="organization" content="Boost Consulting, Indiana University Open Systems Lab" />
<meta name="date" content="2006-09-11" />
<meta name="copyright" content="Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003." />
<link rel="stylesheet" href="../../../rst.css" type="text/css" />
</head>
<body>
<div class="document" id="permutation-iterator">
<h1 class="title">Permutation Iterator</h1>
<table class="docinfo" frame="void" rules="none">
<col class="docinfo-name" />
<col class="docinfo-content" />
<tbody valign="top">
<tr><th class="docinfo-name">Author:</th>
<td>Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek</td></tr>
<tr><th class="docinfo-name">Contact:</th>
<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>
<tr><th class="docinfo-name">Organization:</th>
<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
Lab</a></td></tr>
<tr><th class="docinfo-name">Date:</th>
<td>2006-09-11</td></tr>
<tr><th class="docinfo-name">Copyright:</th>
<td>Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003.</td></tr>
</tbody>
</table>
<!-- Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">abstract:</th><td class="field-body"><!-- Copyright David Abrahams 2006. Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
The permutation iterator adaptor provides a permuted view of a given
range. That is, the view includes every element of the given range but
in a potentially different order.</td>
</tr>
</tbody>
</table>
<div class="contents topic" id="table-of-contents">
<p class="topic-title first">Table of Contents</p>
<ul class="simple">
<li><a class="reference internal" href="#introduction" id="id2">Introduction</a></li>
<li><a class="reference internal" href="#reference" id="id3">Reference</a><ul>
<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>
<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>
<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>
</ul>
</li>
<li><a class="reference internal" href="#example" id="id7">Example</a></li>
</ul>
</div>
<div class="section" id="introduction">
<h1><a class="toc-backref" href="#id2">Introduction</a></h1>
<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
<p>The adaptor takes two arguments:</p>
<blockquote>
<ul class="simple">
<li>an iterator to the range V on which the permutation
will be applied</li>
<li>the reindexing scheme that defines how the
elements of V will be permuted.</li>
</ul>
</blockquote>
<p>Note that the permutation iterator is not limited to strict
permutations of the given range V.  The distance between begin and end
of the reindexing iterators is allowed to be smaller compared to the
size of the range V, in which case the permutation iterator only
provides a permutation of a subrange of V.  The indexes neither need
to be unique. In this same context, it must be noted that the past the
end permutation iterator is completely defined by means of the
past-the-end iterator to the indices.</p>
</div>
<div class="section" id="reference">
<h1><a class="toc-backref" href="#id3">Reference</a></h1>
<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
<pre class="literal-block">
template&lt; class ElementIterator
        , class IndexIterator
        , class ValueT        = use_default
        , class CategoryT     = use_default
        , class ReferenceT    = use_default
        , class DifferenceT   = use_default &gt;
class permutation_iterator
{
public:
  permutation_iterator();
  explicit permutation_iterator(ElementIterator x, IndexIterator y);

  template&lt; class OEIter, class OIIter, class V, class C, class R, class D &gt;
  permutation_iterator(
      permutation_iterator&lt;OEIter, OIIter, V, C, R, D&gt; const&amp; r
      , typename enable_if_convertible&lt;OEIter, ElementIterator&gt;::type* = 0
      , typename enable_if_convertible&lt;OIIter, IndexIterator&gt;::type* = 0
      );
  reference operator*() const;
  permutation_iterator&amp; operator++();
  ElementIterator const&amp; base() const;
private:
  ElementIterator m_elt;      // exposition only
  IndexIterator m_order;      // exposition only
};

template &lt;class ElementIterator, class IndexIterator&gt;
permutation_iterator&lt;ElementIterator, IndexIterator&gt;
make_permutation_iterator( ElementIterator e, IndexIterator i);
</pre>
<div class="section" id="permutation-iterator-requirements">
<h2><a class="toc-backref" href="#id4"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> requirements</a></h2>
<p><tt class="docutils literal"><span class="pre">ElementIterator</span></tt> shall model Random Access Traversal Iterator.
<tt class="docutils literal"><span class="pre">IndexIterator</span></tt> shall model Readable Iterator.  The value type of
the <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> must be convertible to the difference type of
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt>.</p>
</div>
<div class="section" id="permutation-iterator-models">
<h2><a class="toc-backref" href="#id5"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models</a></h2>
<p><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models the same iterator traversal concepts
as <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> and the same iterator access concepts as
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt>.</p>
<p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Single Pass Iterator and
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Iterator then
<tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Input Iterator.</p>
<p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Forward Traversal Iterator and
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
<tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Forward Iterator.</p>
<p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Bidirectional Traversal Iterator and
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
<tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Bidirectional Iterator.</p>
<p>If <tt class="docutils literal"><span class="pre">IndexIterator</span></tt> models Random Access Traversal Iterator and
<tt class="docutils literal"><span class="pre">ElementIterator</span></tt> models Readable Lvalue Iterator then
<tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> models Random Access Iterator.</p>
<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
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
<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
to <tt class="docutils literal"><span class="pre">E2</span></tt>.</p>
</div>
<div class="section" id="permutation-iterator-operations">
<h2><a class="toc-backref" href="#id6"><tt class="docutils literal"><span class="pre">permutation_iterator</span></tt> operations</a></h2>
<p>In addition to those operations required by the concepts that
<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
following operations.</p>
<p><tt class="docutils literal"><span class="pre">permutation_iterator();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
</tbody>
</table>
<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>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
</tbody>
</table>
<pre class="literal-block">
template&lt; class OEIter, class OIIter, class V, class C, class R, class D &gt;
permutation_iterator(
    permutation_iterator&lt;OEIter, OIIter, V, C, R, D&gt; const&amp; r
    , typename enable_if_convertible&lt;OEIter, ElementIterator&gt;::type* = 0
    , typename enable_if_convertible&lt;OIIter, IndexIterator&gt;::type* = 0
    );
</pre>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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
<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>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">reference</span> <span class="pre">operator*()</span> <span class="pre">const;</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
</tbody>
</table>
<p><tt class="docutils literal"><span class="pre">permutation_iterator&amp;</span> <span class="pre">operator++();</span></tt></p>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
<tr class="field"><th class="field-name">Returns:</th><td class="field-body"><tt class="docutils literal"><span class="pre">*this</span></tt></td>
</tr>
</tbody>
</table>
<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>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
</tbody>
</table>
<pre class="literal-block">
template &lt;class ElementIterator, class IndexIterator&gt;
permutation_iterator&lt;ElementIterator, IndexIterator&gt;
make_permutation_iterator(ElementIterator e, IndexIterator i);
</pre>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<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>
</tr>
</tbody>
</table>
</div>
</div>
<div class="section" id="example">
<h1><a class="toc-backref" href="#id7">Example</a></h1>
<!-- Copyright David Abrahams 2006. Distributed under the Boost -->
<!-- Software License, Version 1.0. (See accompanying -->
<!-- file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) -->
<pre class="literal-block">
using namespace boost;
int i = 0;

typedef std::vector&lt; int &gt; element_range_type;
typedef std::list&lt; int &gt; index_type;

static const int element_range_size = 10;
static const int index_size = 4;

element_range_type elements( element_range_size );
for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it)
  *el_it = std::distance(elements.begin(), el_it);

index_type indices( index_size );
for(index_type::iterator i_it = indices.begin() ; i_it != indices.end() ; ++i_it )
  *i_it = element_range_size - index_size + std::distance(indices.begin(), i_it);
std::reverse( indices.begin(), indices.end() );

typedef permutation_iterator&lt; element_range_type::iterator, index_type::iterator &gt; permutation_type;
permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() );
permutation_type it = begin;
permutation_type end = make_permutation_iterator( elements.begin(), indices.end() );

std::cout &lt;&lt; &quot;The original range is : &quot;;
std::copy( elements.begin(), elements.end(), std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
std::cout &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; &quot;The reindexing scheme is : &quot;;
std::copy( indices.begin(), indices.end(), std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
std::cout &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; &quot;The permutated range is : &quot;;
std::copy( begin, end, std::ostream_iterator&lt; int &gt;( std::cout, &quot; &quot; ) );
std::cout &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; &quot;Elements at even indices in the permutation : &quot;;
it = begin;
for(i = 0; i &lt; index_size / 2 ; ++i, it+=2 ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
std::cout &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; &quot;Permutation backwards : &quot;;
it = begin + (index_size);
assert( it != begin );
for( ; it-- != begin ; ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
std::cout &lt;&lt; &quot;\n&quot;;

std::cout &lt;&lt; &quot;Iterate backward with stride 2 : &quot;;
it = begin + (index_size - 1);
for(i = 0 ; i &lt; index_size / 2 ; ++i, it-=2 ) std::cout &lt;&lt; *it &lt;&lt; &quot; &quot;;
std::cout &lt;&lt; &quot;\n&quot;;
</pre>
<p>The output is:</p>
<pre class="literal-block">
The original range is : 0 1 2 3 4 5 6 7 8 9
The reindexing scheme is : 9 8 7 6
The permutated range is : 9 8 7 6
Elements at even indices in the permutation : 9 7
Permutation backwards : 6 7 8 9
Iterate backward with stride 2 : 6 8
</pre>
<p>The source code for this example can be found <a class="reference external" href="../example/permutation_iter_example.cpp">here</a>.</p>
</div>
</div>
<div class="footer">
<hr class="footer" />
<a class="reference external" href="permutation_iterator.rst">View document source</a>.
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.

</div>
</body>
</html>
Commit	Line	Data
7c673cae FG	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
	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< 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 >
98	class permutation_iterator
99	{
100	public:
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;
113	private:
114	ElementIterator m_elt; // exposition only
115	IndexIterator m_order; // exposition only
116	};
117
118	template <class ElementIterator, class IndexIterator>
119	permutation_iterator<ElementIterator, IndexIterator>
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<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
147	with <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
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< class OEIter, class OIIter, class V, class C, class R, class D >
176	permutation_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">
221	template <class ElementIterator, class IndexIterator>
222	permutation_iterator<ElementIterator, IndexIterator>
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<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">
241	using namespace boost;
242	int i = 0;
243
244	typedef std::vector< int > element_range_type;
245	typedef std::list< int > 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< element_range_type::iterator, index_type::iterator > 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 << "The original range is : ";
265	std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) );
266	std::cout << "\n";
267
268	std::cout << "The reindexing scheme is : ";
269	std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) );
270	std::cout << "\n";
271
272	std::cout << "The permutated range is : ";
273	std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) );
274	std::cout << "\n";
275
276	std::cout << "Elements at even indices in the permutation : ";
277	it = begin;
278	for(i = 0; i < index_size / 2 ; ++i, it+=2 ) std::cout << *it << " ";
279	std::cout << "\n";
280
281	std::cout << "Permutation backwards : ";
282	it = begin + (index_size);
283	assert( it != begin );
284	for( ; it-- != begin ; ) std::cout << *it << " ";
285	std::cout << "\n";
286
287	std::cout << "Iterate backward with stride 2 : ";
288	it = begin + (index_size - 1);
289	for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " ";
290	std::cout << "\n";
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>