鄂尔多斯网站制作公司,手机版网站原理,工业和信息化部icp网站备案系统,seo综合查询 站长工具目录
一#xff0c;什么是迭代器
1#xff0c;定义
2#xff0c;迭代器的设计思维
3#xff0c;迭代器种类
二#xff0c;迭代器与容器
1#xff0c;容器中的迭代器
2#xff0c;迭代器失效问题
三#xff0c;迭代器的类型萃取#xff08;traits#xff09; …目录
一什么是迭代器
1定义
2迭代器的设计思维
3迭代器种类
二迭代器与容器
1容器中的迭代器
2迭代器失效问题
三迭代器的类型萃取traits
四反向迭代器
1什么是适配器adapters
2什么是反向迭代器
3反向迭代器的实现 一什么是迭代器
1定义
迭代器iterators是一种抽象的设计概念是一种设计模式它的定义如下提供一种方法使之能够按照顺序依次访问某个容器中的各个元素而又无需暴露该容器的内部表述方式。 2迭代器的设计思维
不论是泛型思维或 STL 的实际运用迭代器iterators都扮演着重要的角色。STL 的中心思想在于将数据容器containers和算法algorithms分开彼此独立设计最后再以一剂粘合剂将它们撮合在一起而迭代器就是这个粘合剂。
迭代器是一种行为类似指针的对象而指针的各种行为中最常见也最重要的便是解引用dereference和成员访问member access因此迭代器最重要的编程工作就是对 operator* 和 operator- 进行重载overloading工作。当我们对一个迭代器对象解引用时我们就会得到这个迭代器所指向的内容
vectorint vec {1,2,3,4};
auto iter vec.begin(); // vec.begin() 会返回该容器中的第一个元素的迭代器
*iter; // 我们对这个迭代器解引用就会得到 vec 中的第一个元素 任何一个 STL 算法都需要获得由一对迭代器所标示的区间用以表示操作范围。这一对迭代器所标示的是个所谓的左闭右开区间以 [first, last) 表示。也就是说整个实际范围从 first 开始直到 last-1。迭代器 last 所指的是最后一个元素的下一位置。这种左闭右开的设计会带来许多的便利例如下面这个 STL 算法的循环设计
// find 接收两个迭代器与一个目标在这两个迭代器构成的范围内搜寻此目标
templateclass InputIterator, class T
InputIterator find(InputIterator first, InputIterator last, const T value) {while (first ! last and *first ! value)first;return first;
}
// 如果返回的迭代器是 last, 则表示没有找到目标
左闭右开示意图 下面来演示一下容器、算法、迭代器是怎么合作的以 find 函数为例 // 只要我们传入不同的迭代器find 函数就能够对不同的容器进行查找操作
vectorchar vec { a,b,c,d,e};
listint lt { 1,2,3,4,5,6 };auto it1 find(vec.begin(), vec.end(), d);
if (it1 vec.end()) cout not found endl;
else cout found endl;auto it2 find(lt.begin(), lt.end(), 5);
// ...3迭代器种类 在 C 中常见的迭代器种类包括以下几种 ① 前向迭代器Forward Iterator它们适用于单向遍历容器的所有元素支持递增操作。例如单向链表std::forward list使用的就是这种迭代器。 ② 双向迭代器Bidirectional Iterator它们是在前向迭代器的基础上增加了递减操作--的迭代器可以向前或向后遍历容器中的元素适用于双向遍历容器的所有元素。例如双向链表std::list使用的就是双向迭代器 ③ 随机访问迭代器Random Access Iterator它们是功能最为强大的迭代器支持任意两个迭代器之间的定位、偏移、比较等操作可以以常量时间实现跳跃访问。除了支持双向迭代器的所有操作外还支持迭代器的加减法运算以及比较大小的运算。例如对 std::vector 容器进行随机访问时使用的就是随机访问迭代器。 二迭代器与容器
1容器中的迭代器
在 STL 中几乎每个容器都会支持相应的迭代器类型。我们暂且以 std::list 为例来看看一个容器要设计出迭代器需要做哪些事情。前面有提到迭代器的行为类似于指针所以在迭代器类的模板参数列表中一定要有这个“指针”所指向的类型
templateclass T // T 是需要在链表中存放的数据类型
class List_Iterator{typedef List_IteratorT self;// 因为 std::list 是双向链表, 那自然我们要设计的迭代器肯定是双向迭代器了// 下面是双向迭代器需要实现的基本功能// 解引用与访问T operator*();T* operator-();// 前置 ,-- 与后置 ,--self operator();self operator(int);self operator--();self operator--(int);// 迭代器之间的比较bool operator();bool operator!();};
在容器 list 中我们就可以这样来使用这个迭代器
// 链表类
templateclass T
class list{
public:typedef List_IteratorT iterator;// ...
};
不过我们还要考虑一下 const 迭代器
typedef List_Iteratorconst T const_iterator; // 这样行吗迭代器最重要的编程工作就是对 operator* 和 operator- 进行重载工作所以迭代器中肯定会有返回值为 T 以及 T* 的函数。因此我们要考虑按照上面的 const 迭代器的设计T 和 T* 符合我们的预期吗我们来看以下代码
templateclass T
class List_Iterator {
private:T data 0;
public:List_Iterator() {}T reference() { return data; }T* pointer() { return data; }
};int main() {List_Iteratorconst int cit;// 我们所期望的const int expect_ref 0;const int* expect_ptr nullptr;// 实际的auto real_ref cit.reference();auto real_ptr cit.pointer();return 0;
}
我们调出监视窗口 嗯这样确实符合我们的预期。 但是我们还要考虑到如果迭代器需要使用原来的数据类型呢例如
templateclass T
class List_Iterator {
public:// List_Node 是链表的节点类型, 如果我们需要 T 来去拿到相应的节点类型呢?typedef List_NodeT Node;
};List_Iteratorconst int iter;
// 如果我们传入的模板参数是 const int, 那我们在 List_Iterator 中所取得的 Node
// 就是 List_Nodeconst int, 而我们所期望的 Node 是 List_Nodeint
所以很明显typedef List_Iteratorconst T const_iterator; 按照这样来设计肯定不行。
因此为了得到我们想要的 const 迭代器我们需要在迭代器类的模板参数列表中新添加两个参数引用类型与指针类型。解决方案如下
// T 是需要在链表中存放的数据类型, Ref 是引用类型, Ptr 是指针类型
templateclass T, class Ref, class Ptr
class List_Iterator{typedef List_IteratorT, Ref, Ptr self;// 因为在某些场景下需要用普通迭代器来构造 const 迭代器所以我们需要下面这两句typedef List_IteratorT, T, T* iterator;List_Iterator(iterator iter);// 为了提高代码的可读性和可维护性, 使得容器的模板参数更具有可定制性和通用性// 这里添加几个 typedef 来定义一下相应的类型, 这个非常重要typedef T value_type;typedef Ref reference;typedef Ptr pointer;// 解引用与访问reference operator*();pointer operator-();// 前置 ,-- 与后置 ,--self operator();self operator(int);self operator--();self operator--(int);// 迭代器之间的比较bool operator();bool operator!();};// 链表类
templateclass T
class list{
public:typedef List_IteratorT, T, T* iterator;typedef List_IteratorT, const T, const T* const_iterator;// ...
};
现在我们已经设计出来了 list 迭代器类型的框架了。不过要想实现一个针对 list 而设计的迭代器那必须得先对 list 的实现细节有着非常充分的了解尤其是实现 、-- 操作时虽然容器迭代器的框架都是类似的但是迭代器的具体实现工作还是就交给容器的设计者好啦。
对 list 迭代器的实现细节感兴趣的话可以看看这个C 简单模拟实现 STL 中的 list 与 queue-CSDN博客 2迭代器失效问题
会引起其底层空间改变的操作都有可能使迭代器失效我们来看下面这个例子
listint lt {1,2,3,4,5};
auto iter lt.begin();
lt.erase(1);
cout *iter endl; // 此时的 iter 还有效吗
所以为了避免使用失效的迭代器建议在进行可能导致迭代器失效的操作之后重新获取迭代器来确保迭代器的有效性。
listint lt {1,2,3,4,5};
auto iter lt.begin();
lt.erase(1);
iter lt.begin(); // 重新获取迭代器
cout *iter endl; 三迭代器的类型萃取traits
每个迭代器都会有自己的相应类型associated types在上文中我们尝试去设计 list 迭代器的时候就已经见识过了想要为一个容器设计一个专门的迭代器就至少会有 value_type、pointer、reference 这三种类型。根据大佬们的经验迭代器相应类型并不只有“迭代器所指向对象的类型即 value_type”最常用的相应类型有五种而 value_type、pointer、reference 就只是其中的三种这里就不详细介绍另外两种了。
在很多的情况下我们都需要拿到迭代器的相应类型在下一部分中我们去实现反向迭代器时就能够体会到了怎么拿到呢我们通过一个叫做 iterator_traits 的迭代器特性萃取机来拿到。
templateclass Iterator
struct iterator_traits {typedef typename Iterator::value_type value_type;typedef typename Iterator::pointer pointer;typedef typename Iterator::reference reference;// 下面这两种只是提一下, 后文不再出现这两种类型typedef typename Iterator::iterator_categoty iterator_category;typedef typename Iterator::difference_type difference_type;
};
这个萃取机依赖着这样一个规则凡是一个专门为容器设计的迭代器都有能力且因该定义自己的相应类型就比如在上文中写过的
// T 是需要在链表中存放的数据类型, Ref 是引用类型, Ptr 是指针类型
templateclass T, class Ref, class Ptr
class List_Iterator{// ...// 为了提高代码的可读性和可维护性, 使得容器的模板参数更具有可定制性和通用性// 这里添加几个 typedef 来定义一下相应的类型, 这个非常重要typedef T value_type;typedef Ref reference;typedef Ptr pointer;// ...
};
但是还有一个特殊的情况那就是原生指针。原生指针是一种天然的迭代器但是它没有能力去定义自己的相应类型。怎么办我们可以通过模板的特化partial specialization来解决这一问题。
// 针对迭代器本身是原生指针类型设计的特化版本
templateclass T
struct iterator_traitsT* {typedef T value_type;typedef T* pointer;typedef T reference;
};// 针对迭代器本身是 const 指针类型设计的特化版本
templateclass T
struct iterator_traitsconst T* {typedef T value_type;typedef const T* pointer;typedef const T reference;
};
iterator_traits 的示意图 四反向迭代器
1什么是适配器adapters
反向迭代器是一种迭代器适配器。适配器adapters在STL组件的灵活组合运用功能上扮演着轴承、转换器的角色。适配器这个概念事实上是一种设计模式。适配器的定义如下将一个 class 的接口转换为另一个 class 的接口使原本因接口不兼容而不能合作的 classes可以一起运作。
STL 所提供的各种配接器中改变仿函数functors接口者我们称为函数适配器function adapter改变容器containers接口者我们称为容器适配器container adapter改变迭代器iterators接口者我们称为迭代器适配器iterator adapter。 2什么是反向迭代器
reverse terator它的功能就是将迭代器的移动行为倒转。如果 STL 算法接受的不是一般正常的迭代器而是这种反向迭代器它就会以从尾到头的方向来处理序列中的元素。例如
vectorchar vec { 1,2,3,4,5,6 };find(vec.begin(), vec.end(), 7); // 从 1 开始查找到 6, 1-2-...-6
find(vec.rbegin(), vec.rend(), 7); // 从 6 开始查找到 1, 6-5-...-1
// rbegin() 返回反向迭代器的第一个元素, rend() 返回反向迭代器的最后一个元素我们可以先来看一下两段 vecotr 与 list 的部分源码
template class T
class vector {
public:typedef T value_type;typedef value_type* iterator;typedef reverse_iteratoriterator reverse_iterator;reverse_iterator rbegin() { return reverse_iterator(end()); }reverse_terator rend() { return reverse_iterator(begin()); }// ...
};template class T
class list {
public:typedef __list_iteratorT, T, T* iterator;typedef reverse_iteratoriterator reverse_iterator;reverse_iterator rbegin() { return reverse_iterator(end()); }reverse_terator rend() { return reverse_iterator(begin()); }// ...
};
在 STL 的容器中只要是双向序列容器就一定支持 rbegin() 与 rend() 操作。 3反向迭代器的实现
仔细观察一下上面的代码我们可以发现反向迭代器的 rbegin()rend() 分别对应着正向迭代器的 end() 与 begin()但是 rbegin()rend() 与 end()begin() 所指向的并不是同一个元素。如图 为什么要这么设计呢这其实主要是为了配合迭代器区间左闭右开的习惯我们想要将一个正向迭代器区间转换为一个反向迭代器区间的时候不要有任何的额外处理。那么反向迭代器的内部是怎么实现的呢
// 反向迭代器类
templateclass iterator
class Reverse_Iterator {
private:iterator _it; // 反向迭代器所对应的正向迭代器public:typedef Reverse_Iteratoriterator self;// 迭代器相应类型萃取typedef typename iterator_traitsiterator::reference reference;typedef typename iterator_traitsiterator::pointer pointer;typedef typename iterator_traitsiterator::value_type value_type;Reverse_Iterator(iterator it) :_it(it) {}Reverse_Iterator(const self re_it):_it(re_it._it){}// 将其他类型的反向迭代器转换为当前类型的反向迭代器iterator base()const { return _it; }templateclass iterReverse_Iterator(const Reverse_Iteratoriter re_it):_it(re_it.base()) {}// 下面这个函数就是反向迭代器的关键所在: 对反向迭代器取值// 就是将其对应的正向迭代器后退一个之后再取值reference operator*()const { iterator tmp _it;return *(--tmp);}pointer operator-()const { return (operator*()); }// 实际上变成 --self operator() { return --_it; }self operator(int) {iterator tmp _it;--_it;return tmp;}// -- 实际上变成 self operator--() { return _it; }self operator--(int) {iterator tmp _it;_it;return tmp;}bool operator(const self rit) { return _it rit._it; }bool operator!(const self rit) { return not (_it rit._it); }// ...
};
对反向迭代器进行 与 -- 的示意图
