動機

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

由於迭代器遍歷和值訪問兩個問題被混合在單個層次中，所以許多有用的迭代器不能被正確地歸類。例如，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的建議純粹只是一個擴充。進一步說，這些新的迭代器概念是後向兼容於舊的迭代器要求的，而且舊的迭代器也前向兼容於新的迭代器概念。也就是說，滿足舊要求的迭代器也滿足新系統中的對應概念，符合新概念的迭代器也自動滿足相應的舊要求。

設計

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

• 可讀迭代器
• 可寫迭代器
• 可交換迭代器
• 左值迭代器

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

另一組概念處理遍歷：

• 可遞增迭代器
• 單遍迭代器
• 前向遍歷迭代器
• 雙向遍歷迭代器
• 隨機訪問遍歷迭代器

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

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

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

• 可交互迭代器

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

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

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

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

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

提議文本

{
  X tmp = r;
  --r;
  return tmp;
}

{
  Distance m = n;
  if (m >= 0)
    while (m--)
      ++r;
  else
    while (m++)
      --r;
  return r;
}

// 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 { };

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

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.