迭代器的外觀

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_facade 是一個基類模板,依據少量的核心函數和關聯類型實現了標準迭代器的接口,用於派生出迭代器類。

目錄

簡介

迭代器的接口可以非常複雜,不過還是存在一個核心的接口子集,該子集對於所有不同功能的迭代器都是必須的。我們可以為迭代器列出以下核心行為:

除了以上列出的行為以外,核心接口元素還應包括一些由迭代器 traits 所聲明的關聯類型:value_type, reference, difference_type, 和 iterator_category.

迭代器外觀使用了 Curiously Recurring Template Pattern (CRTP) [Cop95],這樣用戶可以在派生類中指定 iterator_facade 的行為。以前的設計使用了策略對像來指定行為,但這種方法由於以下原因而被棄用:

  1. 策略對像拷貝的創建和銷毀會增加開銷,而現在的方法可以避免。
  2. 策略對像方法不允許對被創建的迭代器類型定制構造函數,而如果 iterator_facade 要用於其它的庫實現,該特性是必須的。
  3. 如果不使用 CRTP, 那麼標準所要求的:迭代器的 operator++ 要返回迭代器類型本身,將會導致由本庫所創建的所有迭代器都必須是iterator_facade<...> 的特化,而不能是象 indirect_iterator<T*> 這樣的類型。要創建新的參數化迭代器就必須要使用笨重的類型生成器元函數,而且一個獨立的 iterator_adaptor 層也是不可能的了。

用法

iterator_facade 的用戶應從 iterator_facade 的一個特化派生出他的迭代器類,並將該派生的迭代器類作為 iterator_facade 的第一個模板參數。其它模板參數的順序是經過仔細選擇的,以便於使用缺省值。例如,定義一個常量左值迭代器時,用戶可以傳入將迭代器的 value_type 的一個const版本作為 iterator_facadeValue 參數傳入,而省略後面的 Reference 參數。

派生的迭代器類必須定義一些成員函數來實現迭代器的核心行為。下表描述了一些依據於迭代器類型而要求必須有效的表達式。這些成員函數會有簡單的描述,更為詳細的介紹請見"迭代器外觀的要求"一節。

表達式 作用
i.dereference() 訪問所引向的值
i.equal(j) 比較與 j 的等價性
i.increment() 前進一個位置
i.decrement() 後退一個位置
i.advance(n) 前進 n 個位置
i.distance_to(j) 計算與 j 的距離

除了實現以上核心接口函數之外,一個派生自 iterator_facade 的迭代器通常還要定義幾個構造函數。為了符合標準的迭代器概念,至少要有一個複製構造函數。此外,如果迭代器類型 X 是與另一個迭代器類型 Y 可以自動互操作的(如常量迭代器和可變迭代器),那麼就必須有一個從 XY 或者從 YX 的隱式轉換(不必兩個都有),通常的實現方式就是一個轉換構造函數。最後,如果迭代器符合前向遍歷迭代器或更為強化的迭代器概念,則要求有一個缺省構造函數。

迭代器的核心訪問

iterator_facade 及其操作符的實現要能夠訪問派生類的核心成員函數。而將核心成員函數聲明為公有的,又會把實現細節暴露給了用戶。這裡使用的設計可以確保實現細節不會出現在派生迭代器類型的公有接口中。

防止直接訪問核心成員函數有兩個好處。首先,用戶不可能在要使用 value_type 的成員時無意中用到了迭代器的成員函數。這在以前的智能指針實現中是一個問題。第二個也是主要的好處是,庫的實現可以自由地將一個基於 iterator_facade 的迭代器換為手工實現的迭代器,而無需擔心破壞了要被直接訪問的公有核心成員函數的代碼。

在一個簡單的實現中,要保持派生類的核心成員函數私有,就要將 iterator_facade 的所有七個操作符聲明為友元函數。為了減輕這個負擔,我們提供了 iterator_core_access 類,它的作用是作為派生迭代器類的核心成員函數的網關。派生類的作者只需將 iterator_core_access 聲明為友元就可以讓程序庫使用他的核心成員函數了。

iterator_core_access 被實現為一個空類,只包含了私有的靜態成員函數,這些函數會調用迭代器的核心成員函數。我們不需要對這個網關協議進行標準化。請注意,即使 iterator_core_access 使用了公有的成員函數,也不會有安全漏洞,因為每個核心成員函數都保證了迭代器的不變式。

operator[]

泛型迭代器的索引操作符帶來了特殊的挑戰。隨機訪問迭代器的 operator[] 只要求返回某個可以轉換為 value_type 的東西。要求它返回一個左值會將某些當前合法的隨機訪問迭代器排除在外,這些迭代器在它的數據成員中保存了一個被引用值(如 counting_iterator), 由於 *(p+n) 是臨時迭代器 p+n 的引用,當 operator[] 返回時就會被銷毀。

用 iterator_facade 創建的可寫迭代器實現了在 issue 299 的首選方案中和在提議書 n1550 中所採用的語義:p[n] 的結果是一個可以轉換為迭代器的 value_type 的對象,且 p[n] = x 等同於 *(p + n) = x (註:該結果對象可以實現為某個包含了 p+n 的一個拷貝的代理)。這個方法對於任意的隨機訪問迭代器都可以正確工作,不管迭代器的其它實現細節。用戶如果知道更多有關他的迭代器的實現細節,也可以實現一個 operator[] 以在派生的迭代器類中返回一個左值;這樣可以向迭代器的用戶隱藏由 iterator_facade 所提供的實現。

operator->

一個可讀迭代器(或者現在的輸入迭代器)的 reference 類型並不需要真的是一個引用,只要它可以轉換為迭代器的 value_type 就行了。但是,如果 value_type 是一個類,那麼就還需要可以通過 operator-> 訪問其成員。因此,一個迭代器如果其 reference 類型不真的是一個引用,那麼就必須從它的 operator-> 返回一個代理,其中包含被引用值的拷貝。

iterator_facadeoperator->operator[] 的返回類型並沒有明確地指定。這些類型被描述為一組要求,iterator_facade 的實現必須滿足這些要求。

[Cop95] (1, 2) [Coplien, 1995] Coplien, J., Curiously Recurring Template Patterns, C++ Report, February 1995, pp. 24-27.

參考

template <
class Derived
, class Value
, class CategoryOrTraversal
, class Reference = Value&
, class Difference = ptrdiff_t
>
class iterator_facade {
public:
typedef remove_const<Value>::type value_type;
typedef Reference reference;
typedef Value* pointer;
typedef Difference difference_type;
typedef /* 見 下文 */ iterator_category;

reference operator*() const;
/* 見 下文 */ operator->() const;
/* 見 下文 */ operator[](difference_type n) const;
Derived& operator++();
Derived operator++(int);
Derived& operator--();
Derived operator--(int);
Derived& operator+=(difference_type n);
Derived& operator-=(difference_type n);
Derived operator-(difference_type n) const;
protected:
typedef iterator_facade iterator_facade_;
};

// 比較操作符
template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type // exposition
operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

// 迭代器減法
template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
/* 見 下文 */
operator-(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);

// 迭代器加法
template <class Dr, class V, class TC, class R, class D>
Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&,
typename Derived::difference_type n);

template <class Dr, class V, class TC, class R, class D>
Derived operator+ (typename Derived::difference_type n,
iterator_facade<Dr,V,TC,R,D> const&);

iterator_facadeiterator_category 成員為

iterator-category(CategoryOrTraversal, value_type, reference)

其中 iterator-category 定義如下:

iterator-category(C,R,V) :=
if (C 可轉換為 std::input_iterator_tag
|| C 可轉換為 std::output_iterator_tag
)
return C

else if (C 不可轉換為 incrementable_traversal_tag)
程序有錯誤 else return 一個滿足以下兩個約束條件的類型 X: 1. X 可轉換為 X1, 並且沒有更深的派生類,其中 X1 的定義為: if (R 為引用類型 && C 可轉換為 forward_traversal_tag) { if (C 可轉換為 random_access_traversal_tag) X1 = random_access_iterator_tag else if (C 可轉換為 bidirectional_traversal_tag) X1 = bidirectional_iterator_tag else X1 = forward_iterator_tag } else { if (C 可轉換為 single_pass_traversal_tag && R 可轉換為 V) X1 = input_iterator_tag else X1 = C } 2. category-to-traversal(X) 可轉換為也可以由 X 轉換的最深派生層次的
traversal tag type, 並且沒有更深的派生 traversal tag type.

[註:目的是允許 iterator_category 是五個原有的 category tags 之一,而可轉換為 traversal tags 之一並沒有增加信息]

上面所用的 enable_if_interoperable 模板是為了暴露不合理的操作符。這些成員操作符只有當派生類型 Dr1Dr2 是可交互的才應提供一組重載,即兩個類型中至少有一個可轉換為另一個。enable_if_interoperable 方法使用了 SFINAE 來實現當這兩個類型不可交互時將這些操作符剔除出重載函數組。這些操作符的行為就像 enable_if_interoperable 的定義如下:

template <bool, typename> enable_if_interoperable_impl
{};

template <typename T> enable_if_interoperable_impl<true,T>
{ typedef T type; };

template<typename Dr1, typename Dr2, typename T>
struct enable_if_interoperable
: enable_if_interoperable_impl<
is_convertible<Dr1,Dr2>::value || is_convertible<Dr2,Dr1>::value
, T
>
{};

iterator_facade 的要求

下表描述了對於 iterator_facadeDerived 參數的有效表達式,依賴於所屬的迭代器概念。第一列中的操作必須可以被類 iterator_core_access 的成員函數訪問。此外,static_cast<Derived*>(iterator_facade*) 應該是合法的。

在下表中,Fiterator_facade<X,V,C,R,D>,a 是類型 X 的一個對象,bc 是類型 const X 的對象,n 是類型 F::difference_type 的對象,y 是一個與 X 可交互的單遍迭代器類型的常量對象,而 z 是一個與 X 可交互的隨機訪問遍歷迭代器的常量對象。

iterator_facade 核心操作

表達式 返回類型 斷言/備註 用於實現哪些迭代器概念
c.dereference() F::reference   可讀迭代器,可寫迭代器
c.equal(y) 可轉換為 bool true 當且僅當 cy 引向同一個位置 單遍迭代器
a.increment() 未使用   可遞增迭代器
a.decrement() 未使用   雙向遍歷迭代器
a.advance(n) 未使用   隨機訪問遍歷迭代器
c.distance_to(z) 可轉換為 F::difference_type 等同於 distance(c, X(z)). 隨機訪問遍歷迭代器

iterator_facade 的操作

本節所介紹的各個操作是作為 Derived 核心接口的操作符,它們可能是不可訪問的(即私有接口)。實現中應該通過類 iterator_core_access 的成員函數來訪問這些操作符。

reference operator*() const;

返回: static_cast<Derived const*>(this)->dereference()

operator->() const; (見 下文)

返回:

如果 reference 是一個引用類型,則返回一個類型為 pointer 的對象,等同於:

&static_cast<Derived const*>(this)->dereference()

否則返回一個不確定類型的對象,以滿足 (*static_cast<Derived const*>(this))->m 等價於 (w = **static_cast<Derived const*>(this), w.m) 其中 w 是類型 value_type 的某個臨時對象。

unspecified operator[](difference_type n) const;

返回: 一個可轉換為 value_type 的對象。對於類型 value_type 的常量對像 v, 以及類型 difference_type 的對象 n, (*this)[n] = v 等價於 *(*this + n) = v, 且 static_cast<value_type const&>((*this)[n]) 等價於 static_cast<value_type const&>(*(*this + n))

Derived& operator++();

作用:
static_cast<Derived*>(this)->increment();
return *static_cast<Derived*>(this);

Derived operator++(int);

作用:
Derived tmp(static_cast<Derived const*>(this));
++*this;
return tmp;

Derived& operator--();

作用:
static_cast<Derived*>(this)->decrement();
return *static_cast<Derived*>(this);

Derived operator--(int);

作用:
Derived tmp(static_cast<Derived const*>(this));
--*this;
return tmp;

Derived& operator+=(difference_type n);

作用:
static_cast<Derived*>(this)->advance(n);
return *static_cast<Derived*>(this);

Derived& operator-=(difference_type n);

作用:
static_cast<Derived*>(this)->advance(-n);
return *static_cast<Derived*>(this);

Derived operator-(difference_type n) const;

作用:
Derived tmp(static_cast<Derived const*>(this));
return tmp -= n;
template <class Dr, class V, class TC, class R, class D>
Derived operator+ (iterator_facade<Dr,V,TC,R,D> const&,
typename Derived::difference_type n);

template <class Dr, class V, class TC, class R, class D>
Derived operator+ (typename Derived::difference_type n,
iterator_facade<Dr,V,TC,R,D> const&);
作用:
Derived tmp(static_cast<Derived const*>(this));
return tmp += n;
template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator ==(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

((Dr1 const&)lhs).equal((Dr2 const&)rhs).

否則,

((Dr2 const&)rhs).equal((Dr1 const&)lhs).

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator !=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

!((Dr1 const&)lhs).equal((Dr2 const&)rhs).

否則,

!((Dr2 const&)rhs).equal((Dr1 const&)lhs).

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator <(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) < 0.

否則,

((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) > 0.

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator <=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) <= 0.

否則,

((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) >= 0.

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator >(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) > 0.

否則,

((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) < 0.

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,bool>::type
operator >=(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回:

如果 is_convertible<Dr2,Dr1>::value

((Dr1 const&)lhs).distance_to((Dr2 const&)rhs) >= 0.

否則,

((Dr2 const&)rhs).distance_to((Dr1 const&)lhs) <= 0.

template <class Dr1, class V1, class TC1, class R1, class D1,
class Dr2, class V2, class TC2, class R2, class D2>
typename enable_if_interoperable<Dr1,Dr2,difference>::type
operator -(iterator_facade<Dr1,V1,TC1,R1,D1> const& lhs,
iterator_facade<Dr2,V2,TC2,R2,D2> const& rhs);
返回類型:

如果 is_convertible<Dr2,Dr1>::value

difference shall be iterator_traits<Dr1>::difference_type.

否則

difference shall be iterator_traits<Dr2>::difference_type

返回:

如果 is_convertible<Dr2,Dr1>::value

-((Dr1 const&)lhs).distance_to((Dr2 const&)rhs).

否則,

((Dr2 const&)rhs).distance_to((Dr1 const&)lhs).

指南和例子

在本節中我們來瀏覽一下幾個用 iterator_facade 實現的迭代器,它們用於一個多態對像鏈表的簡單例子。這個例子來自於 Keith Macdonald 在 Boost-Users 郵件列表上的 posting .

問題

假設我們已經寫了一個多態鏈表的節點基類:

# include <iostream>

struct node_base
{
node_base() : m_next(0) {}

// 每個節點負責管理它後面的所有節點
virtual ~node_base() { delete m_next; }

// 訪問後面的鏈表
node_base* next() const { return m_next; }

// 打印輸出到流
virtual void print(std::ostream& s) const = 0;

// 對值進行加倍
virtual void double_me() = 0;

void append(node_base* p)
{
if (m_next)
m_next->append(p);
else
m_next = p;
}

private:
node_base* m_next;
};

這個鏈表可以保存不同類型的對象,通過把以下模板的特化類型鏈接到一起:

template <class T>
struct node : node_base
{
node(T x)
: m_value(x)
{}

void print(std::ostream& s) const { s << this->m_value; }
void double_me() { m_value += m_value; }

private:
T m_value;
};

我們還可以用以下流操作符打印任意一個節點:

inline std::ostream& operator<<(std::ostream& s, node_base const& n)
{
n.print(s);
return s;
}

我們的第一個挑戰是,構建一個可用於此鏈表的合適的迭代器。

一個使用 iterator_facade 基本迭代器

我們將通過從 iterator_facade 派生,來構造一個 node_iterator 類,以實現這個迭代器的多數操作符。

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>

class node_iterator
: public boost::iterator_facade<...>
{
...
};

iterator_facade 的模板參數

iterator_facade 有幾個模板參數,所以我們必須決定對這些參數使用什麼樣的類型。這些參數分別是 Derived, Value, CategoryOrTraversal, Reference, 和 Difference.

Derived

由於 iterator_facade 使用了 CRTP [Cop95],所以第一個參數就是這個迭代器類名字本身,node_iterator.

Value

Value 參數決定了 node_iteratorvalue_type. 在這個例子中,我們要迭代 node_base 對象,所以 Value 應為 node_base.

CategoryOrTraversal

現在我們要決定我們的 node_iterator 應滿足哪一個 迭代器遍歷概念 了。單向鏈表只有前向鏈接,所以我們的迭代器不可能是 雙向遍歷迭代器。我們的迭代器應該可以多次遍歷同一個鏈表(不應該像 istream_iterator 那樣消耗掉它所遍歷的流),因此它肯定是 前向遍歷迭代器。所以我們在這個參數位置上傳入 boost::forward_traversal_tag 1.

[1] iterator_facade 也支持舊式的迭代器類別標誌,所以我們也可以在這裡傳入 std::forward_iterator_tag; 這樣,所得到的迭代器的 iterator_category 將是 std::forward_iterator_tag.

Reference

Reference 參數是 node_iterator 的提領操作符所返回的類型,並且應與 std::iterator_traits<node_iterator>::reference 一致。在本庫中的缺省值是 Value&; 由於 node_base& 是這個迭代器的 reference 類型的一個不錯的選擇,所以我們可以省略這個參數,或者傳入 use_default.

Difference

Difference 參數決定了如果計算兩個 node_iterator 間的距離,並且應與 std::iterator_traits<node_iterator>::difference_type 一致。在本庫中 Difference 的缺省值是 std::ptrdiff_t, 這個類型適合於計算內存中任意兩個地址間的距離,這幾乎適用於任意迭代器,所以我們也可以省略這個參數。

這樣,node_iterator 的聲明應該如下:

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>

class node_iterator
: public boost::iterator_facade<
node_iterator
, node_base
, boost::forward_traversal_tag
>
{
...
};

構造函數和數據成員

接下來我們要決定如何表示迭代器的位置。表示的方法應該採用數據成員的方式,這樣我們還要寫一個構造函數來初始化它們。node_iterator 的位置很自然地應該用一個 node_base 的指針來表示。我們需要一個構造函數,由 node_base* 構造一個迭代器,還要一個缺省構造函數以滿足 前向遍歷迭代器 的要求2。所以我們的 node_iterator 就變成了:

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>

class node_iterator
: public boost::iterator_facade<
node_iterator
, node_base
, boost::forward_traversal_tag
>
{
public:
node_iterator()
: m_node(0)
{}

explicit node_iterator(node_base* p)
: m_node(p)
{}

private:
...
node_base* m_node;
};
[2] 技術上,C++ 標準幾乎不需要一個缺省構造的迭代器,所以如果我們非常關心效率的話,也可以編寫一個不初始化 m_node 的缺省構造函數。

實現核心的操作

最後一步就是實現我們的迭代器想要滿足的概念所要求的 核心操作。根據這個 表格,我們可以看到應該實現前三行的操作,因為 node_iterator 需要滿足 可讀迭代器單遍迭代器,和 可遞增迭代器 的要求。

因此我們需要提供 dereference, equal, 和 increment 三個成員函數。我們不想讓這些成員函數成為 node_iterator 的公有接口,所以我們將它們聲明為私有的,並且授權 boost::iterator_core_access 為友元,這樣 iterator_facade 就有了一個"後門"來訪問這些核心操作了:

# include "node.hpp"
# include <boost/iterator/iterator_facade.hpp>

class node_iterator
: public boost::iterator_facade<
node_iterator
, node_base
, boost::forward_traversal_tag
>
{
public:
node_iterator()
: m_node(0) {}

explicit node_iterator(node_base* p)
: m_node(p) {}

private:
friend class boost::iterator_core_access;

void increment() { m_node = m_node->next(); }

bool equal(node_iterator const& other) const
{
return this->m_node == other.m_node;
}

node_base& dereference() const { return *m_node; }

node_base* m_node;
};

喔,一個完整且漂亮的可讀、前向遍歷的迭代器!關於如何使用它的一個例子,請見 這個程序

常量 node_iterator

現在,我們的 node_iterator 可以讓用戶既訪問 nodeprint(std::ostream&) const 成員函數,也可以訪問非常量的 double_me() 成員函數。如果我們想構建一個 常量的 node_iterator, 我們只需要做三處修改:

class const_node_iterator
: public boost::iterator_facade<
const_node_iterator
, node_base const , boost::forward_traversal_tag > { public: const_node_iterator() : m_node(0) {} explicit const_node_iterator(node_base* p) : m_node(p) {} private: friend class boost::iterator_core_access; void increment() { m_node = m_node->next(); } bool equal(const_node_iterator const& other) const { return this->m_node == other.m_node; } node_base const& dereference() const { return *m_node; }

node_base const* m_node;
};

事實上,node_iteratorconst_node_iterator 是如此的相似,應該將它們的共同代碼取出來放入到如下的模板中:

template <class Value>
class node_iter
: public boost::iterator_facade<
node_iter<Value>
, Value
, boost::forward_traversal_tag
>
{
public:
node_iter()
: m_node(0) {}

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

private:
friend class boost::iterator_core_access;

bool equal(node_iter<Value> const& other) const
{
return this->m_node == other.m_node;
}

void increment()
{ m_node = m_node->next(); }

Value& dereference() const
{ return *m_node; }

Value* m_node;
};
typedef node_iter<node_base> node_iterator;
typedef node_iter<node_base const> node_const_iterator;

互操作性

我們的 const_node_iterator 自己可以很好地工作,但如果要和 node_iterator 一起使用,就有點不太滿足要求了。例如,我們希望可以將一個 node_iterator 傳給需要 node_const_iterator 的地方,正如你可以對 std::list<int>iteratorconst_iterator 這樣做一樣。而且,如果給定同一個鏈表的 node_iteratornode_const_iterator, 我們還希望可以比較它們的相等性。

這種同時使用兩個不同的迭代器類型的能力稱為 interoperability互操作性。在我們的例子中實現互操作性非常簡單,只要將 equal 函數模板化,並且增加一個模板轉換構造函數34就可以了:

template <class Value>
class node_iter
: public boost::iterator_facade<
node_iter<Value>
, Value
, boost::forward_traversal_tag
>
{
public:
node_iter()
: m_node(0) {}

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

template <class OtherValue>
node_iter(node_iter<OtherValue> const& other)
: m_node(other.m_node) {}

private:
friend class boost::iterator_core_access;
template <class> friend class node_iter;

template <class OtherValue>
bool equal(node_iter<OtherValue> const& other) const
{
return this->m_node == other.m_node;
}

void increment()
{ m_node = m_node->next(); }

Value& dereference() const
{ return *m_node; }

Value* m_node;
};
typedef impl::node_iterator<node_base> node_iterator;
typedef impl::node_iterator<node_base const> node_const_iterator;
[3] 如果你用的是一個較老的編譯器,不能編譯這個例子,那麼請看 例子代碼 中如何解決。
[4] 如果 node_iterator 是一個 隨機訪問遍歷迭代器,我們還要模板化它的 distance_to 函數。

你在 這裡 可以看到一個如何測試我們的可交互迭代器的例子。

實話實說

現在 node_iteratornode_const_iterator 都完全按照你的意願來工作了... 幾乎如此。我們可以比較它們,也可以從一個方向進行轉換:從 node_iteratornode_const_iterator. 如果我們試著從 node_const_iterator 轉換為 node_iterator, 我們會得到一個錯誤,因為轉換構造函數試圖用一個 node const* 初始化 node_iteratorm_node, 一個 node* . 這有什麼問題呢?

問題是,boost::is_convertible<node_const_iterator,node_iterator>::value 會為 true, 但它應該是 false. is_convertible 說謊了,因為它只看到了 node_iter 的轉換構造函數的 聲明,而看不到內部的 定義 以確認它可以編譯。完美的解決方案是,當 m_node 的轉換失敗時,讓 node_iter 的轉換構造函數消失。

實際上,這種魔術可以用 boost::enable_if 來實現。按以下方式重寫轉換構造函數,我們就可以在轉換構造函數不適用的時候從重載函數組中將它去掉。

#include <boost/type_traits/is_convertible.hpp>
#include <boost/utility/enable_if.hpp>

...

private:
struct enabler {};

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

結束語

我們的 iterator_facade 指南到此為止,不過在你結束閱讀之前,我們強烈建議你看一看 iterator_adaptor. 那裡有另一種方法編寫更為高級的迭代器。