概述

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());
}

迭代器的类别基本上是迭代器概念，除了连续迭代器没有自己的标记，因为它被发现会破坏代码。