概述

Created: November-22, 2018

迭代器是位置

迭代器是一種導航和操作一系列元素的方法，是指標的通用擴充套件。從概念上講，重要的是要記住迭代器是位置，而不是元素。例如，按以下順序：

A B C

該序列包含三個元素和四個位置

+---+---+---+---+
| `A` | B | C |   |
+---+---+---+---+

元素是序列中的東西。位置是序列中可能發生有意義操作的位置。例如，一個插入元素 A 之前或之後的位置，而不插入元素。甚至刪除元素（erase(A)）也是通過首先找到它的位置，然後刪除它來完成的。

從迭代器到值

要從位置轉換為值，請取消引用迭代器：

auto my_iterator = my_vector.begin(); // position
auto my_value = *my_iterator; // value

可以將迭代器視為取消引用它在序列中引用的值。這對於理解為什麼不應該在序列中取消引用 end() 迭代器特別有用：

+---+---+---+---+
| `A` | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           +-- An iterator here has no value. Do not dereference it!
  +-------------- An iterator here dereferences to the value A.

在 C++標準庫中找到的所有序列和容器中，begin() 將返回一個迭代器到第一個位置，end() 將一個迭代器返回到最後一個位置（不是最後一個位置！）。因此，演算法中這些迭代器的名稱通常標記為 first 和 last：

+---+---+---+---+
| `A` | B | C |   |
+---+---+---+---+
  ↑           ↑
  |           |
  +- first    +- last

也可以獲得任何序列的迭代器，因為即使空序列至少包含一個位置：

+---+
|   |
+---+

在一個空序列中，begin() 和 end() 將是相同的位置，並且都不能被解除引用：

+---+
|   |
+---+
  ↑
  |
  +- empty_sequence.begin()
  |
  +- empty_sequence.end()

迭代器的替代視覺化是它們標記元素之間的位置：

+---+---+---+
| `A` | B | C |
+---+---+---+
↑   ^   ^   ↑
|           |
+- first    +- last

並取消引用迭代器返回對迭代器之後的元素的引用。這種觀點特別有用的一些情況是：

insert 操作會將元素插入到迭代器指示的位置，
erase 操作將返回一個迭代器，該迭代器對應於與傳入的位置相同的位置，
迭代器及其相應的反向迭代器位於元素之間的相同位置

無效的迭代器

如果（例如，在操作過程中）其位置不再是序列的一部分，則迭代器變為無效。在將有效迭代器重新分配到有效位置之前，無法取消引用它。例如：

std::vector<int>::iterator first;
{
    std::vector<int> foo;
    first = foo.begin(); // first is now valid
} // foo falls out of scope and is destroyed
// At this point first is now invalid

C++標準庫中的許多演算法和序列成員函式都有規則來控制迭代器何時失效。每種演算法在處理（和無效）迭代器的方式上都不同。

使用迭代器進行導航

我們知道，迭代器用於導航序列。為了做到這一點，迭代器必須在整個序列中遷移它的位置。迭代器可以按順序前進，有些可以向前推進：

auto first = my_vector.begin();
++first;                                             // advance the iterator 1 position
std::advance(first, 1);                              // advance the iterator 1 position
first = std::next(first);                            // returns iterator to the next element
std::advance(first, -1);                             // advance the iterator 1 position backwards
first = std::next(first, 20);                        // returns iterator to the element 20 position forward
first = std::prev(first, 5);                         // returns iterator to the element 5 position backward
auto dist = std::distance(my_vector.begin(), first); // returns distance between two iterators.

注意，std::distance 的第二個引數應該可以從第一個引數（或者，換句話說，first 應該小於或等於 second）。

即使你可以使用迭代器執行算術運算子，也不是所有型別的迭代器都定義了所有操作。a = b + 3; 適用於隨機訪問迭代器，但不適用於前向或雙向迭代器，它仍然可以通過類似 b = a; ++b; ++b; ++b; 的 3 位前進。因此，如果你不確定什麼是迭代器型別（例如，在接受迭代器的模板函式中），建議使用特殊函式。

迭代器概念

C++標準描述了幾種不同的迭代器概念。這些根據它們在所引用的序列中的行為進行分組。如果你知道迭代器模型的概念（行為類似），則*無論其所屬的順序如何，*都可以確保該迭代器的行為。它們通常按照從最受限制到最低限制的順序進行描述（因為下一個迭代器概念比它的前一步更好）：

輸入迭代器：每個位置只能解除引用一次。只能前進，一次只能一個位置。
Forward Iterators：一個可以被解除引用任意次數的輸入迭代器。
雙向迭代器：一個前向迭代器，也可以一次向後前進一個位置。
隨機訪問迭代器：一種雙向迭代器，可以一次向前或向後前進任意數量的位置。
連續迭代器（自 C++ 17 開始）：一個隨機訪問迭代器，它保證底層資料在記憶體中是連續的。

演算法可以根據給定的迭代器建模的概念而變化。例如，儘管可以為前向迭代器實現 random_shuffle，但是可以提供需要隨機訪問迭代器的更有效的變體。

迭代器特徵

迭代器特徵為迭代器的屬性提供統一的介面。它們允許你檢索值，差異，指標，引用型別以及迭代器類別：

template<class Iter>
Iter find(Iter first, Iter last, typename std::iterator_traits<Iter>::value_type val)  {
    while (first != last) {
        if (*first == val)
            return first;
        ++first;
    }
    return last;
}

迭代器的類別可用於專門化演算法：

template<class BidirIt>
void test(BidirIt a, std::bidirectional_iterator_tag)  {
    std::cout << "Bidirectional iterator is used" << std::endl;
}
 
template<class ForwIt>
void test(ForwIt a, std::forward_iterator_tag)  {
    std::cout << "Forward iterator is used" << std::endl;
}
 
template<class Iter>
void test(Iter a)  {
    test(a, typename std::iterator_traits<Iter>::iterator_category());
}

迭代器的類別基本上是迭代器概念，除了連續迭代器沒有自己的標記，因為它被發現會破壞程式碼。