迭代器適配器

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

iterator_adaptor 類模板的每個特化類都派生自 iterator_facade 的某個特化類。iterator_facade 所需要的各個核心接口函數依據 iterator_adaptorBase 模板參數而實現。派生自 iterator_adaptor 的類通常要重定義某些核心接口函數來調整 Base 類型的行為。這個派生類是否符合某個標準迭代器概念,取決於 Base 類型所支持的操作以及 iterator_facade 的哪些核心接口函數被 Derived 類重新定義。

目錄

簡介

iterator_adaptor 類模板通過改編某個 Base1 類型來創建一個新的迭代器。iterator_adaptor 的實例派生自一個對應的 iterator_facade 的實例,並依據 Base 類型實現核心行為。基本上,iterator_adaptor 只是將所有操作前轉至 Base 類型的一個實例,該實例被作為一個成員保存。

[1] (1, 2) 這裡的術語 "Base" 並不是指基類,也沒有使用派生。我們跟隨了標準庫的帶領,標準庫為 reverse_iterator 適配器提供了 base() 函數來訪問底層的迭代器對象。

iterator_adaptor 的用戶創建了一個派生自某個 iterator_adaptor 實例的類,然後有選擇地重新定義在 iterator_facade 的核心要求表格中所列的某些核心成員函數。Base 類型不必完全符合迭代器的所有要求;它只須支持那些被 iterator_adaptor 的核心接口函數使用而又沒有在用戶的派生類中重新定義的操作就可以了。

iterator_adaptor 有幾個模板參數的缺省值是 use_default. 這允許用戶使用缺省參數,即使他想在後面的參數列表中指定參數。還有,對應的關聯類型缺省值有些複雜,需要用元編程來計算它們,而 use_default 可以幫助簡化實現。最後,use_default 類型的標識符沒有留作非未指明的,這是因為規定該標識符可以有助於突出 Reference 模板參數並不總是與迭代器的 reference 類型一致這一事實,並防止用戶由於這個假設而出錯。

參考

template <
class Derived
, class Base
, class Value = use_default
, class CategoryOrTraversal = use_default
, class Reference = use_default
, class Difference = use_default
>
class iterator_adaptor
: public iterator_facade<Derived, V', C', R', D'> // 請見 詳細說明 { friend class iterator_core_access; public: iterator_adaptor(); explicit iterator_adaptor(Base const& iter); typedef Base base_type; Base const& base() const; protected: typedef iterator_adaptor iterator_adaptor_; Base const& base_reference() const; Base& base_reference(); private: // iterator_facade 的核心迭代器接口 typename iterator_adaptor::reference dereference() const; template < class OtherDerived, class OtherIterator, class V, class C, class R, class D > bool equal(iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& x) const; void advance(typename iterator_adaptor::difference_type n); void increment(); void decrement(); template < class OtherDerived, class OtherIterator, class V, class C, class R, class D > typename iterator_adaptor::difference_type distance_to( iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& y) const; private: Base m_iterator; // exposition only };

iterator_adaptor 的要求

static_cast<Derived*>(iterator_adaptor*) 必須是合法的。Base 參數必須是可賦值和可複製構造的。

iterator_adaptor 的基類參數

上面的 iterator_adaptor 摘要中的基類 iterator_facadeV', C', R', 和 D'  參數定義如下:

V' = if (Value 為 use_default)
return iterator_traits<Base>::value_type
else
return Value

C' = if (CategoryOrTraversal 為 use_default)
return iterator_traversal<Base>::type
else
return CategoryOrTraversal

R' = if (Reference 為 use_default)
if (Value 為 use_default)
return iterator_traits<Base>::reference
else
return Value&
else
return Reference

D' = if (Difference 為 use_default)
return iterator_traits<Base>::difference_type
else
return Difference

iterator_adaptor 的公有操作

iterator_adaptor();

要求: Base 類型必須是可缺省構造的。
返回: 一個 iterator_adaptor 實例,其中的 m_iterator 為缺省構造。

explicit iterator_adaptor(Base const& iter);

返回: 一個 iterator_adaptor 實例,其中的 m_iteratoriter 複製構造。

Base const& base() const;

返回: m_iterator

iterator_adaptor 的保護成員函數

Base const& base_reference() const;

返回: m_iterator 的一個常量引用。

Base& base_reference();

返回: m_iterator 的一個非常量引用。

iterator_adaptor 的私有成員函數

typename iterator_adaptor::reference dereference() const;

返回: *m_iterator
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
bool equal(iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& x) const;
返回: m_iterator == x.base()

void advance(typename iterator_adaptor::difference_type n);

作用: m_iterator += n;

void increment();

作用: ++m_iterator;

void decrement();

作用: --m_iterator;
template <
class OtherDerived, class OtherIterator, class V, class C, class R, class D
>
typename iterator_adaptor::difference_type distance_to(
iterator_adaptor<OtherDerived, OtherIterator, V, C, R, D> const& y) const;
返回: y.base() - m_iterator

指南和例子

在本節中,我們將進一步對我們在 iterator_facade 指南 中所開發的 node_iter 類模板進行精化。如果你還沒有讀過那篇文章,你應該現在回過頭去看看,因為我們將要補充那個例子中所缺少的東西。

你可能會不同意,但 node_iterator 底層的 node_base* 對像本身就是一個迭代器,正像其它所有的指針一樣。如果我們從迭代器的觀點來近距離觀察這個指針,我們可以看到,它與我們所構建的 node_iterator 有很多相同點。首先,它們有很多相同的關聯類型(value_type, reference, pointer, 和 difference_type)。其次,有些核心功能也一樣:node_iterator 的 operator*operator== 都是返回其底層指針的相同操作的執行結果(通過 node_iteratordereferenceequal 成員函數)。node_base*node_iterator 間唯一真正不同的行為發生在它們被遞增的時候: node_iterator 採用 m_next 指針,而 node_base* 則遞增一個地址偏移量。

這帶來了一種模式,即在某個類似於迭代器的類型(Base1 類型)的基礎之上構建一個迭代器,只需要對底層類型的行為做出少量的修改,這就是 iterator_adaptor 所實現的模式。使用 iterator_adaptor 和使用 iterator_facade 非常相似,但由於 iterator_adaptor 盡可能地模仿其 Base 類型的行為,所以我們既不需要提供一個 Value 參數,也不用實現除了 increment 之外的任何核心行為。node_iter 的實現可以簡化為:

template <class Value>
class node_iter
: public boost::iterator_adaptor<
node_iter<Value> // Derived
, Value* // Base
, boost::use_default // Value
, boost::forward_traversal_tag // CategoryOrTraversal
>
{
private:
struct enabler {}; // 避免誤用的私有類型

public:
node_iter()
: node_iter::iterator_adaptor_(0) {}

explicit node_iter(Value* p)
: node_iter::iterator_adaptor_(p) {}

template <class OtherValue>
node_iter(
node_iter<OtherValue> const& other
, typename boost::enable_if<
boost::is_convertible<OtherValue*,Value*>
, enabler
>::type = enabler()
)
: node_iter::iterator_adaptor_(other.base()) {}

private:
friend class boost::iterator_core_access;
void increment() { this->base_reference() = this->base()->next(); }
};

請留意這裡對 node_iter::iterator_adaptor_ 的使用:iterator_adaptor 定義了一個嵌套的 iterator_adaptor_ 類型來代表它自己本身,使得我們可以方便地引用這個複雜的基類 node_iter<Value>. [註:該方法已知不能用於 Borland C++ 5.6.4 和 Metrowerks CodeWarrior 9.0 之前的版本]

在 這裡 你可以看到一個例子程序,測試了這個版本的節點迭代器。

在這個 node_iter 例子中,並不強制一定要將 boost::use_default 作為 iterator_adaptorValue 參數;我們可以只是將傳入的 node_iterValue 順著傳給 iterator_adaptor, 而且還更短!多數由 iterator_adaptor 構建的迭代器類模板是以另一個迭代器類型為參數的,而不是以它的 value_type 為參數。例如,boost::reverse_iterator 接受一個迭代器類型的參數,並以相反的順序進行遍歷,由於原迭代器和反序迭代器具有完全相同的關聯類型,所以iterator_adaptor 將這些缺省類型委託給它的 Base,以縮短 boost::reverse_iterator 的實現,不需要這樣寫四次:

std::iterator_traits<Iterator>::some-associated-type

我們建議你重溫一下 reverse_iterator 的文檔和實現,以及其它 Boost 特化迭代器適配器,以對可以用 iterator_adaptor 做些什麼有所瞭解。特別是,看一下 transform_iterator, 它可能是最簡明的適配器,還有 counting_iterator, 它示範了 iterator_adaptorBase 類型不一定要是一個迭代器。