1[section:permutation Permutation Iterator] 2 3The permutation iterator adaptor provides a permuted view of a given 4range. That is, the view includes every element of the given range but 5in a potentially different order. The adaptor takes two arguments: 6 7* an iterator to the range V on which the permutation 8 will be applied 9* the reindexing scheme that defines how the 10 elements of V will be permuted. 11 12Note that the permutation iterator is not limited to strict 13permutations of the given range V. The distance between begin and end 14of the reindexing iterators is allowed to be smaller compared to the 15size of the range V, in which case the permutation iterator only 16provides a permutation of a subrange of V. The indexes neither need 17to be unique. In this same context, it must be noted that the past the 18end permutation iterator is completely defined by means of the 19past-the-end iterator to the indices. 20 21[h2 Example] 22 23 using namespace boost; 24 int i = 0; 25 26 typedef std::vector< int > element_range_type; 27 typedef std::list< int > index_type; 28 29 static const int element_range_size = 10; 30 static const int index_size = 4; 31 32 element_range_type elements( element_range_size ); 33 for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it) 34 *el_it = std::distance(elements.begin(), el_it); 35 36 index_type indices( index_size ); 37 for(index_type::iterator i_it = indices.begin() ; i_it != indices.end() ; ++i_it ) 38 *i_it = element_range_size - index_size + std::distance(indices.begin(), i_it); 39 std::reverse( indices.begin(), indices.end() ); 40 41 typedef permutation_iterator< element_range_type::iterator, index_type::iterator > permutation_type; 42 permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() ); 43 permutation_type it = begin; 44 permutation_type end = make_permutation_iterator( elements.begin(), indices.end() ); 45 46 std::cout << "The original range is : "; 47 std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) ); 48 std::cout << "\n"; 49 50 std::cout << "The reindexing scheme is : "; 51 std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) ); 52 std::cout << "\n"; 53 54 std::cout << "The permutated range is : "; 55 std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) ); 56 std::cout << "\n"; 57 58 std::cout << "Elements at even indices in the permutation : "; 59 it = begin; 60 for(i = 0; i < index_size / 2 ; ++i, it+=2 ) std::cout << *it << " "; 61 std::cout << "\n"; 62 63 std::cout << "Permutation backwards : "; 64 it = begin + (index_size); 65 assert( it != begin ); 66 for( ; it-- != begin ; ) std::cout << *it << " "; 67 std::cout << "\n"; 68 69 std::cout << "Iterate backward with stride 2 : "; 70 it = begin + (index_size - 1); 71 for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " "; 72 std::cout << "\n"; 73 74 75The output is: 76 77[pre 78The original range is : 0 1 2 3 4 5 6 7 8 9 79The reindexing scheme is : 9 8 7 6 80The permutated range is : 9 8 7 6 81Elements at even indices in the permutation : 9 7 82Permutation backwards : 6 7 8 9 83Iterate backward with stride 2 : 6 8 84] 85 86The source code for this example can be found 87[example_link permutation_iter_example.cpp..here]. 88 89[h2 Reference] 90 91[h3 Synopsis] 92 93 template< class ElementIterator 94 , class IndexIterator 95 , class ValueT = use_default 96 , class CategoryT = use_default 97 , class ReferenceT = use_default 98 , class DifferenceT = use_default > 99 class permutation_iterator 100 { 101 public: 102 permutation_iterator(); 103 explicit permutation_iterator(ElementIterator x, IndexIterator y); 104 105 template< class OEIter, class OIIter, class V, class C, class R, class D > 106 permutation_iterator( 107 permutation_iterator<OEIter, OIIter, V, C, R, D> const& r 108 , typename enable_if_convertible<OEIter, ElementIterator>::type* = 0 109 , typename enable_if_convertible<OIIter, IndexIterator>::type* = 0 110 ); 111 reference operator*() const; 112 permutation_iterator& operator++(); 113 ElementIterator const& base() const; 114 private: 115 ElementIterator m_elt; // exposition only 116 IndexIterator m_order; // exposition only 117 }; 118 119 template <class ElementIterator, class IndexIterator> 120 permutation_iterator<ElementIterator, IndexIterator> 121 make_permutation_iterator( ElementIterator e, IndexIterator i); 122 123 124[h3 Requirements] 125 126`ElementIterator` shall model Random Access Traversal Iterator. 127`IndexIterator` shall model Readable Iterator. The value type of 128the `IndexIterator` must be convertible to the difference type of 129`ElementIterator`. 130 131[h3 Concepts] 132 133`permutation_iterator` models the same iterator traversal concepts 134as `IndexIterator` and the same iterator access concepts as 135`ElementIterator`. 136 137If `IndexIterator` models Single Pass Iterator and 138`ElementIterator` models Readable Iterator then 139`permutation_iterator` models Input Iterator. 140 141If `IndexIterator` models Forward Traversal Iterator and 142`ElementIterator` models Readable Lvalue Iterator then 143`permutation_iterator` models Forward Iterator. 144 145If `IndexIterator` models Bidirectional Traversal Iterator and 146`ElementIterator` models Readable Lvalue Iterator then 147`permutation_iterator` models Bidirectional Iterator. 148 149If `IndexIterator` models Random Access Traversal Iterator and 150`ElementIterator` models Readable Lvalue Iterator then 151`permutation_iterator` models Random Access Iterator. 152 153`permutation_iterator<E1, X, V1, C2, R1, D1>` is interoperable 154with `permutation_iterator<E2, Y, V2, C2, R2, D2>` if and only if 155`X` is interoperable with `Y` and `E1` is convertible 156to `E2`. 157 158[h3 Operations] 159 160In addition to those operations required by the concepts that 161`permutation_iterator` models, `permutation_iterator` provides the 162following operations. 163 164 permutation_iterator(); 165 166[*Effects: ] Default constructs `m_elt` and `m_order`. 167 168 169 explicit permutation_iterator(ElementIterator x, IndexIterator y); 170 171[*Effects: ] Constructs `m_elt` from `x` and `m_order` from `y`. 172 173 174 template< class OEIter, class OIIter, class V, class C, class R, class D > 175 permutation_iterator( 176 permutation_iterator<OEIter, OIIter, V, C, R, D> const& r 177 , typename enable_if_convertible<OEIter, ElementIterator>::type* = 0 178 , typename enable_if_convertible<OIIter, IndexIterator>::type* = 0 179 ); 180 181[*Effects: ] Constructs `m_elt` from `r.m_elt` and 182 `m_order` from `y.m_order`. 183 184 185 reference operator*() const; 186 187[*Returns: ] `*(m_elt + *m_order)` 188 189 190 permutation_iterator& operator++(); 191 192[*Effects: ] `++m_order`[br] 193[*Returns: ] `*this` 194 195 196 ElementIterator const& base() const; 197 198[*Returns: ] `m_order` 199 200 201 template <class ElementIterator, class IndexIterator> 202 permutation_iterator<ElementIterator, IndexIterator> 203 make_permutation_iterator(ElementIterator e, IndexIterator i); 204 205[*Returns: ] `permutation_iterator<ElementIterator, IndexIterator>(e, i)` 206 207[endsect] 208