C++ 反向迭代器

什么是反向迭代器？

反向迭代器是C++ STL（标准模板库）中的一种特殊迭代器，它允许我们以相反的顺序遍历容器中的元素。与普通迭代器从开始到结束遍历不同，反向迭代器从容器的最后一个元素开始，向前移动直到第一个元素。

备注

反向迭代器实际上是对普通迭代器的一种适配，通过改变迭代器的移动方向和取值方式来实现逆序访问。

为什么需要反向迭代器？

在很多编程场景中，我们需要从后向前处理数据，例如：

• 查找字符串中最后一个特定字符
• 逆序输出容器内容
• 从后向前应用某些算法
• 需要同时进行正向和反向遍历的场景

使用反向迭代器可以让这些操作变得简单而优雅，不需要我们手动计算索引或编写复杂的循环。

反向迭代器的种类

C++ STL中提供了几种反向迭代器：

1. reverse_iterator - 可读可写的反向迭代器
2. const_reverse_iterator - 只读的反向迭代器

获取反向迭代器的方法

大多数STL容器都支持反向迭代器，可以通过以下成员函数获取：

• rbegin() - 返回指向容器最后一个元素的反向迭代器
• rend() - 返回指向容器第一个元素之前位置的反向迭代器
• crbegin() - 返回常量反向迭代器（C++11起）
• crend() - 返回常量反向迭代器（C++11起）

使用反向迭代器

让我们通过一些例子来了解反向迭代器的使用：

基本用法

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 使用反向迭代器遍历容器
    std::cout << "使用反向迭代器遍历: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环和反向迭代器遍历（C++11）
    std::cout << "使用范围for循环遍历: ";
    for (auto& num : std::vector<int>(numbers.rbegin(), numbers.rend())) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

使用反向迭代器遍历: 5 4 3 2 1 
使用范围for循环遍历: 5 4 3 2 1 

在不同容器中使用反向迭代器

cpp

#include <iostream>
#include <vector>
#include <list>
#include <string>

int main() {
    // 在向量中使用反向迭代器
    std::vector<int> vec = {10, 20, 30, 40, 50};
    std::cout << "Vector逆序: ";
    for (auto it = vec.rbegin(); it != vec.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 在列表中使用反向迭代器
    std::list<char> letters = {'a', 'b', 'c', 'd', 'e'};
    std::cout << "List逆序: ";
    for (auto it = letters.rbegin(); it != letters.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 在字符串中使用反向迭代器
    std::string text = "Hello World";
    std::cout << "String逆序: ";
    for (auto it = text.rbegin(); it != text.rend(); ++it) {
        std::cout << *it;
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

Vector逆序: 50 40 30 20 10 
List逆序: e d c b a 
String逆序: dlroW olleH

反向迭代器的工作原理

反向迭代器的行为可能会让初学者感到困惑。这是因为反向迭代器在内部实际上是基于普通迭代器实现的，但做了一些调整：

1. 当创建反向迭代器时，它会引用原始迭代器前面的元素
2. 当对反向迭代器进行递增操作时，实际上是对原始迭代器进行递减操作

这种关系可以用下图表示：

提示

记住：rbegin() 指向最后一个元素，而 rend() 指向第一个元素之前的位置（这与普通迭代器的 begin() 和 end() 刚好相反）。

使用 reverse_iterator 适配器

C++标准库提供了 std::reverse_iterator 适配器，可以将普通迭代器转换为反向迭代器：

cpp

#include <iostream>
#include <vector>
#include <iterator>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 创建一个指向numbers末尾的普通迭代器
    auto it = numbers.end();
    
    // 将普通迭代器转换为反向迭代器
    std::reverse_iterator<std::vector<int>::iterator> rev_it(it);
    
    // 此时rev_it指向最后一个元素
    --rev_it; // 必须先递减，因为end()指向末尾之后
    std::cout << "反向迭代器当前指向: " << *rev_it << std::endl;
    
    // 将反向迭代器转回普通迭代器
    auto original_it = rev_it.base();
    std::cout << "转回的普通迭代器当前指向: " << *original_it << std::endl;
    
    return 0;
}

输出：

反向迭代器当前指向: 5
转回的普通迭代器当前指向: 1

base()方法

反向迭代器提供了一个 base() 方法，可以获取对应的普通迭代器。需要注意的是，反向迭代器和其对应的基础迭代器并不指向同一个元素：

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    auto rit = numbers.rbegin(); // 指向50
    std::cout << "反向迭代器指向: " << *rit << std::endl;
    
    auto it = rit.base(); // base()返回的迭代器指向反向迭代器后面的元素
    std::cout << "对应的基础迭代器指向: " << *(it-1) << std::endl;
    
    return 0;
}

输出：

反向迭代器指向: 50
对应的基础迭代器指向: 50

实际应用场景

场景一：查找字符串中最后一个匹配字符

cpp

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::string text = "Hello world, welcome to C++ programming!";
    
    // 查找最后一个'o'
    auto it = std::find(text.rbegin(), text.rend(), 'o');
    
    if (it != text.rend()) {
        // 计算正向位置
        size_t position = std::distance(it, text.rend()) - 1;
        std::cout << "最后一个'o'的位置: " << position << std::endl;
        std::cout << "完整字符串: " << text << std::endl;
        std::cout << "位置指示: ";
        
        for (size_t i = 0; i < text.length(); ++i) {
            if (i == position) {
                std::cout << "^";
            } else {
                std::cout << " ";
            }
        }
        std::cout << std::endl;
    } else {
        std::cout << "字符'o'未找到" << std::endl;
    }
    
    return 0;
}

输出：

最后一个'o'的位置: 27
完整字符串: Hello world, welcome to C++ programming!
位置指示:                            ^

场景二：回文检测

cpp

#include <iostream>
#include <string>
#include <algorithm>

bool isPalindrome(const std::string& str) {
    // 移除所有非字母字符并转为小写
    std::string cleanStr;
    for (char c : str) {
        if (std::isalpha(c)) {
            cleanStr.push_back(std::tolower(c));
        }
    }
    
    // 创建反向字符串
    std::string reversedStr(cleanStr.rbegin(), cleanStr.rend());
    
    // 比较两个字符串
    return cleanStr == reversedStr;
}

int main() {
    std::string test1 = "A man, a plan, a canal, Panama";
    std::string test2 = "race a car";
    
    std::cout << "\"" << test1 << "\" 是回文吗? " 
              << (isPalindrome(test1) ? "是" : "否") << std::endl;
    
    std::cout << "\"" << test2 << "\" 是回文吗? " 
              << (isPalindrome(test2) ? "是" : "否") << std::endl;
    
    return 0;
}

输出：

"A man, a plan, a canal, Panama" 是回文吗? 是
"race a car" 是回文吗? 否

场景三：逆序打印容器的同时保持原始顺序

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    // 打印原始顺序
    std::cout << "原始顺序: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用反向迭代器打印，无需修改原容器
    std::cout << "反向打印: ";
    for (auto it = numbers.rbegin(); it != numbers.rend(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 打印原始顺序，确认容器未修改
    std::cout << "再次打印原始顺序: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出：

原始顺序: 1 2 3 4 5 
反向打印: 5 4 3 2 1 
再次打印原始顺序: 1 2 3 4 5 

反向迭代器与算法

STL算法可以与反向迭代器一起使用，实现逆序操作：

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> numbers = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    
    // 使用反向迭代器排序（降序）
    std::sort(numbers.rbegin(), numbers.rend());
    
    std::cout << "降序排序结果: ";
    for (const auto& num : numbers) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用反向迭代器查找
    auto it = std::find(numbers.rbegin(), numbers.rend(), 4);
    
    if (it != numbers.rend()) {
        std::cout << "在降序排序后，4的位置是第 " 
                  << std::distance(numbers.rbegin(), it) + 1 
                  << " 个元素" << std::endl;
    }
    
    return 0;
}

输出：

降序排序结果: 9 8 7 6 5 4 3 2 1 
在降序排序后，4的位置是第 6 个元素

注意事项和常见陷阱

1. 迭代器失效

与普通迭代器一样，当容器结构发生变化（如添加或删除元素）时，反向迭代器也可能失效。

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5};
    
    auto rit = numbers.rbegin();
    std::cout << "当前元素: " << *rit << std::endl; // 输出5
    
    // 删除最后一个元素（反向迭代器的第一个元素）
    numbers.pop_back();
    
    // 危险操作！rit已经失效
    // std::cout << "失效后尝试访问: " << *rit << std::endl; // 未定义行为
    
    // 重新获取迭代器
    rit = numbers.rbegin();
    std::cout << "重新获取迭代器后: " << *rit << std::endl; // 输出4
    
    return 0;
}

输出：

当前元素: 5
重新获取迭代器后: 4

2. 反向迭代器与索引的转换

当使用反向迭代器时，容器中元素的索引关系需要特别注意：

cpp

#include <iostream>
#include <vector>

int main() {
    std::vector<int> numbers = {10, 20, 30, 40, 50};
    
    // 打印容器及索引
    std::cout << "容器内容与索引:\n";
    for (size_t i = 0; i < numbers.size(); ++i) {
        std::cout << "索引 " << i << ": " << numbers[i] << std::endl;
    }
    std::cout << std::endl;
    
    // 使用反向迭代器和计算对应索引
    std::cout << "反向迭代器与对应索引:\n";
    int count = 0;
    for (auto rit = numbers.rbegin(); rit != numbers.rend(); ++rit, ++count) {
        size_t original_index = numbers.size() - 1 - count;
        std::cout << "反向位置 " << count << " (原始索引 " 
                  << original_index << "): " << *rit << std::endl;
    }
    
    return 0;
}

输出：

容器内容与索引:
索引 0: 10
索引 1: 20
索引 2: 30
索引 3: 40
索引 4: 50

反向迭代器与对应索引:
反向位置 0 (原始索引 4): 50
反向位置 1 (原始索引 3): 40
反向位置 2 (原始索引 2): 30
反向位置 3 (原始索引 1): 20
反向位置 4 (原始索引 0): 10

总结

反向迭代器是C++ STL中的一个强大工具，它让我们能够以相反的顺序遍历容器，而不需要手动实现复杂的逻辑。主要要点包括：

1. 反向迭代器允许从容器末尾向开头遍历元素
2. 大多数STL容器都支持反向迭代器，通过 rbegin() 和 rend() 获取
3. 反向迭代器可以与STL算法结合使用，实现逆序操作
4. 反向迭代器的 base() 方法可以获取对应的正向迭代器
5. 使用反向迭代器时需要注意迭代器失效和索引转换等问题

熟练掌握反向迭代器可以使代码更加简洁、高效，特别是在需要从后向前处理数据的场景中。

练习

为了加深对反向迭代器的理解，尝试完成以下练习：

1. 编写一个函数，使用反向迭代器检查一个字符串是否是回文，不考虑大小写和非字母字符
2. 实现一个函数，将一个向量中的元素按照从大到小的顺序排列，使用反向迭代器实现
3. 编写一个程序，查找一个向量中最后一个满足特定条件（如，最后一个偶数）的元素
4. 使用反向迭代器，将一个容器的内容复制到另一个容器中，使其顺序颠倒

扩展资源

• C++ Reference: Reverse Iterators
• C++ Reference: rbegin/rend
• C++ Standard Library: A Tutorial and Reference by Nicolai M. Josuttis

继续学习和实践将帮助你更好地理解和应用反向迭代器，提高你的C++编程技能。