C++迭代器：概念、分类与应用

### C++迭代器：概念、分类与应用 #### 1. 数据结构与迭代器概述 在C++编程中，数据的组织方式对操作效率有着显著影响。STL（标准模板库）提供了多种容器类型，在选择不同的数据结构时，STL容器的渐近复杂度是需要考虑的关键因素。同时，现代处理器的缓存层次结构也影响着数据的组织方式，高效利用缓存级别至关重要，这也是像`std::vector`和`std::string`这类在内存中连续存储元素的容器被广泛使用的原因之一。 迭代器是C++中一个非常重要的概念，它是STL算法的基础。虽然其语法类似于普通的C指针，但功能却十分强大。通过一些示例，我们可以学习如何创建一个用于迭代线性范围的自定义迭代器。 #### 2. 迭代器的基本概念 迭代器本质上是一个表示序列中位置的对象，它基本包含以下功能： - `is_end()`：判断是否超出序列范围，返回布尔值。 - `read()`：获取当前位置的值。 - `step_fwd()`：移动到下一个位置。 需要注意的是，这些命名函数在C++中并不实际存在，只是为了便于理解。在实际实现中，它们基于C指针语义。 除了上述基本功能，许多算法还要求迭代器能够向后移动以及向特定位置写入值，因此还可能需要以下功能： - `write(T val)`：向当前位置写入值。 - `step_bwd()`：移动到上一个位置。 - `step(int n)`：移动指定数量的元素。 此外，对于一些数据源，如用户输入、网络连接或文件，读写操作可能意味着向前移动，因此还需要以下功能： - `write_step_fwd(T val)`：写入并向前移动。 - `read_step_fwd(T val)`：读取并向前移动。 `step(int n)`函数看似多余，因为它可以通过多次调用`step_fwd()`或`step_bwd()`来实现，但对于一些算法，如二分查找，需要迭代器能够在常量时间内移动多个位置，以提高效率。 #### 3. 迭代器的分类 不同的算法对迭代器的要求不同，STL将这些要求分为以下四种基本迭代器类别： - **forward_iterator**：只能向前移动。 - **bidirectional_iterator**：可以向前和向后移动。 - **random_access_iterator**：可以在常量时间内移动任意数量的步骤。 - **contiguous_iterator**：底层数据是连续的内存块，如`std::string`、`std::vector`、`std::array`和很少使用的`std::valarray`。 此外，支持`read_step_fwd()`和`write_step_fwd()`的迭代器也有相应的类别： - **input_iterator**：支持`read_step_fwd() -> T`。 - **output_iterator**：支持`write_step_fwd(T) -> void`。 以下是不同算法对迭代器功能的要求总结： | 算法 | 所需迭代器功能 | | ---- | ---- | | 统计值的出现次数 | `is_end()`、`read()`、`step_fwd()` | | 用值填充容器 | `is_end()`、`write()`、`step_fwd()` | | 排序范围上的二分查找 | `step()`、`read()` | | 重新排列元素 | `read()`、`write()`、`step_fwd()`、`step_bwd()` | #### 4. 指针模拟语法 C++迭代器的语法基于标准C指针表示法，这意味着基于迭代器构建的任何算法也适用于常规C指针。 ##### 4.1 移动函数的实现 移动函数通过指针算术实现，以下是每个移动函数重载的运算符及使用示例： | 表示的函数 | 重载的运算符 | 使用示例 | | ---- | ---- | ---- | | `step_fwd() -> void` | `operator++()` | `++it;` | | `step_bwd() -> void` | `operator--()` | `--it;` | | `step(int n) -> void` | `operator+=(int n)` | `it += 5;` | ##### 4.2 读写函数的实现 `read()`和`write()`函数通过`operator*`实现，就像解引用指针一样： | 表示的函数 | 使用示例 | | ---- | ---- | | `read() -> T` | `auto value = *it;` | | `write(T val) -> void` | `*it = T{};` | ##### 4.3 判断是否结束的实现 `is_end() -> bool`函数通过与一个表示迭代器超出范围边界的值进行比较来实现。以下是在常规C数组指针算术和链表中实现`is_end()`的示例： ```cpp // C-style array int array[3] = {22, 44, 66}; int* begin = &array[0]; int* end = &array[3]; for( int* ptr = begin; ptr != end; ++ptr ) { } // C-style linked list struct Element { Element* next_;}; Element a, b, c; a.next_ = &b; b.next_ = &c; c.next_ = nullptr; Element* begin = &a; Element* end = nullptr; for( auto ptr = begin; ptr != nullptr; ptr = ptr->next_ ) { } ``` 当在C++中实现迭代器时，无论迭代器迭代的是什么，都需要使用相同的方法。实现`is_end()`函数的等效方法是将迭代器与一个表示序列结束的值进行比较。 对于输入/输出迭代器使用的`read_step_fwd()`和`write_step_fwd()`函数，只能通过两个连续的表达式来表达。 在实现高级迭代器时，使用Boost库的迭代器外观（iterator facade）是很有优势的，在其中可以像上面的示例函数一样以命名函数的形式实现功能，迭代器外观会处理向运算符的转换。更多信息可参考：http://www.boost.org。 #### 5. 作为生成器的迭代器 深入研究迭代器概念可以发现，迭代器实际上并不需要指向实际数据，我们可以动态生成值。以下是一个简单的前向迭代器实现，它可以动态生成整数： ```cpp class IntIterator { public: IntIterator(int v) : v_{v} {} auto operator==(const IntIterator& it)const{ return v_ == it.v_; } auto operator!=(const IntIterator& it)const{ return !(*this==it); } auto& operator*() const { return v_; } auto& operator++() { ++v_; return *this; } private: int v_{}; }; ``` 可以使用`IntIterator`来迭代一个递增的整数范围，就像迭代一个值的容器一样： ```cpp auto first = IntIterator{12}; // Start at 12 auto last = IntIterator{16}; // Stop when equal to 16 for(auto it = first; it != last; ++it) { std::cout << (*it) << " "; } // Prints 12 13 14 15 ``` #### 6. 迭代器特性 STL通过迭代器满足的类别来区分迭代器，这通过在迭代器类中定义以下五种特定类型来实现： - `iterator_category`：迭代器满足的类别。 - `difference_type`：用于存储两个迭代器之间距离的类型。 - `value_type`：解引用迭代器时返回的值的类型。 - `reference`：用于引用`value_type`的类型。 - `pointer`：用于指向`value_type`的指针类型。 对于`IntIterator`，应定义以下类型： ```cpp class IntIterator { public: ... using difference_type = int; using value_type = int; using referen ```