跳到主要内容

C++ 自定义迭代器

什么是迭代器？​

迭代器是C++中一种重要的工具，它提供了一种访问容器中元素的统一方式，使我们能够遍历容器内的元素而无需了解容器的底层实现细节。在STL(标准模板库)中，虽然已经提供了丰富的迭代器实现，但有时我们需要为自定义的数据结构实现迭代器，以便能够像使用标准容器一样方便地操作我们的数据。

为什么需要自定义迭代器？​

自定义迭代器的主要目的包括：

  1. 为自定义容器提供标准的访问接口
  2. 允许自定义容器使用STL算法
  3. 实现特定的遍历方式或访问策略
  4. 提供额外的功能，如过滤、转换等

迭代器的类型​

在开始创建自定义迭代器之前，让我们了解迭代器的几种主要类型：

  1. 输入迭代器：只能向前读取元素一次
  2. 输出迭代器：只能向前写入元素一次
  3. 前向迭代器：可以多次读取元素
  4. 双向迭代器：可以前后移动
  5. 随机访问迭代器：可以随机访问任何元素
备注

不同类型的迭代器需要实现不同的操作符。随着从输入迭代器到随机访问迭代器的顺序，所需实现的操作符越来越多。

创建自定义迭代器的基本步骤​

创建一个自定义迭代器通常需要以下几个步骤：

  1. 定义迭代器类并包含必要的类型定义
  2. 实现构造函数和析构函数
  3. 实现解引用操作符(*)和箭头操作符(->)
  4. 实现递增操作符(++)
  5. 实现比较操作符(==和!=)
  6. 如果是双向迭代器，还需实现递减操作符(--)
  7. 如果是随机访问迭代器，还需实现加减和关系比较操作符

实现一个简单的前向迭代器​

让我们通过一个简单的例子来说明如何实现一个前向迭代器。假设我们有一个自定义的链表类MyLinkedList，我们将为它实现一个迭代器。

cpp
#include <iostream>
#include <iterator>
#include <cstddef>

// 定义链表节点
template <typename T>
struct Node {
    T data;
    Node* next;
    
    Node(const T& value) : data(value), next(nullptr) {}
};

// 自定义链表类
template <typename T>
class MyLinkedList {
private:
    Node<T>* head;
    Node<T>* tail;
    size_t size;

public:
    // 前向声明迭代器类
    class Iterator;
    
    MyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    ~MyLinkedList() {
        Node<T>* current = head;
        while (current) {
            Node<T>* next = current->next;
            delete current;
            current = next;
        }
    }
    
    // 在链表尾部添加元素
    void push_back(const T& value) {
        Node<T>* newNode = new Node<T>(value);
        if (!head) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
        size++;
    }
    
    // 返回开始迭代器
    Iterator begin() {
        return Iterator(head);
    }
    
    // 返回结束迭代器
    Iterator end() {
        return Iterator(nullptr);
    }
    
    // 迭代器类定义
    class Iterator {
    private:
        Node<T>* current;
        
    public:
        // 迭代器必要的类型定义
        using iterator_category = std::forward_iterator_tag;
        using value_type = T;
        using difference_type = std::ptrdiff_t;
        using pointer = T*;
        using reference = T&;
        
        // 构造函数
        Iterator(Node<T>* ptr) : current(ptr) {}
        
        // 解引用操作符
        reference operator*() const {
            return current->data;
        }
        
        // 箭头操作符
        pointer operator->() const {
            return &(current->data);
        }
        
        // 前缀递增操作符
        Iterator& operator++() {
            current = current->next;
            return *this;
        }
        
        // 后缀递增操作符
        Iterator operator++(int) {
            Iterator temp = *this;
            current = current->next;
            return temp;
        }
        
        // 相等比较操作符
        bool operator==(const Iterator& other) const {
            return current == other.current;
        }
        
        // 不等比较操作符
        bool operator!=(const Iterator& other) const {
            return current != other.current;
        }
    };
};

使用我们的自定义迭代器​

现在让我们看一个使用这个自定义迭代器的例子：

cpp
int main() {
    MyLinkedList<int> myList;
    
    // 添加一些元素
    myList.push_back(10);
    myList.push_back(20);
    myList.push_back(30);
    myList.push_back(40);
    
    // 使用迭代器遍历链表
    std::cout << "链表中的元素：";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 使用范围for循环（C++11及以上）
    std::cout << "使用范围for循环：";
    for (const auto& value : myList) {
        std::cout << value << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

链表中的元素：10 20 30 40 
使用范围for循环：10 20 30 40

更进一步：实现双向迭代器​

如果我们想实现一个双向迭代器，需要添加向后移动的能力。以下是如何扩展我们的迭代器类来支持双向操作：

cpp
// 假设我们有一个双向链表节点
template <typename T>
struct BiNode {
    T data;
    BiNode* next;
    BiNode* prev;
    
    BiNode(const T& value) : data(value), next(nullptr), prev(nullptr) {}
};

// 双向链表的迭代器
template <typename T>
class BidirectionalIterator {
private:
    BiNode<T>* current;
    
public:
    // 迭代器必要的类型定义
    using iterator_category = std::bidirectional_iterator_tag;
    using value_type = T;
    using difference_type = std::ptrdiff_t;
    using pointer = T*;
    using reference = T&;
    
    // 构造函数
    BidirectionalIterator(BiNode<T>* ptr) : current(ptr) {}
    
    // 解引用和箭头操作符
    reference operator*() const { return current->data; }
    pointer operator->() const { return &(current->data); }
    
    // 前缀递增和递减
    BidirectionalIterator& operator++() {
        current = current->next;
        return *this;
    }
    
    BidirectionalIterator& operator--() {
        current = current->prev;
        return *this;
    }
    
    // 后缀递增和递减
    BidirectionalIterator operator++(int) {
        BidirectionalIterator temp = *this;
        current = current->next;
        return temp;
    }
    
    BidirectionalIterator operator--(int) {
        BidirectionalIterator temp = *this;
        current = current->prev;
        return temp;
    }
    
    // 比较操作符
    bool operator==(const BidirectionalIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const BidirectionalIterator& other) const {
        return current != other.current;
    }
};

实际应用案例：过滤迭代器​

有时我们需要在遍历容器时应用某种过滤条件。下面是一个过滤迭代器的例子，它只会返回满足特定条件的元素：

cpp
#include <iostream>
#include <vector>
#include <functional>

template <typename Container, typename Predicate>
class FilterIterator {
private:
    typename Container::const_iterator current;
    typename Container::const_iterator end;
    Predicate predicate;
    
    // 找到下一个满足条件的元素
    void find_next_valid() {
        while (current != end && !predicate(*current)) {
            ++current;
        }
    }
    
public:
    using iterator_category = std::forward_iterator_tag;
    using value_type = typename Container::value_type;
    using difference_type = std::ptrdiff_t;
    using pointer = const value_type*;
    using reference = const value_type&;
    
    FilterIterator(typename Container::const_iterator start,
                   typename Container::const_iterator end,
                   Predicate pred)
        : current(start), end(end), predicate(pred) {
        find_next_valid();
    }
    
    reference operator*() const {
        return *current;
    }
    
    pointer operator->() const {
        return &(*current);
    }
    
    FilterIterator& operator++() {
        ++current;
        find_next_valid();
        return *this;
    }
    
    FilterIterator operator++(int) {
        FilterIterator temp = *this;
        ++(*this);
        return temp;
    }
    
    bool operator==(const FilterIterator& other) const {
        return current == other.current;
    }
    
    bool operator!=(const FilterIterator& other) const {
        return current != other.current;
    }
};

// 辅助函数，用于创建过滤迭代器
template <typename Container, typename Predicate>
class FilterView {
private:
    const Container& container;
    Predicate predicate;
    
public:
    FilterView(const Container& cont, Predicate pred)
        : container(cont), predicate(pred) {}
    
    FilterIterator<Container, Predicate> begin() const {
        return FilterIterator<Container, Predicate>(
            container.begin(), container.end(), predicate);
    }
    
    FilterIterator<Container, Predicate> end() const {
        return FilterIterator<Container, Predicate>(
            container.end(), container.end(), predicate);
    }
};

template <typename Container, typename Predicate>
FilterView<Container, Predicate> filter(const Container& container, Predicate pred) {
    return FilterView<Container, Predicate>(container, pred);
}

使用这个过滤迭代器的例子：

cpp
int main() {
    std::vector<int> numbers = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    
    // 使用过滤迭代器只遍历偶数
    auto isEven = [](int n) { return n % 2 == 0; };
    
    std::cout << "偶数：";
    for (const auto& num : filter(numbers, isEven)) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    // 使用过滤迭代器只遍历大于5的数
    auto greaterThan5 = [](int n) { return n > 5; };
    
    std::cout << "大于5的数：";
    for (const auto& num : filter(numbers, greaterThan5)) {
        std::cout << num << " ";
    }
    std::cout << std::endl;
    
    return 0;
}

输出结果：

偶数：2 4 6 8 10 
大于5的数：6 7 8 9 10

迭代器的特性标记​

为了让STL算法能够正确使用我们的自定义迭代器，我们需要定义几个特性标记类型。这些类型可以告诉STL算法我们的迭代器支持什么操作：

cpp
// 迭代器必要的类型定义
using iterator_category = std::forward_iterator_tag;  // 或其他适当的标记
using value_type = T;
using difference_type = std::ptrdiff_t;
using pointer = T*;
using reference = T&;

不同的迭代器类别对应不同的标记：

  • std::input_iterator_tag - 输入迭代器
  • std::output_iterator_tag - 输出迭代器
  • std::forward_iterator_tag - 前向迭代器
  • std::bidirectional_iterator_tag - 双向迭代器
  • std::random_access_iterator_tag - 随机访问迭代器

C++ 20：概念和约束​

C++20引入了概念(Concepts)，这使得定义迭代器要求更加简单和明确。以下是使用C++20概念的迭代器示例：

cpp
#include <concepts>
#include <iterator>

template <typename T>
class MyIterator {
private:
    // 迭代器实现...
    
public:
    // 使用C++20的概念定义
    using iterator_concept = std::forward_iterator_tag;
    // 其他类型定义...
    
    // 迭代器实现...
};
提示

C++20的概念使得编译器能够提供更好的错误消息，帮助你确保你的迭代器满足所需的要求。

总结​

自定义迭代器是C++编程中一项强大的技术，它可以让我们为自定义的数据结构提供与STL容器相同的访问接口，从而实现更加通用和可复用的代码。通过实现适当的操作符，我们可以创建不同类型的迭代器，以满足不同的需求。

本文中我们学习了：

  1. 迭代器的基本概念和类型
  2. 如何实现一个简单的前向迭代器
  3. 如何实现双向迭代器
  4. 如何创建具有特殊功能的迭代器（如过滤迭代器）
  5. C++20中的迭代器概念

练习​

  1. 实现一个随机访问迭代器，用于自定义的动态数组类。
  2. 创建一个转换迭代器，可以在遍历容器时对元素进行某种转换（如将整数转换为字符串）。
  3. 实现一个逆向迭代器适配器，可以反向遍历任何提供双向迭代器的容器。
  4. 为树形结构（如二叉树）实现一个中序遍历迭代器。
  5. 使用C++20的概念重构本文中的某个迭代器示例。

进一步阅读​

通过掌握自定义迭代器的创建，你将能够更好地利用STL算法，同时为自己的数据结构提供标准化的访问接口，大大提升代码的可读性和复用性。