C++ 总览

示例

迭代器就是位置

迭代器是对一系列元素进行导航和操作的一种手段，并且是指针的通用扩展。从概念上讲，重要的是要记住，迭代器是位置，而不是元素。例如，采取以下顺序：

A B C

该序列包含三个元素和四个位置

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

元素是序列中的事物。位置是可以对序列进行有意义的操作的位置。例如，一个插入到元素A之前或之后的位置，而不插入一个元素。删除元素（erase(A)）的方法是先找到其位置，然后删除它。

从迭代器到值

为了从位置转换为值，需要取消迭代器的引用：

auto my_iterator = my_vector.begin(); // 位置
auto my_value = *my_iterator; // 值

可以将迭代器视为对序列中引用的值的取消引用。这对于理解为什么不应该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(); // 首先有效
} // foo超出范围并被销毁
// 此时首先无效

C ++标准库中的许多算法和序列成员函数都有控制迭代器何时无效的规则。每种算法在处理（和使迭代器无效）方式上都不同。

使用迭代器导航

众所周知，迭代器用于导航序列。为此，迭代器必须在整个序列中迁移其位置。迭代器可以按顺序向前推进，而某些可以向后推进：

auto first = my_vector.begin();
++first;                                             // 推进迭代器1的位置
std::advance(first, 1);                              // 推进迭代器1的位置
first = std::next(first);                            // 返回迭代器到下一个元素
std::advance(first, -1);                             // 推进迭代器1的位置 backwards
first = std::next(first, 20);                        // 返回迭代器到元素20的位置
first = std::prev(first, 5);                         // 将迭代器返回到元素5的后退位置
auto dist = std::distance(my_vector.begin(), first); // 返回两个迭代器之间的距离。

请注意，std :: distance的第二个参数应该可以从第一个参数到达（或者换句话说，first应该小于或等于second）。

即使您可以使用迭代器执行算术运算符，也未为所有类型的迭代器定义所有操作。a = b + 3;将适用于随机访问迭代器，但不适用于正向或双向迭代器，仍然可以通过3位将其前进，例如b = a; ++b; ++b; ++b;。因此，建议您在不确定什么是迭代器类型的情况下使用特殊功能（例如，在接受迭代器的模板函数中）。

迭代器概念

C ++标准描述了几种不同的迭代器概念。根据它们在所引用序列中的行为将它们分组。如果您知道迭代器建模的概念（行为类似），则可以确保该迭代器的行为不受其所属的顺序影响。通常按照从最高到最低的顺序来描述它们（因为下一个迭代器概念比其前身要好一步）：

• 输入迭代器：每个位置只能解引用一次。只能前进，一次只能一个位置。

• 转发迭代器：可以多次取消引用的输入迭代器。

• 双向迭代器：一种向前迭代器，也可以一次向后移动一个位置。

• 随机访问迭代器：双向迭代器，一次可以向前或向后移动任意数量的位置。

• 连续迭代器（自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());
}

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