迭代器的外觀和適配器

Author: David Abrahams, Jeremy Siek, Thomas Witt
Contact: dave@boost-consulting.com, jsiek@osl.iu.edu, witt@styleadvisor.com
Organization: Boost Consulting, Indiana University Open Systems Lab, Zephyr Associates, Inc.
Date: 2006-09-11
Number: This is a revised version of N1530=03-0113, which was accepted for Technical Report 1 by the C++ standard committee's library working group.
copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.
概要: 我們提議了一組類模板,幫助程序員構建符合標準的迭代器,包括從草稿出發和調整其它迭代器。

目錄

動機

迭代器是現代C++編程中的重要角色。它是標準庫中的算法的重要抽像物,使得算法可以被重用於廣泛的上下文中。C++ 標準庫包含了大量有用的迭代器。每一種標準容器都帶有常量和非常量迭代器2,還有相應的反向版本用於以相反順序對容器進行遍歷。標準還提供了 istream_iteratorostream_iterator 用於從流讀取和寫出到流,insert_iterator, front_insert_iteratorback_insert_iterator 則用於插入元素到容器中,還有 raw_storage_iterator 用於初始化原始內存。[7]

儘管標準庫提供了許多迭代器,但是還是遺漏了一些明顯和有用的迭代器,對於C++程序員來說創建新的迭代器類型仍是一項常見的工作。有一些文獻討論了一些迭代器,如 line_iterator [3] 和 Constant_iterator [9]. 迭代器的抽像是非常強有力的,我們認為程序員總是需要發明新的迭代器類型。

雖然創建一個幾乎符合標準的迭代器很容易,但是對迭代器的要求包含了一些很微妙的地方,使得創建一個精確符合標準的迭代器非常困難。更進一步,迭代器的接口非常豐富,包含了許多操作符,技術上是存在冗余而實現它們是乏味的。為了讓構造迭代器的重複工作可以自動完成,我們提議了 iterator_facade, 它是一個迭代器基類模板,提供了標準迭代器的豐富接口,並且將其實現委託給派生類的成員函數。除了減少創建迭代器所需的代碼數量之外,iterator_facade 還提供了編譯期錯誤檢測。迭代器實現中經常被忽視的錯誤變成了編譯期錯誤,因為派生類的實現必須符合 iterator_facade 的期望。

構造迭代器的一個常見模式是將一個已有的迭代器改編為新的迭代器。一個迭代器的功能由四個正交的方面組成:遍歷,間接性,相等性比較和距離計算。改編一個舊的迭代器以創建新的迭代器通常可以節省工作量,因為你可以重用某些方面的功能而重定義其它方面。例如,標準提供了 reverse_iterator, 它將一個任意的雙向迭代器改編為以相反的順序進行遍歷。和普通的迭代器一樣,在標準之外定義的迭代器適配器已經常常出現在文獻中:

[1] 我們用術語"概念"表示一個被用於某個特定模板參數的類型所必須滿足的一組要求。
[2] 術語"非常量迭代器"是指,可以通過對被提領的迭代器進行賦值來修改迭代器所指的對象,而"常量迭代器"則是指迭代器所指的對象不能被改變。

為了滿足構造適配器的需要,我們提議了 iterator_adaptor 類模板。iterator_adaptor 的實例可用作新迭代器的基類,它提供的缺省行為是將所有操作前轉至底層的迭代器。用戶可以在派生的迭代器類中有選擇地替代某些操作。該提議書中還包含了許多特定的適配器,如 transform_iterator 可以在迭代器提領時執行某些用戶指定的函數。

對標準的影響

該提議書完全是對C++標準庫的添加。但是,請注意本提議書依賴於"新的迭代器概念"提議書。

設計

迭代器的概念

本提議書是依據 n1550 中提議的新的迭代器概念來闡述的,由於用戶自定義的迭代器尤其是改編的迭代器一直以來都受到老的迭代器分類方式所帶來的著名的分類問題所困擾。

本提議書本沒有完全遵照 n1550 中的提議,如在新舊分類法間建立直接的映射。如果 n1550 不被接受,本提議書可能會用這些映射重新編寫。

可交互性

在當前標準中,對於迭代器的可交互性問題幾乎沒有提及。當前有兩個缺點是由可交互性問題所引起的。

問題 179 提及這樣一個事實,即非常量的容器迭代器只被要求可轉換為對應的常量迭代器類型,而不要求這些類型的對象可以相互比較或相減。這種情形在實踐中是乏味的,而且與內建類型的工作方式不一致。本提議書實現了問題 179 所建議的解決方案,正如當今多數標準庫實現所做的那樣。換句話說,如果一個迭代器類型 A 有一個隱式的或用戶定義的到迭代器類型 B 的轉換,那麼這兩個迭代器類型就是可交互的,且常見的操作符都可用。

問題 280 提及了當前反向迭代器類型間的可交互性的缺失。本提議書中的新的 reverse_iterator 模板修正了 280 所提到的問題。它提供了想要的可交互性,而且沒有引入不想要的重載。

迭代器的外觀

迭代器接口非常豐富,不過存在一組對於所有功能都需要的核心接口。我們已為迭代器標識出以下核心行為:

  • 提領
  • 遞增
  • 遞減
  • 相等性比較
  • 隨機訪問動作
  • 距離計算

除了以上列出的行為以外,核心接口元素還應包括一些由迭代器 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] [Coplien, 1995] Coplien, J., Curiously Recurring Template Patterns, C++ Report, February 1995, pp. 24-27.

迭代器的適配器

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

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

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

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

特定的適配器

本提議書還包含了幾個特定適配器的例子,它們可以用 iterator_adaptor 很容易地實現:

  • indirect_iterator, 它迭代一組迭代器、指針或智能指針,並對它們進行多一次的提領動作。
  • 一個新的 reverse_iterator, 它將一個底層迭代器的移動方向反序,並允許改編後的常量和非常量迭代器以期望的方法相互操作(而不是像在多數 C++98 的實現那樣)。
  • transform_iterator, 它將一個用戶自定義的函數對像作用於底層迭代器的提領值。
  • filter_iterator, 它提供某個迭代器區間的一個視圖,其中跳過底層區間的一些元素。
  • counting_iterator, 它用於改編任意的可遞增類型(如整型數、迭代器),可以對改編後的迭代器進行遞增/遞減,並且對它的提領動作將產生 Base 類型的連續值。
  • function_output_iterator, 可以方便地創建定制化的輸出迭代器。

基於 Boost 庫的這些例子,用戶已經生成了許多新的適配器,如排列適配器,它對一個隨機訪問迭代器進行重新排列的操作;還有步幅適配器,它改編一個隨機訪問迭代器將其 移動的步幅乘以一個常量因子。另外,Boost Graph Library (BGL) 使用了迭代器適配器來將其它 graph 庫,如 LEDA [10] 和 Stanford GraphBase [8], 改編為 BGL 接口(該接口要求符合 C++ 標準的迭代器)。

提議文本

頭文件 <iterator_helper> 概要 [lib.iterator.helper.synopsis]

struct use_default;

struct iterator_core_access { /* 實現細節 */ };

template <
class Derived
, class Value
, class CategoryOrTraversal
, class Reference = Value&
, class Difference = ptrdiff_t
>
class iterator_facade;

template <
class Derived
, class Base
, class Value = use_default
, class CategoryOrTraversal = use_default
, class Reference = use_default
, class Difference = use_default
>
class iterator_adaptor;

template <
class Iterator
, class Value = use_default
, class CategoryOrTraversal = use_default
, class Reference = use_default
, class Difference = use_default
>
class indirect_iterator;

template <class Dereferenceable>
struct pointee;

template <class Dereferenceable>
struct indirect_reference;

template <class Iterator>
class reverse_iterator;

template <
class UnaryFunction
, class Iterator
, class Reference = use_default
, class Value = use_default
>
class transform_iterator;

template <class Predicate, class Iterator>
class filter_iterator;

template <
class Incrementable
, class CategoryOrTraversal = use_default
, class Difference = use_default
>
class counting_iterator;

template <class UnaryFunction>
class function_output_iterator;

迭代器外觀 [lib.iterator.facade]

iterator_facade 是一個基類模板,它依據由派生的迭代器類所提供的少量核心函數和關聯類型實現標準迭代器的接口。

類模板 iterator_facade

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).

迭代器適配器 [lib.iterator.adaptor]

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

類模板 iterator_adaptor

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

特定的適配器 [lib.iterator.special.adaptors]

本節中所使用的 enable_if_convertible<X,Y>::type 表達式是為了說明的目的。特定適配器的轉換構造函數應該只是一組重載,使得類型 X 的對象可以隱式轉換為 Y 的對象。enable_if_convertible 的符合特徵應該像以下所定義的 enable_if_convertible 那樣:

template <bool> enable_if_convertible_impl
{};

template <> enable_if_convertible_impl<true>
{ struct type; };

template<typename From, typename To>
struct enable_if_convertible
: enable_if_convertible_impl<is_convertible<From,To>::value>
{};

如果一個非缺省參數表達式被用作函數參數的值,而該參數的類型是根據 enable_if_convertible 來寫的,那麼程序就是錯誤的,無需診斷。

[註:enable_if_convertible 方法使用了 SFINAE,當類型不能被隱式轉換時,將某個構造函數排除出重載集。]

間接迭代器

indirect_iterator 改編一個迭代器,改編的方法是在 operator*() 中多使用一次提領。例如,該迭代器適配器可以用於察看一個指針容器(如 list<foo*>),就像它是一個所指類型的容器(如 list<foo>)一樣。indirect_iterator 依賴於兩個輔助 traits, pointeeindirect_reference, 它們提供了對於那些 value_type 不是一個迭代器的底層迭代器的支持。

類模板 pointee

template <class Dereferenceable>
struct pointee
{
typedef /* 見下文 */ type;
};
要求: 對於類型 Dereferenceable 的一個對像 x, *x 是合法的。如果 ++x 是非法的,那麼它應該既不是歧義的,也不違犯訪問控制,且 Dereferenceable::element_type 應該是一個可訪問的類型。否則 iterator_traits<Dereferenceable>::value_type 就應該是合法的。[註:這些要求無需適用於 pointee 的顯式特化或偏特化]

type 按以下算法確定,其中 x 為類型 Dereferenceable 的一個對像:

if ( ++x 是非法的 )
{
return ``Dereferenceable::element_type``
}
else if (``*x`` 是一個 std::iterator_traits<Dereferenceable>::value_type 的非常量引用)
{
return iterator_traits<Dereferenceable>::value_type
}
else
{
return iterator_traits<Dereferenceable>::value_type const
}

類模板 indirect_reference

template <class Dereferenceable>
struct indirect_reference
{
typedef /* 見下文 */ type;
};
要求: 對於類型 Dereferenceable 的一個對像 x, *x 是合法的。如果 ++x 是非法的,那麼它應該既不是歧義的,也不違犯訪問控制,且 pointee<Dereferenceable>::type& 應該是合法的。否則 iterator_traits<Dereferenceable>::reference 就應該是合法的。[註:這些要求無需適用於indirect_reference 的顯式特化或偏特化]

type 按以下算法確定,其中 x 為類型 Dereferenceable 的一個對像:

if ( ++x 是非法的 )
return ``pointee<Dereferenceable>::type&``
else
std::iterator_traits<Dereferenceable>::reference

類模板 indirect_iterator

template <
class Iterator
, class Value = use_default
, class CategoryOrTraversal = use_default
, class Reference = use_default
, class Difference = use_default
>
class indirect_iterator
{
public:
typedef /* 見下文 */ value_type;
typedef /* 見下文 */ reference;
typedef /* 見下文 */ pointer;
typedef /* 見下文 */ difference_type;
typedef /* 見下文 */ iterator_category;

indirect_iterator();
indirect_iterator(Iterator x);

template <
class Iterator2, class Value2, class Category2
, class Reference2, class Difference2
>
indirect_iterator(
indirect_iterator<
Iterator2, Value2, Category2, Reference2, Difference2
> const& y
, typename enable_if_convertible<Iterator2, Iterator>::type* = 0 // exposition
);

Iterator const& base() const;
reference operator*() const;
indirect_iterator& operator++();
indirect_iterator& operator--();
private:
Iterator m_iterator; // exposition
};

indirect_iterator 的成員類型按以下偽代碼定義,其中 Viterator_traits<Iterator>::value_type

if (Value 是 use_default) then
typedef remove_const<pointee<V>::type>::type value_type;
else
typedef remove_const<Value>::type value_type;

if (Reference 是 use_default) then
if (Value 是 use_default) then
typedef indirect_reference<V>::type reference;
else
typedef Value& reference;
else
typedef Reference reference;

if (Value 是 use_default) then
typedef pointee<V>::type* pointer;
else
typedef Value* pointer;

if (Difference 是 use_default)
typedef iterator_traits<Iterator>::difference_type difference_type;
else
typedef Difference difference_type;

if (CategoryOrTraversal 是 use_default)
typedef iterator-category (
iterator_traversal<Iterator>::type,``reference``,``value_type``
) iterator_category;
else
typedef iterator-category (
CategoryOrTraversal,``reference``,``value_type``
) iterator_category;

indirect_iterator 的要求

表達式 *v 應是有效表達式且可轉換為 reference,其中 viterator_traits<Iterator>::value_type 的對象。Iterator 應符合 iterator_category 所表示的遍歷概念。Value, Reference, 和 Difference 的選擇應使得 value_type, reference, 和 difference_type 滿足 iterator_category 的要求。

[註:如果 Value 參數不是 use_default,則對於 iterator_traits<Iterator>::value_type 還有更多要求,如算法所暗示的可以推斷出 value_type 成員的缺省值。]

indirect_iterator 的模型

除了 iterator_categoryiterator_traversal<indirect_iterator>::type 所表示的概念之外,indirect_iterator 的特化類還符合以下概念,其中 viterator_traits<Iterator>::value_type 對像:

  • 可讀迭代器,如果 reference(*v) 可轉換為 value_type.
  • 可寫迭代器,如果 reference(*v) = t 是有效表達式(其中 tindirect_iterator::value_type 對像)
  • 左值迭代器,如果 reference 是引用類型。

indirect_iterator<X,V1,C1,R1,D1>indirect_iterator<Y,V2,C2,R2,D2> 可交互,當且僅當 XY 是可交互的。

indirect_iterator 的操作

除了上述概念所要求的操作以外,indirect_iterator 的特化類還提供了以下操作。

indirect_iterator();

要求: Iterator 必須是可缺省構造的。
作用: 構造一個 indirect_iterator 實例,帶有一個缺省構造的 m_iterator.

indirect_iterator(Iterator x);

作用: 構造一個 indirect_iterator 實例,帶有一個從 x 複製構造得到的 m_iterator.
template <
class Iterator2, class Value2, unsigned Access, class Traversal
, class Reference2, class Difference2
>
indirect_iterator(
indirect_iterator<
Iterator2, Value2, Access, Traversal, Reference2, Difference2
> const& y
, typename enable_if_convertible<Iterator2, Iterator>::type* = 0 // exposition
);
要求: Iterator2 可隱式轉換為 Iterator.
作用: 構造一個 indirect_iterator 實例,其 m_iterator 子對像構造自 y.base().

Iterator const& base() const;

返回: m_iterator

reference operator*() const;

返回: **m_iterator

indirect_iterator& operator++();

作用: ++m_iterator
返回: *this

indirect_iterator& operator--();

作用: --m_iterator
返回: *this

反序迭代器

反序迭代器適配器以相反的方向遍歷被改編的迭代器的區間。

類模板 reverse_iterator

template <class Iterator>
class reverse_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;

reverse_iterator() {}
explicit reverse_iterator(Iterator x) ;

template<class OtherIterator>
reverse_iterator(
reverse_iterator<OtherIterator> const& r
, typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition
);
Iterator const& base() const;
reference operator*() const;
reverse_iterator& operator++();
reverse_iterator& operator--();
private:
Iterator m_iterator; // exposition
};

如果 Iterator 符合隨機訪問遍歷迭代器及可讀左值迭代器,則 iterator_category 可轉換為 random_access_iterator_tag. 否則,如果 Iterator 符合雙向遍歷迭代器及可讀左值迭代器,則 iterator_category 可轉換為 bidirectional_iterator_tag. 否則,iterator_category 可轉換為 input_iterator_tag.

reverse_iterator 的要求

Iterator 必須符合雙向遍歷迭代器。類型 iterator_traits<Iterator>::reference 必須是 *i 的類型,其中 i 為類型 Iterator 的一個對象。

reverse_iterator 的模型

reverse_iterator 的特化類所符合的迭代器遍歷概念和迭代器訪問概念與它的 Iterator 參數所符合的相同。此外,它還可能符合下表中所指定的舊式迭代器概念:

如果 I 符合 則 reverse_iterator<I> 符合
可讀左值迭代器,雙向遍歷迭代器 雙向迭代器
可寫左值迭代器,雙向遍歷迭代器 非常量雙向迭代器
可讀左值迭代器,隨機訪問遍歷迭代器 隨機訪問迭代器
可寫左值迭代器,隨機訪問遍歷迭代器 非常量隨機訪問迭代器

reverse_iterator<X>reverse_iterator<Y> 可交互,當且僅當 XY 是可交互的。

reverse_iterator 的操作

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

reverse_iterator();

要求: Iterator 必須是可缺省構造的。
作用: 構造一個 reverse_iterator 實例,帶有缺省構造的 m_iterator.

explicit reverse_iterator(Iterator x);

作用: 構造一個 reverse_iterator 實例,帶有從 x 複製構造所得的 m_iterator.
template<class OtherIterator>
reverse_iterator(
reverse_iterator<OtherIterator> const& r
, typename enable_if_convertible<OtherIterator, Iterator>::type* = 0 // exposition
);
要求: OtherIterator 可隱式轉換為 Iterator.
作用: 構造一個 reverse_iterator 實例,其 m_iterator 子對像構造自 y.base().

Iterator const& base() const;

返回: m_iterator

reference operator*() const;

作用:
Iterator tmp = m_iterator;
return *--tmp;

reverse_iterator& operator++();

作用: --m_iterator
返回: *this

reverse_iterator& operator--();

作用: ++m_iterator
返回: *this

轉換迭代器

轉換迭代器改編一個迭代器,將 operator* 改為對迭代器提領得到的值應用於一個函數對象,然後返回函數調用的結果。

類模板 transform_iterator

template <class UnaryFunction,
class Iterator,
class Reference = use_default,
class Value = use_default>
class transform_iterator
{
public:
typedef /* 見下文 */ value_type;
typedef /* 見下文 */ reference;
typedef /* 見下文 */ pointer;
typedef iterator_traits<Iterator>::difference_type difference_type;
typedef /* 見下文 */ iterator_category;

transform_iterator();
transform_iterator(Iterator const& x, UnaryFunction f);

template<class F2, class I2, class R2, class V2>
transform_iterator(
transform_iterator<F2, I2, R2, V2> const& t
, typename enable_if_convertible<I2, Iterator>::type* = 0 // exposition only
, typename enable_if_convertible<F2, UnaryFunction>::type* = 0 // exposition only
);
UnaryFunction functor() const;
Iterator const& base() const;
reference operator*() const;
transform_iterator& operator++();
transform_iterator& operator--();
private:
Iterator m_iterator; // exposition only
UnaryFunction m_f; // exposition only
};

如果 Referenceuse_defaulttransform_iteratorreference 成員為 result_of<UnaryFunction(iterator_traits<Iterator>::reference)>::type. 否則,referenceReference.

如果 Valueuse_defaultvalue_type 成員為 remove_cv<remove_reference<reference> >::type. 否則,value_typeValue.

如果 Iterator 符合可讀左值迭代器,並且 Iterator 符合隨機訪問遍歷迭代器,則 iterator_category 可轉換為 random_access_iterator_tag. 否則,如果 Iterator 符合雙向遍歷迭代器,則 iterator_category 可轉換為 bidirectional_iterator_tag. 否則 iterator_category 可轉換為 forward_iterator_tag. 如果 Iterator 不符合可讀左值迭代器則 iterator_category 可轉換為 input_iterator_tag.

transform_iterator 的要求

類型 UnaryFunction 必須是可賦值的、可複製構造的,並且表達式 f(*i) 必須是有效的,其中 f 為類型 UnaryFunction 的一個對象,i 為類型 Iterator 的一個對象,f(*i) 的類型必須是 result_of<UnaryFunction(iterator_traits<Iterator>::reference)>::type.

參數 Iterator 應符合可讀迭代器。

transform_iterator 的模型

transform_iterator 的結果符合以下概念中 Iterator 所符合的最強化的一個。

  • 可寫左值迭代器,如果 transform_iterator::reference 為非常量引用。
  • 可讀左值迭代器,如果 transform_iterator::reference 為常量引用。
  • 否則,可讀迭代器。

transform_iterator 符合其 Iterator 參數所符合的最強化的標準遍歷概念。

如果 transform_iterator 符合可讀左值迭代器,則它依據其 Iterator 參數的情況符合以下原有迭代器概念。

如果 Iterator 符合 則 transform_iterator 符合
單遍迭代器 輸入迭代器
前向遍歷迭代器 前向迭代器
雙向遍歷迭代器 雙向迭代器
隨機訪問遍歷迭代器 隨機訪問迭代器

如果 transform_iterator 符合可寫左值迭代器,則它為非常量迭代器(參照舊式迭代器要求中的定義)。

transform_iterator<F1, X, R1, V1>transform_iterator<F2, Y, R2, V2> 可交互,當且僅當 XY 是可交互的。

transform_iterator 的操作

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

transform_iterator();

返回: 一個 transform_iterator 實例,帶有缺省構造的 m_fm_iterator.

transform_iterator(Iterator const& x, UnaryFunction f);

返回: 一個 transform_iterator 實例,其 m_f 初始化為 fm_iterator 初始化為 x.
template<class F2, class I2, class R2, class V2>
transform_iterator(
transform_iterator<F2, I2, R2, V2> const& t
, typename enable_if_convertible<I2, Iterator>::type* = 0 // exposition only
, typename enable_if_convertible<F2, UnaryFunction>::type* = 0 // exposition only
);
返回: 一個 transform_iterator 實例,其 m_f 初始化為 t.functor()m_iterator 初始化為 t.base().
要求: OtherIterator 可隱式轉換為 Iterator.

UnaryFunction functor() const;

返回: m_f

Iterator const& base() const;

返回: m_iterator

reference operator*() const;

返回: m_f(*m_iterator)

transform_iterator& operator++();

作用: ++m_iterator
返回: *this

transform_iterator& operator--();

作用: --m_iterator
返回: *this

過濾迭代器

過濾迭代器適配器創建一個迭代器區間的視圖,該區間中的某些元素會被跳過。跳過哪些元素是由一個謂詞函數對像來控制的。該謂詞被應用於某個元素,如果返回 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

計數迭代器

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

函數輸出迭代器

函數輸出迭代器適配器可以很容易地創建定制化的輸出迭代器。該適配器接受一個單參函數,並創建一個輸出迭代器的 model。每一個賦給該輸出迭代器的數據都被作為參數傳遞給給定的單參函數。定義該迭代器的動機是,創建一個符合標準的輸出迭代器是有些難度的,尤其是 因為正確的實現通常需要一個代理對象。

function_output_iterator 的要求

UnaryFunction 必須是可賦值和可複製構造的。

function_output_iterator 的模型

function_output_iterator 是可寫和可遞增迭代器概念的 model.

function_output_iterator 的操作

explicit function_output_iterator(const UnaryFunction& f = UnaryFunction());

作用: 構造一個 function_output_iterator 實例,其 m_f 構造自 f.

operator*();

返回: 一個未指定類型的對象 r,對於所有 t 滿足 r = t 等效於 m_f(t).

function_output_iterator& operator++();

返回: *this

function_output_iterator& operator++(int);

返回: *this