C++ 双向迭代器

C++双向迭代器

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

概述

双向迭代器支持以下操作：

• 递增（++）以移动到下一个元素
• 递减（--）以移动到前一个元素
• 解引用（*）以访问当前元素
• 相等性比较（==和!=）

与随机访问迭代器不同，双向迭代器不支持：

• 算术运算（如iter + n）
• 关系比较（如<、>）
• 下标访问（如iter[n]）

双向迭代器的操作

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

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

代码示例

以下示例展示了如何在std::list中使用双向迭代器：

#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;
}

输出:

正向遍历: 10 20 30 40 50 
反向遍历: 50 40 30 20 10 
第一个元素: 10

实际应用场景

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

回文检测示例

#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;
}

输出:

racecar 是回文? true
hello 是回文? false

双向迭代器与其他迭代器的关系

双向迭代器位于迭代器层次结构中的中间位置：

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

数学表示

双向迭代器的数学性质可以表示为：

• 递增操作：$f:I\to I$，其中$I$是迭代器集合
• 递减操作：$g:I\to I$
• 满足：$g(f(i))=i$和$f(g(i))=i$（对于有效迭代器）

限制与注意事项

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

性能考虑

双向迭代器操作的时间复杂度：

• 递增/递减：O(1)
• 解引用：O(1)
• 比较：O(1)

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

总结

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