一、背景
迭代器(iterator)是一种抽象的设计理念,即迭代器模式,通过迭代器可以在不了解容器内部原理的情况下遍历容器。除此之外,STL中迭代器一个最重要的作用就是作为容器(vector,queue,list,map等)与STL算法的粘结剂,只要容器提供迭代器的接口,同一套算法代码可以利用在完全不同的容器中。
二、使用迭代器
如下所示的代码演示了迭代器是如何将容器和算法结合在一起的,其中使用了三种不同的容器,begin()和end()方法返回一个指向容器第一个元素和指向容器最后一个元素后面一个位置的迭代器。对于不同的容器,我们都使用同一个find函数。原因就在于find函数的实现无需考虑容器的种类,只需要容器传入的begin()和end() 迭代器能够完成标准迭代器的要求即可。
#include <iostream>
#include <vector>
#include <deque>
#include <list>
#include <algorithm>
int main(int argc, char *argv[])
{
const int arraysize = 7;
int ia[arraysize] = { 0, 1, 2, 3, 4, 5, 6 };
vector<int > ivect(ia, ia + arraysize);
list <int> ilist(ia, ia + arraysize);
deque<int> ideque(ia, ia + arraysize);
// 对vector使用find
vector<int>::iterator itl = find(ivect.begin(), ivect.end(), 4);
if (itl == ivect.end())
{
std::cout << "vector ,4 is not find" << endl;
}
else
{
std::cout << "vector ,4 is find" << endl;
}
// 对list使用find
list<int>::iterator it2 = find(ilist.begin(), ilist.end(), 4);
if (it2 == ilist.end())
{
std::cout << "list ,4 is not find" << endl;
}
else
{
std::cout << "list ,4 is find" << endl;
}
// 对deque使用find
deque<int>::iterator it3 = find(ideque.begin(), ideque.end(), 8);
if (it3 == ideque.end())
{
std::cout << "deque ,8 is not find" << endl;
}
else
{
std::cout << "deque ,8 is find" << endl;
}
system("pause");
return 0;
}
三、迭代器的分类
常用的迭代器分为5个类别
Input itertor (输入迭代器) 只读;只支持自增运算
Output itertor(输出迭代器)只写;只支持自增运算
Forward itertor(前向迭代器)读写;只支持自增运算
Bidirectional itertor(双向迭代器)读写;支持自增和自减
Random access itertor(随机访问迭代器)读写;支持完整迭代器算数运算
这五种迭代器的继承关系如下所示。
3.1 输入迭代器
输入迭代器可用于读取容器中的元素,但是不保证能支持容器的写入操作。输入迭代器必须至少提供下列支持:
- 相等和不等操作符(==,!=),比较两个迭代器。
- 前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。
- 用于读取元素的解引用操作符(*),此操作符只能出现在赋值运算的右操作数上。
- 箭头操作符(->),这是 (*it).member 的同义语,也就是说,对迭代器进行解引用来获取其所关联的对象的成员。
输入迭代器只能顺序使用,一旦输入迭代器自增了,就无法再用它检查之前的元素。要求在这个层次上提供支持的泛型算法包括 find 和 accumulate,标准库 istream_iterator 类型输入迭代器。
3.2 输出迭代器
输出迭代器可视为与输入迭代器功能互补的迭代器, 输出迭代器可用于向容器写入元素,但是不保证能支持读取容器内容。输出迭代器要求:
- 前置和后置的自增运算(++),使迭代器向前递进指向下一个元素。
- 解引用操作符(*),该引操作符只能出现在赋值运算的左操作数上。给解引用的输出迭代器赋值,将对该迭代器所指向的元素做写入操作。
- 输出迭代器可以要求每个迭代器的值必须正好写入一次。使用输出迭代器时,对于指定的迭代器值应该使用一次 * 运算,而且只能用一次。
输出迭代器一般用作算法的第三个实参, 标记起始写入的位置。 例如, copy 算法使用一个输出迭代器作为它的第三个实参, 将输入范围内的元素复制到输出迭代器指定的目标位置。标准库 ostream_iterator 类型输出迭代器。
3.3 前向迭代器
- 前向迭代器用于读写指定的容器。这类迭代器只会以一个方向遍历序列。
前向迭代器支持输入迭代器和输出迭代器提供的所有操作,除此之外,还支持对同一个元素的多次读写。可复制前向迭代器来记录序列中的一个位置,以便将来返回此处。需要前向迭代器的泛型算法包括 replace。
3.4 双向迭代器
- 双向迭代器从两个方向读写容器。除了提供前向迭代器的全部操作之外,双向迭代器还提供前置和后置的自减运算(–)。
需要使用双向迭代器的泛型算法包括 reverse。所有标准库容器提供的迭代器都至少达到双向迭代器的要求。
3.5 随机访问迭代器
随机访问迭代器提供在常量时间内访问容器任意位置的功能。这种迭代器除了支持双向迭代器的所有功能之外,还支持下面的操作:
- 关系操作符 <、<=、> 和 >=,比较两个迭代器的相对位置。
- 迭代器与整型数值 n 之间的加法和减法操作符 +、+=、- 和 -=,结果是迭代器在容器中向前(或退回)n 个元素。
- 两个迭代器之间的减法操作符(–),得到两个迭代器间的距离。
- 下标操作符 iter[n],这是 *(iter + n) 的同义词。
需要随机访问迭代器的泛型算法包括 sort 算法。vector、deque 和string 迭代器是随机访问迭代器,用作访问内置数组元素的指针也是随机访问迭代器。
四、迭代器的实现
迭代器的作用就是提供一个遍历容器内部所有元素的接口,因此迭代器的内部必须保存一个与容器相关联的指针,然后重载各种运算操作来方便遍历,其中最重要的就是operator*运算符和operator->运算符,以及++,--等可能需要的运算符重载。
下面参照智能指针实现了一个简单vector的迭代器。vecIter主要作用就是包裹一个指针,不同容器内部数据结构不相同,因此迭代器操作符重载的实现也会不同。比如++操作符,对于线性分配内存的数组来说,直接对指针执行++操作即可,但是如果容器是List就需要采用元素内部的方法,比如ptr->next()之类的方法访问下一个元素。因此,STL容器都实现了自己的专属迭代器。
template<class Item>
class vecIter{
Item *ptr;
public:
typedef std::forward_iterator_tag iterator_category;
typedef Item value_type;
typedef Item* pointer;
typedef Item& reference;
typedef std::ptrdiff_t difference_type;
public:
vecIter(Item *p = 0) :ptr(p){}
Item& operator*()const{
return *ptr;
}
Item* operator->()const{
return ptr;
}
//pre
vecIter& operator++(){
++ptr;
return *this;
}
vecIter operator++(int){
vecIter tmp = *this;
++*this;
return tmp;
}
bool operator==(const vecIter &iter){
return ptr == iter.ptr;
}
bool operator!=(const vecIter &iter){
return !(*this == iter);
}
};
int main(){
int a[] = { 1, 2, 3, 4 };
std::cout << std::accumulate(vecIter<int>(a), vecIter<int>(a + 4), 0);//输出 10
}
参考:
迭代器模式(详解版)
C++:标准模板库(STL)_码农code之路的博客-CSDN博客
C++标准模板库(STL)迭代器的原理与实现_wutao02的博客-CSDN博客_stl迭代器实现
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)