計數迭代器

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.
概要:

你如何使用 std::copy() 將0-100填入一個 vector? 內建的整數類型唯一不能滿足的迭代器操作就是缺少一個返回整數當前值的 operator*(). 計數迭代器適配器為需要包裝的類型增加這個至關重要的功能。你不僅可以將計數迭代器適配器用於整數類型,任何可遞增類型均可適用。

counting_iterator 改編一個對象,為其增加一個 operator*,返回該對象的當前值。所有其它迭代器操作均前轉至被改編的對象。

目錄

counting_iterator 概要

template <
class Incrementable
, class CategoryOrTraversal = use_default
, class Difference = use_default
>
class counting_iterator
{
public:
typedef Incrementable value_type;
typedef const Incrementable& reference;
typedef const Incrementable* pointer;
typedef /* 見下文 */ difference_type;
typedef /* 見下文 */ iterator_category;

counting_iterator();
counting_iterator(counting_iterator const& rhs);
explicit counting_iterator(Incrementable x);
Incrementable const& base() const;
reference operator*() const;
counting_iterator& operator++();
counting_iterator& operator--();
private:
Incrementable m_inc; // exposition
};

如果 Difference 參數為 use_defaultdifference_type 為一個未指定的有符號整型類型。否則 difference_typeDifference.

iterator_category 根據以下算法決定:

if (CategoryOrTraversal 不是 use_default)
return CategoryOrTraversal
else if (numeric_limits<Incrementable>::is_specialized)
return iterator-category(
random_access_traversal_tag, Incrementable, const Incrementable&)
else
return iterator-category(
iterator_traversal<Incrementable>::type,
Incrementable, const Incrementable&)
[註:我們建議實現
operator- 和一個 difference_type 以避免當 std::numeric_limits<Incrementable>::is_specialized 為 true 時發生溢出。]

counting_iterator 的要求

Incrementable 參數應該是可複製構造的和可賦值的。

如果 iterator_category 可轉換為 forward_iterator_tagforward_traversal_tag, 則以下寫法必須是合法的:

Incrementable i, j;
++i; // 前綴遞增
i == j; // operator==

如果 iterator_category 可轉換為 bidirectional_iterator_tagbidirectional_traversal_tag, 則以下表達式也必須是合法的:

--i

如果 iterator_category 可轉換為 random_access_iterator_tagrandom_access_traversal_tag, 則以下表達式也必須有效:

counting_iterator::difference_type n;
i += n;
n = i - j;
i < j;

counting_iterator 的模型

counting_iterator 的特化類符合可讀左值迭代器。此外,它們還符合可以由其 iterator_category 參數轉換得到的迭代器 tags 還對應的概念。還有,如果 CategoryOrTraversal 不是 use_default,則 counting_iterator 符合迭代器 tag CategoryOrTraversal 所對應的概念。否則,如果 numeric_limits<Incrementable>::is_specialized, 則 counting_iterator 符合隨機訪問遍歷迭代器。否則,counting_iterator 符合 Incrementable 所符合的迭代器遍歷概念。

counting_iterator<X,C1,D1>counting_iterator<Y,C2,D2> 可交互,當且僅當 XY 是可交互的。

counting_iterator 的操作

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

counting_iterator();

要求: Incrementable 是可缺省構造的。
作用: 缺省構造成員 m_inc.

counting_iterator(counting_iterator const& rhs);

作用: rhs.m_inc 構造成員 m_inc.

explicit counting_iterator(Incrementable x);

作用: x 構造成員 m_inc.

reference operator*() const;

返回 m_inc

counting_iterator& operator++();

作用: ++m_inc
返回: *this

counting_iterator& operator--();

作用: --m_inc
返回: *this

Incrementable const& base() const;

返回: m_inc
template <class Incrementable>
counting_iterator<Incrementable> make_counting_iterator(Incrementable x);
返回: 一個 counting_iterator<Incrementable> 實例,其 current 構造自 x.

例子

這個例子用一些數字填充一個數組,再用第一個數組的指針填充第二個數組,兩個任務均使用 counting_iterator. 最後用 indirect_iterator 通過對第二個數組的間接訪問打印出第一個數組中的數字。

int N = 7;
std::vector<int> numbers;
typedef std::vector<int>::iterator n_iter;
std::copy(boost::counting_iterator<int>(0),
boost::counting_iterator<int>(N),
std::back_inserter(numbers));

std::vector<std::vector<int>::iterator> pointers;
std::copy(boost::make_counting_iterator(numbers.begin()),
boost::make_counting_iterator(numbers.end()),
std::back_inserter(pointers));

std::cout << "indirectly printing out the numbers from 0 to "
<< N << std::endl;
std::copy(boost::make_indirect_iterator(pointers.begin()),
boost::make_indirect_iterator(pointers.end()),
std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

輸出結果是:

indirectly printing out the numbers from 0 to 7
0 1 2 3 4 5 6

該例子的源代碼請見 這裡