编辑“︁C++ 双向迭代器”︁（章节）

= C++双向迭代器 =

'''双向迭代器'''（Bidirectional Iterator）是C++标准模板库（STL）中的一种迭代器类别，它扩展了'''前向迭代器'''的功能，允许在容器中既向前又向后移动。双向迭代器是许多STL容器（如<code>std::list</code>、<code>std::set</code>、<code>std::map</code>）的基础迭代器类型。

== 概述 ==
双向迭代器支持以下操作：
* 递增（<code>++</code>）以移动到下一个元素
* 递减（<code>--</code>）以移动到前一个元素
* 解引用（<code>*</code>）以访问当前元素
* 相等性比较（<code>==</code>和<code>!=</code>）

与'''随机访问迭代器'''不同，双向迭代器不支持：
* 算术运算（如<code>iter + n</code>）
* 关系比较（如<code><</code>、<code>></code>）
* 下标访问（如<code>iter[n]</code>）

== 双向迭代器的操作 ==
以下是双向迭代器支持的主要操作：

{| class="wikitable"
|-
! 操作 !! 描述 !! 示例
|-
| <code>++iter</code> || 前置递增 || <code>auto it = list.begin(); ++it;</code>
|-
| <code>iter++</code> || 后置递增 || <code>auto it = list.begin(); it++;</code>
|-
| <code>--iter</code> || 前置递减 || <code>auto it = list.end(); --it;</code>
|-
| <code>iter--</code> || 后置递减 || <code>auto it = list.end(); it--;</code>
|-
| <code>*iter</code> || 解引用 || <code>int value = *it;</code>
|-
| <code>iter->member</code> || 成员访问 || <code>auto name = it->name;</code>
|-
| <code>==</code>, <code>!=</code> || 相等性比较 || <code>if (it1 == it2) {...}</code>
|}

== 代码示例 ==
以下示例展示了如何在<code>std::list</code>中使用双向迭代器：

<syntaxhighlight lang="cpp">
#include <iostream>
#include <list>

int main() {
    std::list<int> numbers = {10, 20, 30, 40, 50};

    // 正向遍历
    std::cout << "正向遍历: ";
    for (auto it = numbers.begin(); it != numbers.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 反向遍历
    std::cout << "反向遍历: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << "\n";

    // 双向移动
    auto it = numbers.begin();
    ++it; // 移动到第二个元素
    --it; // 移回第一个元素
    std::cout << "第一个元素: " << *it << "\n";

    return 0;
}
</syntaxhighlight>

'''输出:'''
<pre>
正向遍历: 10 20 30 40 50 
反向遍历: 50 40 30 20 10 
第一个元素: 10
</pre>

== 实际应用场景 ==
双向迭代器在以下场景中特别有用：
1. '''双向链表遍历'''：<code>std::list</code>只能使用双向迭代器
2. '''集合操作'''：<code>std::set</code>和<code>std::map</code>的迭代器也是双向的
3. '''回文检测'''：可以从两端同时遍历容器来检查回文

=== 回文检测示例 ===
<syntaxhighlight lang="cpp">
#include <iostream>
#include <list>
#include <string>

bool is_palindrome(const std::list<char>& lst) {
    auto forward = lst.begin();
    auto backward = lst.end();
    
    if (backward != lst.begin()) {
        --backward; // 移动到最后一个元素
    }

    while (forward != backward) {
        if (*forward != *backward) {
            return false;
        }
        
        ++forward;
        if (forward == backward) break;
        --backward;
    }
    return true;
}

int main() {
    std::list<char> word1 = {'r', 'a', 'c', 'e', 'c', 'a', 'r'};
    std::list<char> word2 = {'h', 'e', 'l', 'l', 'o'};

    std::cout << std::boolalpha;
    std::cout << "racecar 是回文? " << is_palindrome(word1) << "\n";
    std::cout << "hello 是回文? " << is_palindrome(word2) << "\n";

    return 0;
}
</syntaxhighlight>

'''输出:'''
<pre>
racecar 是回文? true
hello 是回文? false
</pre>

== 双向迭代器与其他迭代器的关系 ==
双向迭代器位于迭代器层次结构中的中间位置：

<mermaid>
graph TD
    A[输入迭代器] --> B[前向迭代器]
    B --> C[双向迭代器]
    C --> D[随机访问迭代器]
    C --> E[连续迭代器]
</mermaid>

== 数学表示 ==
双向迭代器的数学性质可以表示为：
* 递增操作：<math>f : I \rightarrow I</math>，其中<math>I</math>是迭代器集合
* 递减操作：<math>g : I \rightarrow I</math>
* 满足：<math>g(f(i)) = i</math>和<math>f(g(i)) = i</math>（对于有效迭代器）

== 限制与注意事项 ==
1. 双向迭代器不能用于需要随机访问的算法（如<code>std::sort</code>）
2. 递减操作在迭代器指向容器起始位置时是未定义行为
3. 对于空容器，<code>begin() == end()</code>，不应尝试递减<code>end()</code>

== 性能考虑 ==
双向迭代器操作的时间复杂度：
* 递增/递减：O(1)
* 解引用：O(1)
* 比较：O(1)

然而，由于不支持随机访问，某些操作（如计算两个迭代器之间的距离）需要O(n)时间。

== 总结 ==
双向迭代器提供了在容器中双向移动的能力，是许多STL容器的基础接口。理解双向迭代器对于有效使用<code>std::list</code>、<code>std::set</code>和<code>std::map</code>等容器至关重要。虽然不如随机访问迭代器强大，但双向迭代器在需要双向遍历的场景中提供了必要的功能。

[[Category:编程语言]]
[[Category:C++]]
[[Category:C++stl 迭代器]]