当前位置：首页 > article >正文

重温设计模式--C++迭代器种类和用法

article 2024/12/28 2:05:23

文章目录

- - 定义
  - 1、输入迭代器（Input Iterator
  - 2、输出迭代器（Output Iterator）
  - 3、前向迭代器（Forward Iterator）
  - 4、双向迭代器（Bidirectional Iterator）
  - 5、随机访问迭代器（Random - Access Iterator）

定义

它提供了一种方法来顺序访问一个聚合对象（如数组、列表、树等各种容器类型的数据结构）中的各个元素，而又无需暴露该聚合对象的内部表示

1、输入迭代器（Input Iterator

定义和特点：
- 输入迭代器是一种只读迭代器，它能够从一个序列中读取元素，并且只能单向向前移动。其主要目的是用于支持对容器元素的顺序读取操作，就像从一个输入流（如std::istream）中读取数据一样。
- 它支持的操作包括解引用（*操作符）以获取当前元素的值、++操作符来将迭代器移动到下一个元素位置，并且可以通过==和!=操作符来比较两个迭代器是否指向相同的位置。但是，一旦迭代器向前移动，就不能再回到之前的位置。
应用场景：
- 适用于单次遍历容器元素的场景，比如在从标准输入读取数据并存入容器后，使用输入迭代器来逐个读取容器中的数据进行处理，且不需要修改数据，也不需要多次遍历。例如，将std::cin读取的整数序列存入std::vector后，使用输入迭代器来计算这些整数的和。

示例代码片段：

以下是一个简单的示例，使用std::istream_iterator（这是C++标准库中基于输入迭代器概念实现的迭代器类型）从std::cin读取整数，并存入std::vector，然后再使用输入迭代器遍历vector并输出整数。

#include <iostream>
#include <vector>
#include <iterator>
int main() {
    std::vector<int> numbers;
    std::istream_iterator<int> inputIt(std::cin), endIt;
    while (inputIt!= endIt) {
        numbers.push_back(*inputIt);
        ++inputIt;
    }
    std::istream_iterator<int> outputIt(numbers.begin());
    while (outputIt!= numbers.end()) {
        std::cout << *outputIt << " ";
        ++outputIt;
    }
    std::cout << std::endl;
    return 0;
}

2、输出迭代器（Output Iterator）

定义和特点：
- 输出迭代器主要用于向容器或其他输出目标写入数据，同样是单向的，不过它侧重于数据的输出操作。与输入迭代器类似，它也支持++操作符来移动位置，并且可以通过解引用操作符*来将数据写入到当前位置，但解引用操作主要用于赋值，而不是获取值。
应用场景：
- 常用于将数据写入容器的场景，例如将一个计算结果序列逐个存入容器中。在对容器进行填充新元素的操作，特别是从其他数据源生成数据并填充到容器时，输出迭代器很有用。

示例代码片段：

以下示例使用std::ostream_iterator（C++标准库中的输出迭代器类型）将一个整数序列输出到std::cout，它将数据从容器（这里是vector）中逐个取出并输出到控制台。

#include <iostream>
#include <vector>
#include <iterator>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::ostream_iterator<int> outputIt(std::cout, " ");
    for (int num : numbers) {
        *outputIt = num;
        ++outputIt;
    }
    std::cout << std::endl;
    return 0;
}

3、前向迭代器（Forward Iterator）

定义和特点：
- 前向迭代器在输入迭代器和输出迭代器的基础上提供了更多的功能，它不仅可以单向向前移动，而且可以多次遍历同一个序列。它支持所有输入迭代器和输出迭代器的操作，同时解引用操作更加灵活，既可以读取也可以修改元素的值。
应用场景：
- 在需要对容器元素进行多次读取和修改操作的场景中很有用。例如，在一个算法中，可能需要多次遍历一个容器来更新元素的值，或者在一个容器中查找满足特定条件的元素，然后对这些元素进行修改。

示例代码片段：

以下是一个简单的示例，使用自定义的前向迭代器（假设已经有一个自定义的容器类和对应的前向迭代器类实现）来遍历容器并将每个元素的值加倍。

class MyForwardIterator;
class MyContainer {
public:
    MyForwardIterator begin();
    MyForwardIterator end();
    // 其他容器相关的操作
};
class MyForwardIterator {
public:
    MyForwardIterator& operator++();
    int& operator*();
    bool operator==(const MyForwardIterator& other) const;
    bool operator!=(const MyForwardIterator& other) const;
    // 其他迭代器相关的操作
};
void doubleElements(MyContainer& container) {
    MyForwardIterator it = container.begin();
    MyForwardIterator endIt = container.end();
    while (it!= endIt) {
        *it *= 2;
        ++it;
    }
}

4、双向迭代器（Bidirectional Iterator）

定义和特点：
- 双向迭代器在继承前向迭代器功能的基础上，增加了向后移动的能力。它可以通过--操作符将迭代器向反方向移动，从而能够更加灵活地在容器元素之间进行遍历。双向迭代器支持所有前向迭代器的操作，同时还支持反向移动操作。
应用场景：
- 在需要在容器中双向移动的场景中非常有用。例如，在处理双向链表这种数据结构时，或者在一个算法中需要根据某些条件来回遍历容器元素的情况，如在一个排序算法中，可能需要先正向遍历找到一个合适的位置，然后再反向遍历来调整元素的顺序。

示例代码片段：

以std::list为例，std::list的迭代器是双向迭代器。以下代码展示了如何使用双向迭代器在std::list中双向移动并操作元素。

#include <iostream>
#include <list>
int main() {
    std::list<int> numbers = {1, 2, 3, 4, 5};
    std::list<int>::iterator it = numbers.begin();
    // 正向遍历并输出
    while (it!= numbers.end()) {
        std::cout << *it << " ";
        ++it;
    }
    std::cout << std::endl;
    it = numbers.end();
    --it;
    // 反向遍历并输出
    while (it!= numbers.begin()) {
        std::cout << *it << " ";
        --it;
    }
    std::cout << *it << std::endl;
    return 0;
}

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

定义和特点：
- 随机访问迭代器是功能最强大的一种迭代器类型，它除了支持双向迭代器的所有操作外，还支持通过索引（类似数组下标）的方式直接访问容器中的任意元素。可以使用[]操作符进行随机访问，还可以进行迭代器之间的算术运算，如+、-、+=、-=等操作，来快速地在容器元素之间进行跳转。
应用场景：
- 在需要高效地访问容器中任意位置元素的场景中非常有用。例如，在对数组或者std::vector这种支持随机访问的数据结构进行快速排序、二分查找等算法时，随机访问迭代器能够大大提高算法的效率，因为可以直接定位到需要操作的元素位置，而不需要逐个移动迭代器来访问。

示例代码片段：

以下以std::vector为例，展示随机访问迭代器的使用。

#include <iostream>
#include <vector>
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    std::vector<int>::iterator it = numbers.begin();
    // 通过随机访问迭代器直接访问第三个元素（索引为2）
    std::cout << numbers[2] << std::endl;
    // 使用算术运算移动迭代器
    it += 3;
    std::cout << *it << std::endl;
    return 0;
}

不是所有的STL迭代器都是随机访问迭代器
- STL（标准模板库）中有多种容器，每种容器所提供的迭代器类型不同，以适应其内部数据结构的特性和访问需求。
- 输入迭代器（Input Iterator）和输出迭代器（Output Iterator）相关容器：
  - 在一些基于流的操作或者单次单向数据读取/写入场景下会涉及到这两类迭代器相关的概念。例如，istream_iterator和ostream_iterator分别是输入迭代器和输出迭代器类型。它们主要用于从输入流（如std::cin）读取数据到容器或者将容器中的数据输出到输出流（如std::cout），这种迭代器不支持随机访问，而是单向的读取或写入操作。
- 前向迭代器（Forward Iterator）相关容器：
  - forward_list（单向链表）是一个典型的提供前向迭代器的容器。前向迭代器可以单向向前移动，并且可以多次遍历序列，但不支持像随机访问迭代器那样通过索引直接访问元素或者进行迭代器的算术运算。例如，对于std::forward_list<int> flist;，其迭代器只能使用++操作符向前移动来遍历链表中的元素。
- 双向迭代器（Bidirectional Iterator）相关容器：
  - list（双向链表）和set、multiset、map、multimap（关联容器）等提供的是双向迭代器。以std::list为例，它的迭代器可以向前和向后移动，通过--操作符实现反向遍历，但是也不支持像随机访问迭代器一样的索引访问方式。例如，对于std::list<int> myList;，可以使用myList.begin()和myList.end()获取双向迭代器，然后在列表元素之间双向移动，但不能像在vector中那样使用[]操作符直接访问元素。
部分STL容器提供随机访问迭代器
- vector和deque容器：
  - vector（动态数组）和deque（双端队列）是STL中提供随机访问迭代器的典型容器。它们内部的数据结构允许通过索引直接访问元素，就像访问数组元素一样。例如，对于std::vector<int> vec;，可以使用vec[3]来直接访问索引为3的元素，也可以通过迭代器进行算术运算，如vec.begin() + 5来获取指向第6个元素（索引为5）的迭代器。这种随机访问的特性使得vector和deque在很多需要高效访问元素的算法中表现出色，比如快速排序、二分查找等算法可以充分利用这种随机访问迭代器的优势来提高效率。
- array容器：
  - array是一个固定大小的数组容器，它也提供随机访问迭代器。由于其大小在编译时就已经确定，和普通数组类似，它支持通过索引直接访问元素，其迭代器也具备随机访问的能力，如std::array<int, 5> arr;，可以使用arr[2]访问元素，也可以利用随机访问迭代器进行其他操作。