新的迭代器概念

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 n1550=03-0133, which was accepted for Technical Report 1 by the C++ standard committee's library working group. This proposal is a revision of paper n1297, n1477, and n1531.
Copyright: Copyright David Abrahams, Jeremy Siek, and Thomas Witt 2003.
概要: 我們提出了一個新的迭代器概念系統,獨立對待訪問和定位。這樣允許概念更為接近於算法的要求,並為實際使用提供更好的迭代器分類方法。

目錄

動機

標準的迭代器分類和要求是有缺陷的,因為它用單個概念層次來處理兩個正交的問題:迭代器遍歷值訪問。因 此,按照此迭代器分類方式所編寫的許多算法要求過於嚴格。另外,真實世界中的許多迭代器並不能被準確地歸類。例如,一個可以隨機訪問遍歷的基於代理的迭代 器只能被歸類為"輸入迭代器",所以泛型算法不能從它的隨機訪問能力得到好處。當前的迭代器概念層次是以迭代器遍歷方式來分級的(因此有了當前的分類 名),而對於值訪問的要求則被隱藏在不同的地方。下表總結了在當前迭代器分類中的值訪問要求。

在現有迭代器分類中的值訪問要求
輸出迭代器 *i = a
輸入迭代器 *i 可轉換為 T
前向迭代器 *iT& (或 const T& 如果 issue 200 被通過)
隨機訪問迭代器 i[n] 可轉換為 T (對於可變迭代器,如果 issue 299 被通過,則要加上 i[n] = t 的要求)

由於迭代器遍歷和值訪問兩個問題被混合在單個層次中,所以許多有用的迭代器不能被正確地歸類。例如,vector<bool>::iterator 幾乎可以算是一個隨機訪問迭代器,但它的返回類型不是 bool& (請見 issue 96 和 Herb Sutter 的論文 J16/99-0008 = WG21 N1185)。因此,vector<bool> 的迭代器只能滿足輸入迭代器和輸出迭代器的要求。這是非常不直觀的,在這一點上 C++ 標準自相矛盾。在標準的 23.2.4/1,它說 vector 是一個支持隨機訪問迭代器的序列容器。

另一個難于歸類的迭代器是轉換迭代器,它是一個適配器,對某個底層迭代器的提領值執行一個單參函數對像(請見 transform_iterator)。對於象 times 這樣的單參函數,operator* 的返回類型應該是函數對象的 result_type,它顯然不是一個引用。因為隨機訪問迭代器要求 operator* 返回一個左值,如果你用一個轉換迭代器對 int* 進行包裝,則不能得到如你所願一個隨機訪問迭代器,而只是一個輸入迭代器。

第三個例子是 Boost Graph 庫 中的點和邊迭代器。這些迭代器返回點和邊的描述符,它們是就地創建的輕量級句柄。它們必須以值方式返回。因此,它們當前的迭代器分類為 input_iterator_tag, 這意味著嚴格地說,你不能將這些迭代器用於象 min_element() 這樣的算法。作為臨時的解決方法,引入了概念 Multi-Pass 輸入迭代器 來描述點和邊描述符,但是正如該概念建議的設計註釋所說,需要一個更好的解決方案。

簡單地說,有許多有用的迭代器不能準確地歸入當前的標準迭代器類別中。結果就導致了以下不好的後果:

對標準的影響

這個對TR1的建議純粹只是一個擴充。進一步說,這些新的迭代器概念是後向兼容於舊的迭代器要求的,而且舊的迭代器也前向兼容於新的迭代器概念。也就是說,滿足舊要求的迭代器也滿足新系統中的對應概念,符合新概念的迭代器也自動滿足相應的舊要求。

對工作文稿的可能(但未被提議)的修改

對於本文中建議的幾個修改,我們可能會為下一個標準準備工作文稿。這些修改還不是 TR1 的正式部分。

對算法要求的修改

標準庫中的算法可以從新的迭代器概念中獲得好處,因為新的迭代器概念為它們對類型的要求提供了更精確的方法。結果是算法可以在更多的情形下使用,同時對類型的要求也更少。

對於下一個工作文稿(不是 TR1),委員會將考慮對算法的類型要求作出以下修改。這些修改可稱為文本替換,對以下列出的每個算法進行相應的文本替換。

前向迭代器 -> 前向遍歷迭代器及可讀迭代器

find_end, adjacent_find, search, search_n, rotate_copy, lower_bound, upper_bound, equal_range, binary_search, min_element, max_element

前向迭代器(1) -> 單遍迭代器及可讀迭代器,前向迭代器(2) -> 前向遍歷迭代器及可讀迭代器

find_first_of

前向迭代器 -> 可讀迭代器及可寫迭代器

iter_swap

前向迭代器 -> 單遍迭代器及可寫迭代器

fill, generate

前向迭代器 -> 前向迭代器及可交換迭代器

rotate

前向迭代器(1) -> 可交換迭代器及單遍迭代器,前向迭代器(2) -> 可交換迭代器及可遞增迭代器

swap_ranges
前向迭代器 -> 前向遍歷迭代器及可讀迭代器及可寫迭代器
remove, remove_if, unique

前向迭代器 -> 單遍迭代器及可讀迭代器及可寫迭代器

replace, replace_if
雙向迭代器 -> 雙向遍歷迭代器及可交換迭代器
reverse
雙向迭代器 -> 雙向遍歷迭代器及可讀迭代器及可交換迭代器
partition

雙向迭代器(1) -> 雙向遍歷迭代器及可讀迭代器,雙向迭代器(2) -> 雙向遍歷迭代器及可寫迭代器

copy_backwards
雙向迭代器 -> 雙向遍歷迭代器及可交換迭代器及可讀迭代器
next_permutation, prev_permutation
雙向迭代器 -> 雙向遍歷迭代器及可讀迭代器及可寫迭代器
stable_partition, inplace_merge
雙向迭代器 -> 雙向遍歷迭代器及可讀迭代器
reverse_copy
隨機訪問迭代器 -> 隨機訪問遍歷迭代器及可讀迭代器及可寫迭代器
random_shuffle, sort, stable_sort, partial_sort, nth_element, push_heap, pop_heap make_heap, sort_heap
輸入迭代器(2) -> 可遞增迭代器及可讀迭代器
equal, mismatch
輸入迭代器(2) -> 可遞增迭代器及可讀迭代器
transform

反對意見

對於下一個工作文稿(不是 TR1),委員會將考慮取消舊的迭代器分類標誌,以及 std::iterator_traits,因為它將被獨立的 traits 元函數所取代。

vector<bool>

對於下一個工作文稿(不是 TR1),委員會將考慮將 vector<bool>::iterator 重新歸類為隨機訪問遍歷迭代器及可讀迭代器及可寫迭代器。

設計

迭代器的要求被分為兩組。一組概念處理值訪問的語法和語義:

這個訪問概念描述了對於 operator*operator-> 的要求,包括 value_type, reference, 和 pointer 等關聯類型。

另一組概念處理遍歷:

下圖表示了以上遍歷概念的強化關係。

traversal.png

除了迭代器移動操作符如 operator++ 之外,遍歷概念還包括了對位置比較的要求,如 operator==operator<。將概念細分為可遞增和單遍的,是為了提供對原有的輸入和輸出迭代器要求更為精確的匹配。

本建議中還包含一個概念,用於指定一個迭代器可以與另一個迭代器相互操作,如 int* 可以與 int const* 相互操作。

下圖表示了新的迭代器概念與舊的概念之間的關係。

oldeqnew.png

和舊的迭代器要求一樣,我們提供了一些標誌以實現基於遍歷概念進行分派。這些標誌通過繼承相互聯繫,因此一個標誌可以轉換為另一個標誌,如果與第一個標誌相關的概念強化自第二個標誌所對應的概念。

我們的設計重用了 iterator_traits<Iter>::iterator_category 來表示一個迭代器的遍歷能力。要指定舊式迭代器分類所不包含的能力,迭代器的設計者可以用一個既可轉換為最合適的舊迭代器類別,又可以轉換為合適的新迭代器遍歷標誌的 iterator_category 類型。

我們不提供實現基於訪問概念進行分派的標誌,部分原因是我們沒有辦法自動地正確推斷出舊式迭代器的訪問標誌。一個迭代器的可寫性可能依賴於它的 value_type 的可賦值性,但我們沒有辦法檢查一個任意類型是否可賦值的。還好,對基於訪問能力進行分派的需求並沒有基於遍歷能力進行分派的需求那麼迫切。

一個困難的設計決定是關於 operator[] 的。直接的方法是指定 operator[] 的返回某個類型的 reference; 和 operator* 一樣。但是,沿著這個方向下去會發現,一個滿足舊的隨機訪問迭代器要求的迭代器將不需要符合可讀或可寫左值迭代器。為此我們選擇了另一個設計,與 issue 299 中的首選決議相同:operator[] 只被要求返回某個可轉換為 value_type 的東西(對於可讀迭代器),以及被要求支持賦值 i[n] = t (對於可寫迭代器)。

提議文本

添加到 [lib.iterator.requirements]

迭代器的值訪問概念 [lib.iterator.value.access]

在下表中,X 是一個迭代器類型,a 是類型 X 的一個常量對象,Rstd::iterator_traits<X>::referenceTstd::iterator_traits<X>::value_typev 是類型 T 的一個常量對象。

可讀迭代器 [lib.readable.iterators]

一個類或內建類型 X 符合值類型 TReadable Iterator可讀迭代器 概念,如果 X 是可賦值的和可複製構造的,且以下表達式有效並遵從規定的語義。U 為類型 T 的某個指定成員的類型。

可讀迭代器要求 (除了可賦值和可複製構造以外)
表達式 返回類型 備註/前提條件
iterator_traits<X>::value_type T 任意非引用、非-cv-限定的類型
*a Convertible to T
前提條件:a 是可提領的。如果 a == b*a 等價於 *b
a->m U& 前提條件:(*a).m 有良好定義。等價於 (*a).m.

可寫迭代器 [lib.writable.iterators]

一個類或內建類型 X 符合 Writable Iterator可寫迭代器 概念,如果 X 是可複製構造的,且以下表達式有效並遵從規定的語義。可寫迭代器有一個關聯的值類型組。

可寫迭代器要求 (除了可複製構造以外)
表達式 返回類型 前提條件
*a = o   前提條件:o 的類型在 X 的值類型組中

可交換迭代器 [lib.swappable.iterators]

一個類或內建類型 X 符合 Swappable Iterator可交換機迭代器 概念,如果 X 是可複製構造的,且以下表達式有效並遵從規定的語義。

可交換迭代器要求 (除了可複製構造以外)
表達式 返回類型 後續條件
iter_swap(a, b) void 所指向的值被交換

[註:一個同時符合 可讀迭代器可寫迭代器 概念的迭代器也符合 可交換迭代器--end note]

左值迭代器 [lib.lvalue.iterators]

Lvalue Iterator左值迭代器 概念增加一個要求,即 operator* 的返回類型應為迭代器的值類型的引用。

左值迭代器要求
表達式 返回類型 備註/斷言
*a T& Tcv iterator_traits<X>::value_type,其中 cv 是一個可選的 cv-限定符。
前提條件:a 是可提領的。

如果 X 是一個 可寫迭代器,則 a == b 當且僅當 *a*b 為同一個對象。如果 X 是一個 可讀迭代器,則 a == b 意味著 *a*b 為同一個對象。

迭代器遍歷概念 [lib.iterator.traversal]

在下表中,X 是一個迭代器類型,ab 是類型 X 的一個常量對象,rs 是類型 X 的可變對象,Tstd::iterator_traits<X>::value_typev 是類型 T 的一個常量對象。

可遞增迭代器 [lib.incrementable.iterators]

一個類或內建類型 X 符合 Incrementable Iterator可遞增迭代囂 概念,如果 X 是可賦值的和可複製構造的,且以下表達式有效並遵從規定的語義。

可遞增迭代器要求 (除了可賦值和可複製構造以外)
表達式 返回類型 斷言
++r X& &r == &++r
r++    
*r++    
iterator_traversal<X>::type 可轉換為 incrementable_traversal_tag  

如果 X 是一個 可寫迭代器X a(r++); 等價於 X a(r); ++r;*r++ = o 等價於 *r = o; ++r. 如果 X 是一個 可讀迭代器T z(*r++); 等價於 T z(*r); ++r;.

單遍迭代器 [lib.single.pass.iterators]

一個類或內建類型 X 符合 Single Pass Iterator單遍迭代器 概念,如果以下表達式有效且遵從規定的語義。

單遍迭代器要求 (除了可遞增迭代器和可等價比較以外)
表達式 返回類型 操作語義 斷言/前提條件/後續條件
++r X&   前提:r 是可提領的;
後續:r 是可提領的或 r 指向末尾
a == b 可轉換為 bool   == 為該領域的一個等價關係
a != b 可轉換為 bool !(a == b)  
iterator_traversal<X>::type 可轉換為 single_pass_traversal_tag    

前向遍歷迭代器 [lib.forward.traversal.iterators]

一個類或內建類型 X 符合 Forward Traversal Iterator前向遍歷迭代器 概念,如果 X 符合可缺省構造和單遍迭代器的要求,且以下表達式有效並遵從規定的語義。

前向遍歷迭代器要求 (除了可缺省構造和單遍迭代器以外)
表達式 返回類型 斷言/備註
X u; X& 註:u 可以具有異常值
++r X& r == sr 為可提領的則 ++r == ++s.
iterator_traits<X>::difference_type 一個有符號整型類型,表示兩個迭代器間的距離  
iterator_traversal<X>::type 可轉換為 forward_traversal_tag  

雙向遍歷迭代器 [lib.bidirectional.traversal.iterators]

一個類或內建類型 X 符合 Bidirectional Traversal Iterator雙向遍歷迭代器 概念,如果 X 符合前向遍歷迭代器的要求,且以下表達式有效並遵從規定的語義。

雙向遍歷迭代器要求 (除了前向遍歷迭代器以外)
表達式 返回類型 操作語義 斷言/前提/後續條件
--r X&  

前提:存在某個 s 使得 r == ++s

後續:s 為可提領的

++(--r) == r. --r == --s 意味著 r == s. &r == &--r.

r-- 可轉換為 const X&
{
X tmp = r;
--r;
return tmp;
}
 
iterator_traversal<X>::type 可轉換為 bidirectional_traversal_tag    

隨機訪問遍歷迭代器 [lib.random.access.traversal.iterators]

一個類或內建類型 X 符合 Random Access Traversal Iterator隨機訪問遍歷迭代器 概念,如果以下表達式有效且遵從規定的語義。在下表中,Distanceiterator_traits<X>::difference_typen 表示類型 Distance 的一個常量對象。

隨機訪問遍歷迭代器要求 (除了雙向遍歷迭代器以外)
表達式 返回類型 操作語義 斷言/前提條件
r += n X&
{
Distance m = n;
if (m >= 0)
while (m--)
++r;
else
while (m++)
--r;
return r;
}
 
a + n, n + a X { X tmp = a; return tmp += n; }  
r -= n X& return r += -n  
a - n X { X tmp = a; return tmp -= n; }  
b - a Distance a < b ?  distance(a,b) : -distance(b,a) 前提:存在一個 Distance 的值 n 使得 a + n == b. b == a + (b - a).
a[n] 可轉換為 T *(a + n) 前提:a 是一個 可讀迭代器
a[n] = v 可轉換為 T *(a + n) = v 前提:a 是一個 可寫迭代器
a < b 可轉換為 bool b - a > 0 < 是一個全序關係
a > b 可轉換為 bool b < a > 是一個全序關係
a >= b 可轉換為 bool !(a < b)  
a <= b 可轉換為 bool !(a > b)  
iterator_traversal<X>::type 可轉換為 random_access_traversal_tag    

可交互迭代器 [lib.interoperable.iterators]

一個符合單遍迭代器概念的類或內建類型 X 與另一個也符合單遍迭代器概念的類或內建類型 Y 是 interoperable可交互的,如果以下表達式有效且遵從規定的語義。在下表中,x 是類型 X 的一個對象,y 是類型 Y 的一個對象,Distanceiterator_traits<Y>::difference_type,而 n 表示類型 Distance 的一個常量對象。

表達式 返回類型 斷言/前提條件/後續條件
y = x Y 後續條件:y == x
Y(x) Y 後續條件:Y(x) == x
x == y 可轉換為 bool == 是該領域的一個等價關係
y == x 可轉換為 bool == 是該領域的一個等價關係
x != y 可轉換為 bool 在該領域中 bool(a==b) != bool(a!=b) 
y != x 可轉換為 bool 在該領域中 bool(a==b) != bool(a!=b)

如果 XY 都是隨機訪問遍歷迭代器,則必須滿足以下要求。

表達式 返回類型 操作語義 斷言/前提條件
x < y 可轉換為 bool y - x > 0 < 是一個全序關係
y < x 可轉換為 bool x - y > 0 < 是一個全序關係
x > y 可轉換為 bool y < x > 是一個全序關係
y > x 可轉換為 bool x < y > 是一個全序關係
x >= y 可轉換為 bool !(x < y)  
y >= x 可轉換為 bool !(y < x)  
x <= y 可轉換為 bool !(x > y)  
y <= x 可轉換為 bool !(y > x)  
y - x Distance distance(Y(x),y) 前提:存在一個 Distance 的值 n 使得 x + n == y. y == x + (y - x).
x - y Distance distance(y,Y(x)) 前提:存在一個 Distance 的值 n 使得 y + n == x. x == y + (x - y).

添加到 [lib.iterator.synopsis]

// lib.iterator.traits, traits 和 tags
template <class Iterator> struct is_readable_iterator;
template <class Iterator> struct iterator_traversal;

struct incrementable_traversal_tag { };
struct single_pass_traversal_tag : incrementable_traversal_tag { };
struct forward_traversal_tag : single_pass_traversal_tag { };
struct bidirectional_traversal_tag : forward_traversal_tag { };
struct random_access_traversal_tag : bidirectional_traversal_tag { };

添加到 [lib.iterator.traits]

類模板 is_readable_iterator 滿足 UnaryTypeTrait 的要求。

給定一個迭代器類型 X, is_readable_iterator<X>::valuetrue 如果對於類型 X 的一個對像 a, *a 可轉換為 iterator_traits<X>::value_type, 否則為 false.

iterator_traversal<X>::type

category-to-traversal(iterator_traits<X>::iterator_category)

其中 category-to-traversal 定義如下:

category-to-traversal(C) =
if (C 可轉換為 incrementable_traversal_tag)
return C;
else if (C 可轉換為 random_access_iterator_tag)
return random_access_traversal_tag;
else if (C 可轉換為 bidirectional_iterator_tag)
return bidirectional_traversal_tag;
else if (C 可轉換為 forward_iterator_tag)
return forward_traversal_tag;
else if (C 可轉換為 input_iterator_tag)
return single_pass_traversal_tag;
else if (C 可轉換為 output_iterator_tag)
return incrementable_traversal_tag;
else
程序有錯誤

腳注

UnaryTypeTrait 概念定義於 n1519; LWG 正考慮增加一個要求,即特化類型要派生自它們的嵌套 ::type.