迭代器和指针有何关系？

Question

使用迭代器的代码看起来非常类似于使用指针的代码。迭代器是一些晦涩的类型（例如 std::vector::iterator）。

我不明白的是迭代器和指针如何相互关联 - 迭代器是指针的包装器，具有重载操作以前进到相邻元素还是其他东西？

Answer 1

迭代器是指针的泛化。

迭代器（取决于变体）必须实现 * 和 ++

因此指针就是迭代器。但反过来也不一定。

如果你想迭代一个复杂的结构（一棵树，一个图......），迭代器将不仅仅是一个指针，并且不会对内存中的某些实际位置进行任何引用。

Answer 2

迭代器是重载某些运算符的对象，因此用法看起来就像它们是指针。这在给定迭代器类别的能力范围内。随机访问迭代器看起来完全像指针，其他类型的迭代器不提供某些操作（例如双向的 list::iterator 没有运算符 += 其中许多需要随机访问）。

至于“晦涩的名称”，使用普通指针作为迭代器并非完全不可想象：

 template <class T>
 class MyContainer
 {
     ...
     typedef T* iterator;
 }

 MyContainer<int>::iterator it; //the type is really int*

Answer 3

从概念上讲，是的——但它们不必是指针。它们的内部结构和功能将取决于它们“包装”的数据结构。

这就是为什么有不同的迭代器“类”。例如，单向、双向、随机访问等。

有些能够支持多个类别。

例如，如果内部结构是红黑树或链表，则迭代器可能是双向的，但不是随机访问的。如果它们包装一个向量（作为数组实现），您将拥有随机访问和双向。

Answer 4

迭代器只是一种提供迭代器所需接口的类型 - 对于不同类型的迭代器，这些接口是不同的，并在 C++ 标准（迭代器要求）第 24.1 节中指定。

迭代器的实现方式取决于它们迭代的内容 - 对于向量，它们通常是指向数组的单个指针的包装器（无论如何在发布版本中），对于更复杂的容器，它们有更复杂的实现。对于开放式范围，它们将包含用于生成元素的任何算法的状态。

请注意，指向数组中元素的指针满足随机访问迭代器的要求，因此在某种程度上它们是可以互换的。

Answer 5

正如所说：迭代器是指针的泛化。每个指针都是一个迭代器，但并非每个迭代器都是指针（尽管大多数非指针迭代器都包含指针）。

迭代器是一种接口（或概念）。我们可以如下定义最小迭代器接口：

template <typename T>
class iterator
{
    // Advance to the next element of the collection.
    virtual void operator++() = 0;

    // Get access to the element associated with the iterator.
    virtual const T &operator*() = 0;
};

但是迭代器没有真正的抽象基类。所有以迭代器为参数的函数都是模板函数，并且迭代器参数的类型是使用模板定义的。这称为静态多态性。我们可以使用 std::vector 构造函数 作为示例：

template< class InputIt >
vector::vector( InputIt first, InputIt last );

由于 InputIt 是使用模板定义的类型，并且由于所有指针都支持 operator++() 和 operator*()，因此所有指针可以用作迭代器。例如：

int arr[3] = {1, 2, 3};
int *begin = &arr[0];
int *end   = &arr[3];

// Initialize vector from a pair of iterators.
std::vector<int> v(begin, end); // The vector `v` will copy to itself
                               // all elements of `arr` in the range from
                              // arr[0] (including) to arr[3] (excluding).

or

std::string str = "hello";
std::string *begin = &str;
std::string *end   = begin + 1;

// Initialize vector from a pair of iterators.
std::vector<std::string> v(begin, end); // The vector `v` will contain
                                       // a single element which is
                                      // string "hello".

由于迭代器只是一个抽象接口，因此指针并不是迭代器的唯一示例。任何重写 operator++() 和 operator*() 的类都可以用作迭代器。通常容器使用自定义类作为迭代器而不是指针。但有些函数仍然使用指针作为迭代器。一个例子是 std::begin 和 < a href="https://en.cppreference.com/w/cpp/iterator/end" rel="nofollow noreferrer">std::end 静态数组函数：

template< class T, std::size_t N >
T* begin( T (&array)[N] );

template< class T, std::size_t N >
T* end( T (&array)[N] );

有是不同类型的迭代器。最高级的迭代器类型是随机访问迭代器。除了 operator++() 和 operator*() 之外，它还支持许多其他操作，例如向后推进 (operator--()) 或向前推进许多元素单步（operator+=(size_t n)）。指针是随机访问迭代器。

这就是指针和迭代器的关系。

继续。迭代器是允许迭代某些元素集合的对象类。指针只是迭代器的一个示例，但还有其他迭代器。