在 C++ 中，迭代器是一种用于遍历容器（如数组、向量、链表等）元素的对象。C++ 标准库提供了多种类型的迭代器，每种迭代器都有其特定的用途和特性。以下是 C++ 中常见的迭代器类型：

迭代器用法

1. 输入迭代器（Input Iterator）

输入迭代器允许从序列中读取数据，但不能修改数据。它们只支持单向遍历。

• 典型用途：读取输入流中的数据。
• 示例：std::istream_iterator

2. 输出迭代器（Output Iterator）

输出迭代器允许向序列中写入数据，但不能读取数据。它们也只支持单向遍历。

• 典型用途：写入输出流或容器。
• 示例：std::ostream_iterator

3. 前向迭代器（Forward Iterator）

前向迭代器支持单向遍历，可以读取和写入数据。它们可以多次遍历同一个序列。

• 典型用途：单链表、哈希表等。
• 示例：std::forward_list::iterator

4. 双向迭代器（Bidirectional Iterator）

双向迭代器支持双向遍历（前向和后向），可以读取和写入数据。

• 典型用途：双链表、平衡树等。
• 示例：std::list::iterator, std::set::iterator

5. 随机访问迭代器（Random Access Iterator）

随机访问迭代器支持在常数时间内进行任意位置的访问和修改。它们支持所有的迭代器操作，包括算术运算（如加减）。

• 典型用途：数组、向量等。
• 示例：std::vector::iterator, std::deque::iterator, std::array::iterator

6. 常量迭代器（Const Iterator）

常量迭代器类似于其他迭代器，但它们不允许修改所指向的元素。

• 典型用途：需要只读访问的场景。
• 示例：std::vector::const_iterator, std::list::const_iterator

7. 反向迭代器（Reverse Iterator）

反向迭代器用于反向遍历容器。它们将容器的 begin 和 end 反转过来。

• 典型用途：从容器的末尾向前遍历。
• 示例：std::vector::reverse_iterator, std::list::reverse_iterator

迭代器的层次结构

迭代器的层次结构可以用以下图示表示：

Input Iterator
    |
    +-- Forward Iterator
            |
            +-- Bidirectional Iterator
                    |
                    +-- Random Access Iterator

Output Iterator

示例代码

以下是一些使用不同迭代器的示例代码：

#include <iostream>
#include <vector>
#include <list>
#include <set>
#include <algorithm>
#include <iterator>

int main() {
    // 使用随机访问迭代器遍历 vector
    std::vector<int> vec = {1, 2, 3, 4, 5};
    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用双向迭代器遍历 list
    std::list<int> lst = {1, 2, 3, 4, 5};
    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 使用反向迭代器遍历 vector
    for (std::vector<int>::reverse_iterator rit = vec.rbegin(); rit != vec.rend(); ++rit) {
        std::cout << *rit << " ";
    }
    std::cout << std::endl;

    // 使用常量迭代器遍历 set
    std::set<int> s = {1, 2, 3, 4, 5};
    for (std::set<int>::const_iterator cit = s.cbegin(); cit != s.cend(); ++cit) {
        std::cout << *cit << " ";
    }
    std::cout << std::endl;

    return 0;
}

这些示例展示了如何使用不同类型的迭代器来遍历各种容器。理解和正确使用这些迭代器可以帮助你编写更高效和更具可读性的代码。

自定义迭代器

设计一个自定义迭代器可以让你更好地控制容器的遍历行为。在 C++ 中，实现自定义迭代器需要遵循标准迭代器的接口和惯例。以下是一个简单的示例，展示如何设计一个自定义迭代器来遍历一个自定义容器。

自定义容器和迭代器示例

假设我们有一个简单的自定义容器 MyContainer，它存储整数，并且我们要为它设计一个自定义迭代器 MyIterator。

自定义容器MyContainer

#include <iostream>

class MyContainer {
public:
    MyContainer(int* data, size_t size) : data_(data), size_(size) {}

    // 嵌套的自定义迭代器类
    class MyIterator {
    public:
        MyIterator(int* ptr) : ptr_(ptr) {}

        // 解引用运算符
        int& operator*() { return *ptr_; }

        // 前置++运算符
        MyIterator& operator++() {
            ++ptr_;
            return *this;
        }

        // 后置++运算符
        MyIterator operator++(int) {
            MyIterator temp = *this;
            ++(*this);
            return temp;
        }

        // 相等运算符
        bool operator==(const MyIterator& other) const { return ptr_ == other.ptr_; }

        // 不相等运算符
        bool operator!=(const MyIterator& other) const { return ptr_ != other.ptr_; }

    private:
        int* ptr_;
    };

    // 返回容器的起始迭代器
    MyIterator begin() { return MyIterator(data_); }

    // 返回容器的结束迭代器
    MyIterator end() { return MyIterator(data_ + size_); }

private:
    int* data_;
    size_t size_;
};

示例代码

以下是一个使用 MyContainer 和 MyIterator 的示例代码：

#include <iostream>

// 自定义容器和迭代器的定义（如上所示）

int main() {
    int data[] = {1, 2, 3, 4, 5};
    MyContainer container(data, 5);

    // 使用自定义迭代器遍历容器
    for (MyContainer::MyIterator it = container.begin(); it != container.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

详细解释

• 自定义容器 MyContainer：这是一个简单的类，包含一个整数数组和数组的大小。
• 嵌套的自定义迭代器类 MyIterator：构造函数：接受一个指向整数的指针。解引用运算符 (operator*)：返回当前指针指向的整数引用。前置和后置递增运算符 (operator++)：用于遍历数组。相等和不相等运算符 (operator== 和 operator!=)：用于比较迭代器是否相等。
• begin 和 end 方法：返回容器的起始和结束迭代器。

扩展功能

你可以扩展这个示例以支持更多功能，例如双向迭代器、随机访问迭代器等。以下是一些可能的扩展：

• 双向迭代器：实现前置和后置递减运算符 (operator--)。
• 随机访问迭代器：实现加减运算符 (operator+, operator-) 以及索引运算符 (operator[])。

总结

设计自定义迭代器需要遵循标准迭代器的接口和惯例。通过实现必要的运算符和方法，你可以创建适合你自定义容器的迭代器。这不仅使你的容器更加灵活和强大，还能与标准库中的算法和容器无缝集成。

数组、向量、链表遍历 示例

使用迭代器遍历数组

虽然数组本身不提供标准库迭代器，但我们可以使用指针来模拟迭代器的行为。

#include <iostream>

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int* begin = std::begin(arr);
    int* end = std::end(arr);

    for (int* it = begin; it != end; ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    return 0;
}

使用迭代器遍历向量

向量（std::vector）是 C++ 标准库提供的动态数组，它提供了标准的迭代器接口。

#include <iostream>
#include <vector>

int main() {
    std::vector<int> vec = {1, 2, 3, 4, 5};

    for (std::vector<int>::iterator it = vec.begin(); it != vec.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 也可以使用范围 for 循环
    for (const auto& elem : vec) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

使用迭代器遍历链表

链表（std::list）是 C++ 标准库提供的双向链表，它也提供了标准的迭代器接口。

#include <iostream>
#include <list>

int main() {
    std::list<int> lst = {1, 2, 3, 4, 5};

    for (std::list<int>::iterator it = lst.begin(); it != lst.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;

    // 也可以使用范围 for 循环
    for (const auto& elem : lst) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}