C++的标准模板库(STL)中,迭代器是一种重要的工具,用于访问容器中的元素。
迭代器是一个变量,相当于容器和操纵容器的算法之间的中介。迭代器可以指向容器中的某个元素,通过迭代器就可以读写它指向的元素。从这一点上看,迭代器和指针类似。
分类
1) 正向迭代器,定义方法如下:
容器类名::iterator 迭代器名;
2) 常量正向迭代器,定义方法如下:
容器类名::const_iterator 迭代器名;
3) 反向迭代器,定义方法如下:
容器类名::reverse_iterator 迭代器名;
4) 常量反向迭代器,定义方法如下:
容器类名::const_reverse_iterator 迭代器名;
用法
通过迭代器指向它指向的元素, * 迭代器名就代表迭代器指向的元素。常量迭代器是只读权限,以const来修饰,非常量迭代器还能修改元素
++ 自增操作:
正向迭代器进行++操作,指向容器的后一个元素
反向迭代器进行++操作,则指向容器的前一个元素
我们通过迭代器来遍历容器中全部元素,一般来说有四种方式(本人习惯用):
以下使用vector为例:
- 基本的迭代器循环
- C++11之后,增强版for
- lambda表达式与for_each结合,需引用头文件 #include<algorithm>
- 不需要修改容器元素的话,可以使用常量迭代器
#include<iostream>//以vector为例#include<vector>// 需要使用for_eacj必须引入的算法库函数#include<algorithm>using namespace std;// 遍历void Test() {vector<int> v;v.push_back(20);v.push_back(10);v.push_back(5);// 1.基本的循环for (auto it = v.begin(); it != v.end(); ++it) {cout << *it << " ";}cout << endl;// 2.C++11之后,增强版forfor (const auto& elem : v) {cout << elem << " ";}cout << endl;// 3.lambda表达式for_each(v.begin(), v.end(), [](int elem) { cout << elem << " "; });cout << endl;// 4.不需要修改容器元素的话,可以使用常量迭代器for (auto it = v.cbegin(); it != v.cend(); ++it) {cout << *it << " ";}cout << endl;}void Test_reverse() {vector<int> vec;for (int i = 0; i < 5; i++) {vec.push_back(i);}// 反向迭代器for (vector<int>::reverse_iterator it = vec.rbegin(); it != vec.rend(); ++it) {cout << *it << " ";}cout << endl;//lambdafor_each(vec.rbegin(), vec.rend(), [](const auto& elem)-> void { cout << elem << " "; });}int main() {Test();Test_reverse();return 0;}
程序运行结果是:
我们可能会疑惑,在使用基本循环时,为什么用前自增
无论是正向迭代器,还是反向迭代器
我们来回一下 ++重载成前置和后置运算符是这样的:
OPerator OPerator::operator++() {// 前置++++n;return *this;}OPerator OPerator::operator++(int k) {// 后置++OPerator temp(*this);// 记录修改前的对象n++;return temp;}
后置++的底层实现,我们要先保存一个对象temp,多了步骤,肯定执行速度慢于前置++。相同的,迭代器实质上也是一个对象,STL中,在重载迭代器的++运算符时,后置也是慢于前置的,一次可能相差不多,但在次数多的迭代中,差异就会变得明显了。
不同迭代器的具体操作
不同容器的迭代器,其功能强弱有所不同。容器的迭代器的功能强弱,决定了该容器是否支持 STL 中的某种算法。例如,排序算法需要通过随机访问迭代器来访问容器中的元素,因此有的容器就不支持排序算法。
常用的迭代器按功能强弱分为输入、输出、正向、双向、随机访问五种,这里只介绍常用的三种。
1) 正向迭代器。假设 p 是一个正向迭代器,则 p 支持以下操作:++p,p++,*p。此外,两个正向迭代器可以互相赋值,还可以用==和!=运算符进行比较。
2) 双向迭代器。双向迭代器具有正向迭代器的全部功能。除此之外,若 p 是一个双向迭代器,则--p和p--都是有定义的。--p使得 p 朝和++p相反的方向移动。
3) 随机访问迭代器。随机访问迭代器具有双向迭代器的全部功能。若 p 是一个随机访问迭代器,i 是一个整型变量或常量,则 p 还支持以下操作:
p+=i:使得 p 往后移动 i 个元素。
p-=i:使得 p 往前移动 i 个元素。
p+i:返回 p 后面第 i 个元素的迭代器。
p-i:返回 p 前面第 i 个元素的迭代器。
p[i]:返回 p 后面第 i 个元素的引用。
此外,两个随机访问迭代器 p1、p2 还可以用 <、>、<=、>= 运算符进行比较。p1<p2的含义是:p1 经过若干次(至少一次)++操作后,就会等于 p2。其他比较方式的含义与此类似。
对于两个随机访问迭代器 p1、p2,表达式p2-p1也是有定义的,其返回值是 p2 所指向元素和 p1 所指向元素的序号之差(也可以说是 p2 和 p1 之间的元素个数减一)。
模拟实现迭代器
(手撕套餐【包括: 正向迭代器,反向迭代器,常量正向迭代器,常量反向迭代器】)
我们还需要再模拟一个适配器,以达到使用统一的迭代器对不同的容器都能进行操作
我们知道,迭代器中提供的功能有:
- 构造函数
- operator++函数重载
- operator++(int)函数重载
- operator--函数重载
- operator--(int)函数重载
- operator*函数重载
- operator->函数重载
- operator!=函数重载
- operator==函数重载
而正向,反向,常量迭代器,具体的实现内容也有差别,这个时候我们就可以将之分开封装,然后放入我们自己的namespace,也就做到了实现自己的迭代器。
封装好的模板类工程代码
Iterator_for_all_container.h;#pragma once#include <iostream>#include <vector>#include <list>using namespace std;// 正向迭代器template <class Iterator>class ForwardIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = typename iterator_traits<Iterator>::reference;using pointer = typename iterator_traits<Iterator>::pointer;explicit ForwardIterator(Iterator it) : current(it) {}reference operator*() {return *current;}// 前置++ForwardIterator& operator++() {++current;return *this;}// 后置++ForwardIterator operator++(int) {ForwardIterator tmp = *this;++(*this);return tmp;}bool operator!=(const ForwardIterator& other) const {return current != other.current;}};// 常量正向迭代器template <class Iterator>class ConstForwardIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = const typename iterator_traits<Iterator>::value_type&;using pointer = const typename iterator_traits<Iterator>::value_type*;explicit ConstForwardIterator(Iterator it) : current(it) {}reference operator*() const {return *current;}// 前置++ConstForwardIterator& operator++() {++current;return *this;}// 后置++ConstForwardIterator operator++(int) {ConstForwardIterator tmp = *this;++(*this);return tmp;}bool operator!=(const ConstForwardIterator& other) const {return current != other.current;}};// 反向迭代器template <class Iterator>class ReverseIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = typename iterator_traits<Iterator>::reference;// 从 std::reverse_iterator 构造explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it): current(rev_it.base()) {}// 解引用操作符,返回当前迭代器指向的元素auto operator*() const {Iterator tmp = current;--tmp; // 反向迭代return *tmp;}// 前置递增操作符ReverseIterator& operator++() {--current;return *this;}// 后置递增操作符ReverseIterator operator++(int) {ReverseIterator tmp = *this;--current;return tmp;}// 比较操作符bool operator!=(const ReverseIterator& other) const {return current != other.current;}// 基本迭代器(返回底层迭代器)Iterator base() const {return current;}};// 常量反向迭代器template <class Iterator>class ConstReverseIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = const typename iterator_traits<Iterator>::value_type&;explicit ConstReverseIterator(const std::reverse_iterator<Iterator>& rev_it): current(rev_it.base()) {}// 解引用操作符auto operator*() const {Iterator tmp = current;--tmp; // 反向迭代return *tmp;}// 前置递增ConstReverseIterator& operator++() {--current;return *this;}// 不等于操作符bool operator!=(const ConstReverseIterator& other) const {return current != other.current;}// 基本迭代器(返回底层迭代器)Iterator base() const {return current;}};// 适配容器template <class Container>class ContainerAdapter {private:Container& container;public:using iterator = typename Container::iterator;using const_iterator = typename Container::const_iterator;// 构造,初始化ContainerAdapter(Container& container) : container(container) {}// 正向迭代器ForwardIterator<iterator> begin() {return ForwardIterator<iterator>(container.begin());}ForwardIterator<iterator> end() {return ForwardIterator<iterator>(container.end());}// 正向常量迭代器ConstForwardIterator<const_iterator> cbegin() const {return ConstForwardIterator<const_iterator>(container.cbegin());}ConstForwardIterator<const_iterator> cend() const {return ConstForwardIterator<const_iterator>(container.cend());}// 反向ReverseIterator<typename Container::iterator> rbegin() {return ReverseIterator<typename Container::iterator>(container.rbegin());}ReverseIterator<typename Container::iterator> rend() {return ReverseIterator<typename Container::iterator>(container.rend());}// 常量反向迭代器ConstReverseIterator<typename Container::const_iterator> crbegin() const {return ConstReverseIterator<typename Container::const_iterator>(container.crbegin());}ConstReverseIterator<typename Container::const_iterator> crend() const {return ConstReverseIterator<typename Container::const_iterator>(container.crend());}};
接下来我们来详解一下其中一类迭代器,其他的三个都与之类似,
就以反向迭代器为例吧
这个类 ReverseIterator 实现了一个反向迭代器的自定义模板类,用于使容器支持反向遍历。其主要功能是提供与标准反向迭代器类似的行为,即从容器的尾部开始迭代,并且支持解引用、递增、比较等常见的迭代器操作。
1. 类模板声明与成员变量
template <class Iterator>class ReverseIterator {private:Iterator current;...
}
- 这是一个模板类,接受一个类型参数 Iterator,代表底层容器的迭代器类型。
- current 是一个成员变量,保存当前迭代器的位置,它将被用来访问容器中的元素。
2. 类型别名
using value_type = typename iterator_traits<Iterator>::value_type;using reference = typename iterator_traits<Iterator>::reference;
- value_type 和 reference 是类型别名,分别代表迭代器所指向的元素类型和值类型的引用。
- iterator_traits 是标准库中的一个结构体模板,用于提取给定迭代器类型的相关类型信息,如 value_type 和 reference。
- value_type 是容器中元素的类型。
- reference 是该元素的引用类型,提供通过迭代器对元素进行修改的能力。
3. 构造函数
explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it): current(rev_it.base()) {}
- 构造函数接收一个 std::reverse_iterator 类型的迭代器 rev_it,并将它转换为该类的 current 成员。
- std::reverse_iterator 是标准库提供的反向迭代器,它是通过反向迭代一个正向迭代器来实现的。调用 rev_it.base() 获取底层的正向迭代器,然后将它赋值给 current。
4. 解引用操作符 (operator*)
auto operator*() const {Iterator tmp = current;--tmp; // 反向迭代return *tmp;}
- 该操作符实现了解引用操作,即当迭代器通过 *it 被访问时,返回迭代器当前指向的元素。
- 由于这是反向迭代器,当你解引用时,实际上要访问 current 前一个位置的元素。所以,使用 --tmp 将迭代器向前移动一个位置,然后返回 *tmp,即当前元素的值。
- 这样实现确保反向迭代器能从尾部向头部正确地遍历容器。
5. 前置递增操作符 (operator++)
ReverseIterator& operator++() {--current;return *this;}
- 前置递增操作符 (++it) 是标准的递增操作。对于反向迭代器,递增操作实际上是使 current 向前(逆向)移动一个位置。
- --current; 使 current 向容器的前一个元素移动。注意,这里实现了递减,而不是递增,因为我们是在进行反向遍历。
- 返回 *this 是为了支持链式调用,即 ++it; 后可以继续使用迭代器。
6. 后置递增操作符 (operator++(int))
ReverseIterator operator++(int) {ReverseIterator tmp = *this;--current;return tmp;}
- 后置递增操作符 (it++) 会先返回当前的迭代器副本,再递增迭代器。
- ReverseIterator tmp = *this; 保存当前迭代器的副本。
- --current; 递减 current,使迭代器指向前一个元素。
- 返回 tmp,即递增前的迭代器副本。这与前置递增不同,前置递增直接返回递增后的迭代器,而后置递增返回递增前的迭代器。
7. 不等于操作符 (operator!=)
bool operator!=(const ReverseIterator& other) const {return current != other.current;}
- 这个操作符用于比较两个反向迭代器是否不相等。
- 比较的是它们内部的 current 成员(即底层迭代器),如果 current 不相等,表示两个迭代器指向不同的位置,返回 true,表示迭代器不相等。
8. base() 方法
Iterator base() const {return current;}
- base() 方法返回底层的正向迭代器 current,它指向容器的一个元素。
- 这个方法是为了兼容标准库中的 std::reverse_iterator,通过 base() 可以获取反向迭代器的底层正向迭代器。
- 例如,可以通过 rev_it.base() 获取反向迭代器 rev_it 对应的正向迭代器。
9. 总结
ReverseIterator 类提供了一个反向迭代器的实现,可以用于反向遍历容器。它的关键特性包括:
- 从正向迭代器转换而来:通过 std::reverse_iterator 构造反向迭代器。
- 解引用与递增操作:支持解引用操作符(operator*)和递增操作符(operator++),允许反向访问容器的元素。
- 支持标准迭代器的操作:与标准库的反向迭代器兼容,支持不等于操作符(operator!=)以及底层迭代器的访问(base())。
该迭代器可以与标准库容器(如 std::vector、std::list 等)配合使用,提供灵活的反向遍历能力
在实现了一个容器的多种迭代器之后,我们就需要再封装一个适配器,以来适应多种容器的不同,让我们的迭代器能够操作,访问不同的容器
我们可以显而易见的看到,ContainerAdapter 类提供了一种方式,将不同类型的迭代器(正向迭代器、常量正向迭代器、反向迭代器和常量反向迭代器)包装起来,并与实际容器相适配。通过这种方式,你可以通过 ContainerAdapter 对容器进行灵活的遍历,而无需直接依赖容器原生的迭代器接口。
主要功能
- 适配正向迭代器:提供 begin() 和 end() 方法,支持正向遍历容器。
- 适配常量正向迭代器:提供 cbegin() 和 cend() 方法,支持常量正向遍历容器。
- 适配反向迭代器:提供 rbegin() 和 rend() 方法,支持反向遍历容器。
- 适配常量反向迭代器:提供 crbegin() 和 crend() 方法,支持常量反向遍历容器。
我们对模拟的迭代器及其适配进行一个测试
Test.cpp
#include<iostream>//以vector和list为例#include<vector>// 需要使用for_eacj必须引入的算法库函数#include<algorithm>#include"Iterator_for_all_container.h"using namespace std;// 使用适配器类进行容器的遍历template <class Container>void testContainerAdapter(Container& container) {// 创建适配器实例ContainerAdapter<Container> adapter(container);// 正向迭代器测试std::cout << "正向迭代器: ";for (auto it = adapter.begin(); it != adapter.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 正向常量迭代器测试std::cout << "正向常量迭代器: ";for (auto it = adapter.cbegin(); it != adapter.cend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 反向迭代器测试std::cout << "反向迭代器: ";for (auto it = adapter.rbegin(); it != adapter.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 常量反向迭代器测试std::cout << "常量反向迭代器: ";for (auto it = adapter.crbegin(); it != adapter.crend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// lambdafor_each(adapter.crbegin(), adapter.crend(), [](const auto& elem) ->void { std::cout << elem << " "; });}void Test_iterator() {// 测试 vectorstd::vector<int> vec = { 1, 2, 3, 4, 5 };std::cout << "测试 vector 容器:" << std::endl;testContainerAdapter(vec);// 测试 liststd::list<int> lst = { 10, 20, 30, 40, 50 };std::cout << "\n测试 list 容器:" << std::endl;testContainerAdapter(lst);}int main() {Test_iterator();return 0;}
我们来看看打印出来的结果:
很好,符合预期,特别注明,我们的反向就是在正向的基础上,做相反的操作,这样可以有效减少代码的复用
至于最后一排为什么会有多的一排,那是因为本人又使用for_each算法,结合lambda表达式,遍历了一次反向常量迭代器。
附录(完整的代码声明及定义,以及测试函数)
#pragma once#include <iostream>#include <vector>#include <list>using namespace std;// 正向迭代器template <class Iterator>class ForwardIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = typename iterator_traits<Iterator>::reference;using pointer = typename iterator_traits<Iterator>::pointer;explicit ForwardIterator(Iterator it) : current(it) {}reference operator*() {return *current;}// 前置++ForwardIterator& operator++() {++current;return *this;}// 后置++ForwardIterator operator++(int) {ForwardIterator tmp = *this;++(*this);return tmp;}bool operator!=(const ForwardIterator& other) const {return current != other.current;}};// 常量正向迭代器template <class Iterator>class ConstForwardIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = const typename iterator_traits<Iterator>::value_type&;using pointer = const typename iterator_traits<Iterator>::value_type*;explicit ConstForwardIterator(Iterator it) : current(it) {}reference operator*() const {return *current;}// 前置++ConstForwardIterator& operator++() {++current;return *this;}// 后置++ConstForwardIterator operator++(int) {ConstForwardIterator tmp = *this;++(*this);return tmp;}bool operator!=(const ConstForwardIterator& other) const {return current != other.current;}};// 反向迭代器template <class Iterator>class ReverseIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = typename iterator_traits<Iterator>::reference;// 从 std::reverse_iterator 构造explicit ReverseIterator(const std::reverse_iterator<Iterator>& rev_it): current(rev_it.base()) {}// 解引用操作符,返回当前迭代器指向的元素auto operator*() const {Iterator tmp = current;--tmp; // 反向迭代return *tmp;}// 前置递增操作符ReverseIterator& operator++() {--current;return *this;}// 后置递增操作符ReverseIterator operator++(int) {ReverseIterator tmp = *this;--current;return tmp;}// 比较操作符bool operator!=(const ReverseIterator& other) const {return current != other.current;}// 基本迭代器(返回底层迭代器)Iterator base() const {return current;}};// 常量反向迭代器template <class Iterator>class ConstReverseIterator {private:Iterator current;public:using value_type = typename iterator_traits<Iterator>::value_type;using reference = const typename iterator_traits<Iterator>::value_type&;explicit ConstReverseIterator(const std::reverse_iterator<Iterator>& rev_it): current(rev_it.base()) {}// 解引用操作符auto operator*() const {Iterator tmp = current;--tmp; // 反向迭代return *tmp;}// 前置递增ConstReverseIterator& operator++() {--current;return *this;}// 不等于操作符bool operator!=(const ConstReverseIterator& other) const {return current != other.current;}// 基本迭代器(返回底层迭代器)Iterator base() const {return current;}};// 适配容器template <class Container>class ContainerAdapter {private:Container& container;public:using iterator = typename Container::iterator;using const_iterator = typename Container::const_iterator;// 构造,初始化ContainerAdapter(Container& container) : container(container) {}// 正向迭代器ForwardIterator<iterator> begin() {return ForwardIterator<iterator>(container.begin());}ForwardIterator<iterator> end() {return ForwardIterator<iterator>(container.end());}// 正向常量迭代器ConstForwardIterator<const_iterator> cbegin() const {return ConstForwardIterator<const_iterator>(container.cbegin());}ConstForwardIterator<const_iterator> cend() const {return ConstForwardIterator<const_iterator>(container.cend());}// 反向迭代器ReverseIterator<typename Container::iterator> rbegin() {return ReverseIterator<typename Container::iterator>(container.rbegin());}ReverseIterator<typename Container::iterator> rend() {return ReverseIterator<typename Container::iterator>(container.rend());}// 常量反向迭代器ConstReverseIterator<typename Container::const_iterator> crbegin() const {return ConstReverseIterator<typename Container::const_iterator>(container.crbegin());}ConstReverseIterator<typename Container::const_iterator> crend() const {return ConstReverseIterator<typename Container::const_iterator>(container.crend());}};#include<iostream>//以vector和list为例#include<vector>// 需要使用for_eacj必须引入的算法库函数#include<algorithm>#include"Iterator_for_all_container.h"// 使用适配器类进行容器的遍历template <class Container>void testContainerAdapter(Container& container) {// 创建适配器实例ContainerAdapter<Container> adapter(container);// 正向迭代器测试std::cout << "正向迭代器: ";for (auto it = adapter.begin(); it != adapter.end(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 正向常量迭代器测试std::cout << "正向常量迭代器: ";for (auto it = adapter.cbegin(); it != adapter.cend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 反向迭代器测试std::cout << "反向迭代器: ";for (auto it = adapter.rbegin(); it != adapter.rend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// 常量反向迭代器测试std::cout << "常量反向迭代器: ";for (auto it = adapter.crbegin(); it != adapter.crend(); ++it) {std::cout << *it << " ";}std::cout << std::endl;// lambdafor_each(adapter.crbegin(), adapter.crend(), [](const auto& elem) ->void { std::cout << elem << " "; });}void Test_iterator() {// 测试 vectorstd::vector<int> vec = { 1, 2, 3, 4, 5 };std::cout << "测试 vector 容器:" << std::endl;testContainerAdapter(vec);// 测试 liststd::list<int> lst = { 10, 20, 30, 40, 50 };std::cout << "\n测试 list 容器:" << std::endl;testContainerAdapter(lst);}int main() {Test_iterator();return 0;}