ceph/src/boost/libs/iterator/doc/quickbook/permutation_iterator.qbk

   1
   2 [section:permutation Permutation Iterator]
   3
   4 The permutation iterator adaptor provides a permuted view of a given
   5 range. That is, the view includes every element of the given range but
   6 in a potentially different order. The adaptor takes two arguments:
   7
   8 * an iterator to the range V on which the permutation
   9   will be applied
  10 * the reindexing scheme that defines how the
  11   elements of V will be permuted.
  12
  13 Note that the permutation iterator is not limited to strict
  14 permutations of the given range V.  The distance between begin and end
  15 of the reindexing iterators is allowed to be smaller compared to the
  16 size of the range V, in which case the permutation iterator only
  17 provides a permutation of a subrange of V.  The indexes neither need
  18 to be unique. In this same context, it must be noted that the past the
  19 end permutation iterator is completely defined by means of the
  20 past-the-end iterator to the indices.
  21
  22 [h2 Example]
  23
  24     using namespace boost;
  25     int i = 0;
  26
  27     typedef std::vector< int > element_range_type;
  28     typedef std::list< int > index_type;
  29
  30     static const int element_range_size = 10;
  31     static const int index_size = 4;
  32
  33     element_range_type elements( element_range_size );
  34     for(element_range_type::iterator el_it = elements.begin() ; el_it != elements.end() ; ++el_it)
  35       *el_it = std::distance(elements.begin(), el_it);
  36
  37     index_type indices( index_size );
  38     for(index_type::iterator i_it = indices.begin() ; i_it != indices.end() ; ++i_it )
  39       *i_it = element_range_size - index_size + std::distance(indices.begin(), i_it);
  40     std::reverse( indices.begin(), indices.end() );
  41
  42     typedef permutation_iterator< element_range_type::iterator, index_type::iterator > permutation_type;
  43     permutation_type begin = make_permutation_iterator( elements.begin(), indices.begin() );
  44     permutation_type it = begin;
  45     permutation_type end = make_permutation_iterator( elements.begin(), indices.end() );
  46
  47     std::cout << "The original range is : ";
  48     std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) );
  49     std::cout << "\n";
  50
  51     std::cout << "The reindexing scheme is : ";
  52     std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) );
  53     std::cout << "\n";
  54
  55     std::cout << "The permutated range is : ";
  56     std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) );
  57     std::cout << "\n";
  58
  59     std::cout << "Elements at even indices in the permutation : ";
  60     it = begin;
  61     for(i = 0; i < index_size / 2 ; ++i, it+=2 ) std::cout << *it << " ";
  62     std::cout << "\n";
  63
  64     std::cout << "Permutation backwards : ";
  65     it = begin + (index_size);
  66     assert( it != begin );
  67     for( ; it-- != begin ; ) std::cout << *it << " ";
  68     std::cout << "\n";
  69
  70     std::cout << "Iterate backward with stride 2 : ";
  71     it = begin + (index_size - 1);
  72     for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " ";
  73     std::cout << "\n";
  74
  75
  76 The output is:
  77
  78     The original range is : 0 1 2 3 4 5 6 7 8 9
  79     The reindexing scheme is : 9 8 7 6
  80     The permutated range is : 9 8 7 6
  81     Elements at even indices in the permutation : 9 7
  82     Permutation backwards : 6 7 8 9
  83     Iterate backward with stride 2 : 6 8
  84
  85
  86 The source code for this example can be found
  87 [@../example/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
 128 the `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
 134 as `IndexIterator` and the same iterator access concepts as
 135 `ElementIterator`.
 136
 137 If `IndexIterator` models Single Pass Iterator and
 138 `ElementIterator` models Readable Iterator then
 139 `permutation_iterator` models Input Iterator.
 140
 141 If `IndexIterator` models Forward Traversal Iterator and
 142 `ElementIterator` models Readable Lvalue Iterator then
 143 `permutation_iterator` models Forward Iterator.
 144
 145 If `IndexIterator` models Bidirectional Traversal Iterator and
 146 `ElementIterator` models Readable Lvalue Iterator then
 147 `permutation_iterator` models Bidirectional Iterator.
 148
 149 If `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
 154 with `permutation_iterator<E2, Y, V2, C2, R2, D2>` if and only if
 155 `X` is interoperable with `Y` and `E1` is convertible
 156 to `E2`.
 157
 158 [h3 Operations]
 159
 160 In addition to those operations required by the concepts that
 161 `permutation_iterator` models, `permutation_iterator` provides the
 162 following 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]