過濾迭代器

Author: David Abrahams, Jeremy Siek, Thomas Witt
Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@ive.uni-hannover.de
Organization: Boost Consulting, Indiana University Open Systems Lab, University of Hanover Institute for Transport Railway Operation and Construction
Date: 2006-09-11
Copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.
概要: 過濾迭代器適配器創建一個迭代器區間的視圖,該區間中的某些元素會被跳過。跳過哪些元素是由一個謂詞函數對像來控制的。該謂詞被應用於某個元素,如果返回 true 則該元素被保留,如果返回 false 則該元素被跳過。跳過了多個元素後,過濾適配器需要知道何時停止,以防止越過底層迭代器區間的末尾。因此一個過濾迭代器要由一對迭代器來構造,這對迭代器表示了被遍歷的未過濾序列的元素範圍。

目錄

filter_iterator 概要

template <class Predicate, class Iterator>
class filter_iterator
{
public:
typedef iterator_traits<Iterator>::value_type value_type;
typedef iterator_traits<Iterator>::reference reference;
typedef iterator_traits<Iterator>::pointer pointer;
typedef iterator_traits<Iterator>::difference_type difference_type;
typedef /* 見下文 */ iterator_category;

filter_iterator();
filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
filter_iterator(Iterator x, Iterator end = Iterator());
template<class OtherIterator>
filter_iterator(
filter_iterator<Predicate, OtherIterator> const& t
, typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition
);
Predicate predicate() const;
Iterator end() const;
Iterator const& base() const;
reference operator*() const;
filter_iterator& operator++();
private:
Predicate m_pred; // exposition only
Iterator m_iter; // exposition only
Iterator m_end; // exposition only
};

如果 Iterator 符合可讀左值迭代器及雙向遍歷迭代器,則 iterator_category 可轉換為 std::bidirectional_iterator_tag. 否則,如果 Iterator 符合可讀左值迭代器及前向遍歷迭代器,則 iterator_category 可轉換為 std::forward_iterator_tag. 否則 iterator_category 可轉換為 std::input_iterator_tag.

filter_iterator 的要求

Iterator 參數應滿足可讀迭代器和單遍迭代器的要求,或者滿足輸入迭代器的要求。

Predicate 參數必須是可賦值、可複製構造的,且表達式 p(x) 必須有效,其中 p 為類型 Predicate 的一個對象,x 為類型 iterator_traits<Iterator>::value_type 的對象,而 p(x) 的類型必須可轉換為 bool.

filter_iterator 的模型

filter_iterator 所符合的概念取決於其 Iterator 參數所符合的概念,如下表所示:

如果 Iterator 符合 則 filter_iterator 符合
單遍迭代器 單遍迭代器
前向遍歷迭代器 前向遍歷迭代器
雙向遍歷迭代器 雙向遍歷迭代器
如果 Iterator 符合 則 filter_iterator 符合
可讀迭代器 可讀迭代器
可寫迭代器 可寫迭代器
左值迭代器 左值迭代器
如果 Iterator 符合 則 filter_iterator 符合
可讀迭代器,單遍迭代器 輸入迭代器
可讀迭代器,前向遍歷迭代器 前向迭代器
可寫迭代器,前向遍歷迭代器 非常量前向迭代器
可寫迭代器,雙向遍歷迭代器 非常量雙向迭代器

filter_iterator<P1, X>filter_iterator<P2, Y> 可交互,當且僅當 XY 是可交互的。

filter_iterator 的操作

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

filter_iterator();

要求: PredicateIterator 必須是可缺省構造的。
作用: 構造一個 filter_iterator,其中``m_pred``, m_iter, 和 m_end 成員都是缺省構造的。

filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());

作用: 構造一個 filter_iterator,其中 m_iter 要麼是區間 [x,end) 中的第一個滿足 f(*m_iter) == true 的位置,要麼``m_iter == end``. 成員 m_pred 構造自 fm_end 構造自 end.

filter_iterator(Iterator x, Iterator end = Iterator());

要求: Predicate 必須是可缺省構造的,且 Predicate 是一個類類型(不是函數指針)。
作用: 構造一個 filter_iterator,其中 m_iter 要麼是區間 [x,end) 中的第一個滿足 m_pred(*m_iter) == true 的位置,要麼``m_iter == end``. 成員 m_pred 是缺省構造的。
template <class OtherIterator>
filter_iterator(
filter_iterator<Predicate, OtherIterator> const& t
, typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition
);``
要求: OtherIterator 可隱式轉換為 Iterator.
作用: 構造一個過濾迭代器,其成員複製自 t.

Predicate predicate() const;

返回: m_pred

Iterator end() const;

返回: m_end

Iterator const& base() const;

返回: m_iterator

reference operator*() const;

返回: *m_iter

filter_iterator& operator++();

作用: 遞增 m_iter 並持續遞增至要麼 m_iter == m_end,要麼 m_pred(*m_iter) == true.
返回: *this
 
template <class Predicate, class Iterator>
filter_iterator<Predicate,Iterator>
make_filter_iterator(Predicate f, Iterator x, Iterator end = Iterator());
返回: filter_iterator<Predicate,Iterator>(f, x, end)
template <class Predicate, class Iterator>
filter_iterator<Predicate,Iterator>
make_filter_iterator(Iterator x, Iterator end = Iterator());
返回: filter_iterator<Predicate,Iterator>(x, end)

例子

這個例子分別使用了 filter_iteratormake_filter_iterator 來輸出一個整數數組中的正整數。然後再用 make_filter_iterator 來輸出大於 -2 的整數。

struct is_positive_number {
bool operator()(int x) { return 0 < x; }
};

int main()
{
int numbers_[] = { 0, -1, 4, -3, 5, 8, -2 };
const int N = sizeof(numbers_)/sizeof(int);

typedef int* base_iterator;
base_iterator numbers(numbers_);

// 使用 filter_iterator 的例子
typedef boost::filter_iterator<is_positive_number, base_iterator>
FilterIter;

is_positive_number predicate;
FilterIter filter_iter_first(predicate, numbers, numbers + N);
FilterIter filter_iter_last(predicate, numbers + N, numbers + N);

std::copy(filter_iter_first, filter_iter_last, std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

// 使用 make_filter_iterator() 的例子
std::copy(boost::make_filter_iterator<is_positive_number>(numbers, numbers + N),
boost::make_filter_iterator<is_positive_number>(numbers + N, numbers + N),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

// 另一個使用 make_filter_iterator() 的例子
std::copy(
boost::make_filter_iterator(
std::bind2nd(std::greater<int>(), -2)
, numbers, numbers + N)

, boost::make_filter_iterator(
std::bind2nd(std::greater<int>(), -2)
, numbers + N, numbers + N)

, std::ostream_iterator<int>(std::cout, " ")
);

std::cout << std::endl;

return boost::exit_success;
}

輸出結果是:

4 5 8
4 5 8
0 -1 4 5 8

這個例子的源代碼請見 這裡