C++实现自定义迭代器
一、迭代器的基本概念
在C++ 编程中，迭代器（Iterator）是一种抽象的概念，它提供了一种访问容器中元素的通用方式，而无需了解容器的具体实现细节。迭代器类似于指针，它可以指向容器中的某个元素，并通过一些操作符（如 ++、-- 等）来遍历容器。
（一）迭代器的作用
迭代器的主要作用是为各种容器提供统一的访问接口。例如，我们有 std::vector、std::list 和 std::map 等不同类型的容器，它们的数据存储结构和访问方式各不相同。但通过迭代器，我们可以以一种相似的方式来遍历和操作这些容器中的元素。
#include <iostream>
#include <vector>
#include <list>
int main() {
std::vector<int> vec = {1, 2, 3, 4, 5};
std::list<int> lst = {1, 2, 3, 4, 5};
// 使用迭代器遍历 vector
std::vector<int>::iterator vecIt;
for (vecIt = vec.begin(); vecIt != vec.end(); ++vecIt) {
std::cout << *vecIt << " ";
}
std::cout << std::endl;
// 使用迭代器遍历 list
std::list<int>::iterator lstIt;
for (lstIt = lst.begin(); lstIt != lst.end(); ++lstIt) {
std::cout << *lstIt << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，我们使用迭代器以相似的方式遍历了 std::vector 和 std::list，尽管这两种容器在内部实现上有很大差异。
（二）迭代器的类型
C++ 标准库定义了几种不同类型的迭代器，每种迭代器具有不同的功能和特性：
-
输入迭代器（Input Iterator）：
- 提供对数据的只读访问。
- 支持
++操作符向前移动迭代器。 - 可以进行相等（
==）和不相等（!=）比较。 - 典型应用场景是从输入流中读取数据。例如，
istream_iterator就是一种输入迭代器。
-
输出迭代器（Output Iterator）：
- 提供对数据的只写访问。
- 支持
++操作符向前移动迭代器。 - 通常用于向输出流中写入数据，如
ostream_iterator。
-
前向迭代器（Forward Iterator）：
- 结合了输入迭代器和输出迭代器的功能，既可以读又可以写。
- 支持多次遍历。
- 除了
++操作符，还可以多次解引用（*）。
-
双向迭代器（Bidirectional Iterator）：
- 在前向迭代器的基础上，支持
--操作符向后移动迭代器。 - 例如，
std::list的迭代器就是双向迭代器，这使得我们可以在list中双向遍历。
- 在前向迭代器的基础上，支持
-
随机访问迭代器（Random Access Iterator）：
- 具有双向迭代器的所有功能，并且支持随机访问。
- 可以使用
+、-、+=、-=等操作符进行跳跃式移动，还支持<、>、<=、>=等比较操作符。 std::vector的迭代器就是随机访问迭代器，这使得我们可以像访问数组一样快速地访问vector中的元素。
二、自定义迭代器的需求场景
虽然 C++ 标准库提供了丰富的迭代器，但在某些特定情况下，我们可能需要自定义迭代器：
-
自定义容器：当我们实现一个新的容器类时，为了提供与标准容器一致的访问接口，就需要为这个容器自定义迭代器。例如，我们实现一个自定义的链表容器，为了能够方便地遍历链表中的元素，就需要定义相应的迭代器。
-
特定的遍历逻辑：标准库迭代器的遍历方式可能无法满足我们的需求。比如，我们可能需要按照特定的顺序（非顺序存储容器中的顺序）遍历容器元素，或者在遍历过程中进行一些特殊的计算或过滤。
三、自定义迭代器的实现步骤
（一）确定迭代器类型
在实现自定义迭代器之前，我们需要根据实际需求确定迭代器的类型。如果我们的容器只需要支持只读遍历，那么输入迭代器可能就足够了；如果需要读写操作且只支持单向遍历，前向迭代器更为合适；如果容器需要双向遍历，双向迭代器是必须的；而对于支持随机访问的容器，随机访问迭代器是最佳选择。
（二）定义迭代器类
-
成员变量：迭代器类通常需要包含一个指向容器中元素的指针或引用作为成员变量。例如，如果我们为一个简单的数组容器定义迭代器，迭代器类中可能会包含一个指向数组元素的指针。
-
构造函数：迭代器类应该有合适的构造函数，用于初始化成员变量。构造函数可以接受容器元素的指针或引用，或者根据不同的情况进行其他初始化操作。
-
重载操作符：根据迭代器类型，我们需要重载相应的操作符。
- 解引用操作符（
*）：返回迭代器当前指向的元素。 - 自增操作符（
++）：将迭代器移动到下一个元素。对于双向迭代器，还需要重载--操作符，将迭代器移动到上一个元素。 - 比较操作符（
==和!=）：用于判断两个迭代器是否指向相同的位置。对于随机访问迭代器，还需要重载<、>等比较操作符。
- 解引用操作符（
（三）在容器类中定义迭代器类型
在自定义容器类中，我们需要定义迭代器类型。通常会使用 typedef 或 C++ 11 引入的 using 关键字来定义。这样，外部代码可以通过容器类来访问迭代器类型。
（四）提供容器的 begin() 和 end() 方法
容器类需要提供 begin() 和 end() 方法，分别返回指向容器起始位置和结束位置的迭代器。begin() 返回的迭代器指向容器的第一个元素，而 end() 返回的迭代器指向容器最后一个元素的下一个位置（常被称为超尾位置）。
四、自定义迭代器的代码示例
（一）自定义单向链表及迭代器
下面我们实现一个简单的单向链表容器，并为其定义一个前向迭代器。
#include <iostream>
// 单向链表节点结构体
template <typename T>
struct ListNode {
T data;
ListNode* next;
ListNode(const T& value) : data(value), next(nullptr) {}
};
// 单向链表容器类
template <typename T>
class MyList {
private:
ListNode<T>* head;
public:
MyList() : head(nullptr) {}
~MyList() {
while (head != nullptr) {
ListNode<T>* temp = head;
head = head->next;
delete temp;
}
}
void push_back(const T& value) {
ListNode<T>* newNode = new ListNode<T>(value);
if (head == nullptr) {
head = newNode;
} else {
ListNode<T>* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
// 前向迭代器类
class Iterator {
private:
ListNode<T>* current;
public:
Iterator(ListNode<T>* node) : current(node) {}
// 解引用操作符
T& operator*() {
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;
}
};
// 返回指向链表起始位置的迭代器
Iterator begin() {
return Iterator(head);
}
// 返回指向链表结束位置（超尾位置）的迭代器
Iterator end() {
return Iterator(nullptr);
}
};
int main() {
MyList<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
// 使用自定义迭代器遍历链表
MyList<int>::Iterator it;
for (it = myList.begin(); it != myList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
在上述代码中，我们首先定义了单向链表的节点结构体 ListNode。然后，MyList 类表示单向链表容器，它包含链表头指针 head 以及一些基本操作方法，如 push_back 用于向链表尾部添加元素。
接着，在 MyList 类内部定义了 Iterator 类，它是单向链表的前向迭代器。Iterator 类包含一个指向当前节点的指针 current，并重载了 *、++、== 和 != 等操作符。
最后，MyList 类提供了 begin() 和 end() 方法，返回指向链表起始位置和结束位置的迭代器。在 main() 函数中，我们创建了一个 MyList 对象，并使用自定义迭代器遍历链表，输出链表中的元素。
（二）自定义双向链表及迭代器
下面我们实现一个双向链表容器，并为其定义双向迭代器。
#include <iostream>
// 双向链表节点结构体
template <typename T>
struct DoublyListNode {
T data;
DoublyListNode* prev;
DoublyListNode* next;
DoublyListNode(const T& value) : data(value), prev(nullptr), next(nullptr) {}
};
// 双向链表容器类
template <typename T>
class MyDoublyList {
private:
DoublyListNode<T>* head;
DoublyListNode<T>* tail;
public:
MyDoublyList() : head(nullptr), tail(nullptr) {}
~MyDoublyList() {
while (head != nullptr) {
DoublyListNode<T>* temp = head;
head = head->next;
delete temp;
}
}
void push_back(const T& value) {
DoublyListNode<T>* newNode = new DoublyListNode<T>(value);
if (head == nullptr) {
head = newNode;
tail = newNode;
} else {
newNode->prev = tail;
tail->next = newNode;
tail = newNode;
}
}
// 双向迭代器类
class Iterator {
private:
DoublyListNode<T>* current;
public:
Iterator(DoublyListNode<T>* node) : current(node) {}
// 解引用操作符
T& operator*() {
return current->data;
}
// 前置自增操作符
Iterator& operator++() {
current = current->next;
return *this;
}
// 后置自增操作符
Iterator operator++(int) {
Iterator temp = *this;
current = current->next;
return temp;
}
// 前置自减操作符
Iterator& operator--() {
current = current->prev;
return *this;
}
// 后置自减操作符
Iterator operator--(int) {
Iterator temp = *this;
current = current->prev;
return temp;
}
// 比较操作符
bool operator==(const Iterator& other) const {
return current == other.current;
}
bool operator!=(const Iterator& other) const {
return current != other.current;
}
};
// 返回指向链表起始位置的迭代器
Iterator begin() {
return Iterator(head);
}
// 返回指向链表结束位置（超尾位置）的迭代器
Iterator end() {
return Iterator(nullptr);
}
};
int main() {
MyDoublyList<int> myDoublyList;
myDoublyList.push_back(1);
myDoublyList.push_back(2);
myDoublyList.push_back(3);
// 使用自定义双向迭代器正向遍历链表
MyDoublyList<int>::Iterator it;
for (it = myDoublyList.begin(); it != myDoublyList.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用自定义双向迭代器反向遍历链表
for (it = myDoublyList.end(); it != myDoublyList.begin(); ) {
--it;
std::cout << *it << " ";
}
std::cout << std::endl;
return 0;
}
在这个代码示例中，我们定义了双向链表的节点结构体 DoublyListNode，它包含前驱指针 prev 和后继指针 next。MyDoublyList 类表示双向链表容器，有 head 和 tail 指针分别指向链表的头和尾。
Iterator 类作为双向迭代器，除了重载前向迭代器的操作符 *、++、== 和 != 外，还重载了 -- 操作符，以支持反向遍历。
在 main() 函数中，我们创建了 MyDoublyList 对象，并分别使用自定义双向迭代器进行正向和反向遍历，展示了双向迭代器的功能。
（三）自定义随机访问迭代器
假设我们有一个简单的数组类，为其定义随机访问迭代器。
#include <iostream>
// 简单数组类
template <typename T, size_t N>
class MyArray {
private:
T data[N];
public:
// 随机访问迭代器类
class Iterator {
private:
T* ptr;
public:
Iterator(T* p) : ptr(p) {}
// 解引用操作符
T& operator*() {
return *ptr;
}
// 前置自增操作符
Iterator& operator++() {
++ptr;
return *this;
}
// 后置自增操作符
Iterator operator++(int) {
Iterator temp = *this;
++ptr;
return temp;
}
// 前置自减操作符
Iterator& operator--() {
--ptr;
return *this;
}
// 后置自减操作符
Iterator operator--(int) {
Iterator temp = *this;
--ptr;
return temp;
}
// 加法操作符
Iterator operator+(size_t offset) {
return Iterator(ptr + offset);
}
// 减法操作符
Iterator operator-(size_t offset) {
return Iterator(ptr - offset);
}
// 复合加法操作符
Iterator& operator+=(size_t offset) {
ptr += offset;
return *this;
}
// 复合减法操作符
Iterator& operator-=(size_t offset) {
ptr -= offset;
return *this;
}
// 小于比较操作符
bool operator<(const Iterator& other) const {
return ptr < other.ptr;
}
// 大于比较操作符
bool operator>(const Iterator& other) const {
return ptr > other.ptr;
}
// 小于等于比较操作符
bool operator<=(const Iterator& other) const {
return ptr <= other.ptr;
}
// 大于等于比较操作符
bool operator>=(const Iterator& other) const {
return ptr >= other.ptr;
}
// 指针偏移操作符
T& operator[](size_t index) {
return *(ptr + index);
}
};
Iterator begin() {
return Iterator(data);
}
Iterator end() {
return Iterator(data + N);
}
};
int main() {
MyArray<int, 5> myArray = {1, 2, 3, 4, 5};
// 使用自定义随机访问迭代器遍历数组
MyArray<int, 5>::Iterator it;
for (it = myArray.begin(); it < myArray.end(); ++it) {
std::cout << *it << " ";
}
std::cout << std::endl;
// 使用随机访问特性
MyArray<int, 5>::Iterator it2 = myArray.begin() + 2;
std::cout << *it2 << std::endl;
return 0;
}
在这个代码示例中，MyArray 类表示一个固定大小的数组。Iterator 类作为随机访问迭代器，重载了丰富的操作符，包括 +、-、+=、-=、<、>、<=、>= 和 [] 等，以支持随机访问。
在 main() 函数中，我们创建了 MyArray 对象，并使用自定义随机访问迭代器进行遍历，同时展示了随机访问的特性，如通过 + 操作符直接跳转到指定位置。
五、自定义迭代器与 STL 算法的结合使用
C++ 标准模板库（STL）提供了大量强大的算法，如排序、查找等。这些算法通常使用迭代器来操作容器中的元素。当我们自定义了迭代器后，也可以将其与 STL 算法结合使用，从而充分利用 STL 的功能。
例如，对于前面定义的 MyList 单向链表容器及其迭代器，我们可以使用 std::for_each 算法来遍历链表并对每个元素进行操作。
#include <iostream>
#include <algorithm>
// 单向链表节点结构体
template <typename T>
struct ListNode {
T data;
ListNode* next;
ListNode(const T& value) : data(value), next(nullptr) {}
};
// 单向链表容器类
template <typename T>
class MyList {
private:
ListNode<T>* head;
public:
MyList() : head(nullptr) {}
~MyList() {
while (head != nullptr) {
ListNode<T>* temp = head;
head = head->next;
delete temp;
}
}
void push_back(const T& value) {
ListNode<T>* newNode = new ListNode<T>(value);
if (head == nullptr) {
head = newNode;
} else {
ListNode<T>* current = head;
while (current->next != nullptr) {
current = current->next;
}
current->next = newNode;
}
}
// 前向迭代器类
class Iterator {
private:
ListNode<T>* current;
public:
Iterator(ListNode<T>* node) : current(node) {}
// 解引用操作符
T& operator*() {
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;
}
};
// 返回指向链表起始位置的迭代器
Iterator begin() {
return Iterator(head);
}
// 返回指向链表结束位置（超尾位置）的迭代器
Iterator end() {
return Iterator(nullptr);
}
};
// 定义一个函数对象，用于打印元素
struct PrintElement {
void operator()(const int& num) {
std::cout << num << " ";
}
};
int main() {
MyList<int> myList;
myList.push_back(1);
myList.push_back(2);
myList.push_back(3);
// 使用 std::for_each 算法遍历链表
std::for_each(myList.begin(), myList.end(), PrintElement());
std::cout << std::endl;
return 0;
}
在上述代码中，我们定义了一个函数对象 PrintElement，它重载了 () 操作符，用于打印传入的整数。然后，我们使用 std::for_each 算法，传入 MyList 的 begin() 和 end() 迭代器以及 PrintElement 对象，实现了对链表的遍历和元素打印。
通过这种方式，我们可以将自定义迭代器与 STL 算法无缝结合，提高代码的复用性和功能性。
六、自定义迭代器的注意事项
-
正确性和一致性：在重载操作符时，要确保操作符的行为符合预期，并且与迭代器类型的定义一致。例如，随机访问迭代器的比较操作符应该能够正确地比较两个迭代器的位置关系。
-
边界检查：在实现迭代器的移动操作符（如
++、--、+、-等）时，要注意进行边界检查，避免迭代器越界。例如，在单向链表的迭代器中，++操作符移动到nullptr时，应该确保不会再继续进行无效操作。 -
内存管理：如果迭代器中包含指针，要注意内存管理。特别是在容器销毁时，迭代器指向的内存可能已经被释放，此时迭代器就成为了悬空指针。可以通过合理的设计，如使用智能指针来避免这类问题。
-
可移植性：在编写自定义迭代器时，要考虑代码的可移植性。避免使用依赖于特定编译器或平台的特性，尽量遵循 C++ 标准规范。
总之，自定义迭代器在 C++ 编程中是一项强大的技术，它允许我们为自定义容器提供统一的访问接口，并与 STL 算法相结合。通过深入理解迭代器的概念、类型以及实现步骤，我们能够编写出高效、灵活且易于维护的代码。