排列迭代器

Author: Toon Knapen, David Abrahams, Roland Richter, Jeremy Siek
Contact: dave@boost-consulting.com, jsiek@osl.iu.edu
Organization: Boost Consulting, Indiana University Open Systems Lab
Date: 2006-09-11
Copyright: Copyright Toon Knapen, David Abrahams, Roland Richter, and Jeremy Siek 2003.
概要: 排列迭代器適配器提供一個給定區間的重排列視圖。即,該視圖包含給定區間中的每個元素,但排列的順序不同。

目錄

簡介

該適配器接受兩個參數:

  • 指向進行重新排列的區間 V 的一個迭代器
  • 定義如何重新排列 V 中的元素的方案

注意,排列迭代器並不限於對給定區間 V 進行嚴格的排列。重排列迭代器的開始至結尾的距離可以小於區間 V 的大小,這樣排列迭代器只是提供了對 V 的一個子區間的排列。索引也不需要是唯一的。在這種情況下,必須要注意排列迭代器的末尾要依據該索引的迭代器的末尾來完整地定義。

參考

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_iterator 的要求

ElementIterator 應符合隨機訪問遍歷迭代器。IndexIterator 應符合可讀迭代器。IndexIterator 的值類型必須可轉換為 ElementIterator 的距離類型。

permutation_iterator 的模型

permutation_iterator 符合與 IndexIterator 一樣的迭代器遍歷概念以及與 ElementIterator 一樣的迭代器訪問概念。

如果 IndexIterator 符合單遍迭代器且 ElementIterator 符合可讀迭代器,則 permutation_iterator 符合輸入迭代器。

如果 IndexIterator 符合前向遍歷迭代器且 ElementIterator 符合可讀左值迭代器,則 permutation_iterator 符合前向迭代器。

如果 IndexIterator 符合雙向遍歷迭代器且 ElementIterator 符合可讀左值迭代器,則 permutation_iterator 符合雙向迭代器。

如果 IndexIterator 符合隨機訪問遍歷迭代器且 ElementIterator 符合可讀左值迭代器,則 permutation_iterator 符合隨機訪問迭代器。

permutation_iterator<E1, X, V1, C2, R1, D1>permutation_iterator<E2, Y, V2, C2, R2, D2> 可交互,當且僅當 XY 是可交互的且 E1 可轉換為 E2.

permutation_iterator 的操作

除了 permutation_iterator 所符合的概念所要求的操作以外,permutation_iterator 還提供了以下操作。

permutation_iterator();

作用: 缺省構造 m_eltm_order.

explicit permutation_iterator(ElementIterator x, IndexIterator y);

作用: x 構造 m_elt,由 y 構造 m_order.
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
);
作用: r.m_elt 構造 m_elt,由 y.m_order 構造 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

該例子的源代碼請見 這裡