Boost C++ 库

……世界上最受推崇且设计最专业的 C++ 库项目之一。 — Herb Sutter 和 Andrei Alexandrescu，《C++ 编码规范》

排列迭代器 - Boost C++ 函数库

排列迭代器

作者 Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek
联系方式 dave@boost-consulting.com, jsiek@osl.iu.edu
组织 Boost Consulting, 印第安纳大学 Open Systems Lab
日期 2006-09-11
版权 Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003.
摘要 置换迭代器适配器（permutation iterator adaptor）提供了给定范围的一种置换视图。也就是说，该视图包含了给定范围内的所有元素，但顺序可能不同。

介绍

该适配器接收两个参数

  • 一个指向范围 V 的迭代器，排列将应用于该范围 V。
  • 定义 V 元素如何排列的重索引方案。

请注意，置换迭代器并不局限于对给定范围 V 进行严格的置换。重索引迭代器的起始（begin）和结束（end）之间的距离允许小于范围 V 的大小，在这种情况下，置换迭代器仅提供 V 的子范围的置换。索引也不需要是唯一的。在同样的语境下，必须指出的是，置换迭代器结束后的位置（past the end）完全由索引的结束迭代器定义。

参考

template< class ElementIterator
        , class IndexIterator
        , class ValueT        = use_default
        , class CategoryT     = use_default
        , class ReferenceT    = use_default
        , class DifferenceT   = use_default >
class permutation_iterator
{
public:
  permutation_iterator();
  explicit permutation_iterator(ElementIterator x, IndexIterator y);

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

template <class ElementIterator, class IndexIterator>
permutation_iterator<ElementIterator, IndexIterator>
make_permutation_iterator( ElementIterator e, IndexIterator i);

permutation_iteratorrequirements

ElementIterator应模拟随机访问遍历迭代器（Random Access Traversal Iterator）。IndexIterator应模拟可读迭代器（Readable Iterator）。其值类型（value type）IndexIterator必须可转换为以下类型的差值类型（difference type）：ElementIterator.

permutation_iterator模型

permutation_iterator模拟与以下相同的迭代器遍历概念：IndexIterator以及与以下相同的迭代器访问概念：ElementIterator.

如果IndexIterator模拟单遍迭代器（Single Pass Iterator）且ElementIterator模拟可读迭代器（Readable Iterator）则permutation_iterator模拟输入迭代器（Input Iterator）。

如果IndexIterator模拟前向遍历迭代器（Forward Traversal Iterator）且ElementIterator模拟可读左值迭代器（Readable Lvalue Iterator）则permutation_iterator模拟前向迭代器（Forward Iterator）。

如果IndexIterator模拟双向遍历迭代器（Bidirectional Traversal Iterator）且ElementIterator模拟可读左值迭代器（Readable Lvalue Iterator）则permutation_iterator模拟双向迭代器（Bidirectional Iterator）。

如果IndexIterator模拟随机访问遍历迭代器（Random Access Traversal Iterator）且ElementIterator模拟可读左值迭代器（Readable Lvalue Iterator）则permutation_iterator模拟随机访问迭代器（Random Access Iterator）。

permutation_iterator<E1, X, V1, C2, R1, D1>与permutation_iterator<E2, Y, V2, C2, R2, D2>当且仅当X与YandE1可转换为E2.

permutation_iterator操作

除了概念所要求的那些操作外，permutation_iterator满足，permutation_iterator还提供了以下操作。

permutation_iterator();

效果默认构造m_eltandm_order.

explicit permutation_iterator(ElementIterator x, IndexIterator y);

效果构造m_elttemplate< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );xandm_ordertemplate< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );y. 
template< class OEIter, class OIIter, class V, class C, class R, class D >
permutation_iterator(
    permutation_iterator<OEIter, OIIter, V, C, R, D> const& r
    , typename enable_if_convertible<OEIter, ElementIterator>::type* = 0
    , typename enable_if_convertible<OIIter, IndexIterator>::type* = 0
    );
效果构造m_elttemplate< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );r.m_eltandm_ordertemplate< class PtrSequence > void transfer( iterator before, typename PtrSequence::iterator object, PtrSequence& from );y.m_order.

reference operator*() const;

返回*(m_elt + *m_order)

permutation_iterator& operator++();

效果++m_order
返回*this

ElementIterator const& base() const;

返回m_order 
template <class ElementIterator, class IndexIterator>
permutation_iterator<ElementIterator, IndexIterator>
make_permutation_iterator(ElementIterator e, IndexIterator i);
返回permutation_iterator<ElementIterator, IndexIterator>(e, i)

示例

using namespace boost;
int i = 0;

typedef std::vector< int > element_range_type;
typedef std::list< int > 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< element_range_type::iterator, index_type::iterator > 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 << "The original range is : ";
std::copy( elements.begin(), elements.end(), std::ostream_iterator< int >( std::cout, " " ) );
std::cout << "\n";

std::cout << "The reindexing scheme is : ";
std::copy( indices.begin(), indices.end(), std::ostream_iterator< int >( std::cout, " " ) );
std::cout << "\n";

std::cout << "The permutated range is : ";
std::copy( begin, end, std::ostream_iterator< int >( std::cout, " " ) );
std::cout << "\n";

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

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

std::cout << "Iterate backward with stride 2 : ";
it = begin + (index_size - 1);
for(i = 0 ; i < index_size / 2 ; ++i, it-=2 ) std::cout << *it << " ";
std::cout << "\n";

找到。输出是

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

该示例的源代码可以在这里找到。

查看文档源码。由 Docutils 从 reStructuredText 源码生成。