服务器和网站的关系,网站成立时间查询,免费咨询刑事辩护在线律师,个人博客网站搭建模板目录
迭代器
介绍
种类
本质
介绍
模拟实现
注意点
代码 迭代器
介绍 在C中#xff0c;迭代器#xff08;Iterators#xff09;是一种用于遍历容器#xff08;如数组、vector、list等#xff09;中元素的工具 无论容器的具体实现细节如何,访问容器中的元素的方…目录
迭代器
介绍
种类
本质
介绍
模拟实现
注意点
代码 迭代器
介绍 在C中迭代器Iterators是一种用于遍历容器如数组、vector、list等中元素的工具 无论容器的具体实现细节如何,访问容器中的元素的方法都是统一的,使用者不需要知道具体实现的细节 迭代器的概念类似于指针但迭代器更为通用可以适用于各种不同类型的容器(且不同对象的迭代器,种类也不同)迭代器在算法函数中也可以使用,这样可以兼容不同的容器(比如sort,find),就可以使用通用的算法模板 种类 迭代器分为几种不同类型每种类型对应不同的容器特性和访问方式 输入迭代器Input Iterator仅支持从容器中读取数据类似于只读操作。它们一次只能移动一个位置不允许修改容器的元素。 输出迭代器Output Iterator仅支持向容器中写入数据类似于只写操作。与输入迭代器类似一次只能移动一个位置。 前向迭代器Forward Iterator支持读取和写入操作并且可以多次遍历容器。每次移动一个位置。 双向迭代器Bidirectional Iterator与前向迭代器类似但可以向前和向后移动每次一个位置。 随机访问迭代器Random Access Iterator具有最强大的功能可以在常量时间内跳转到容器中的任何位置支持读取、写入和算术操作 这几种迭代器互相有包含关系,比如可以使用双向迭代器的,也可以使用随机迭代器 不同的迭代器用以支持遍历不同类型的容器,以及限制了算法函数兼容的容器类型(比如sort就不支持list类型)每个容器都有自己对应的迭代器类型 本质 实际上都是指针,有些容器的迭代器可以直接使用指针(eg:vector),但有些不行(eg: list) list的物理空间并不连续,直接使用无法实现的效果,其他功能也不行因此就需要创建一个类,来规定迭代器的操作 介绍 list是标准模板库STL提供的一个双向带头链表容器类 上面有说,list并不支持sort,但list内部有自己的sort 虽然是这样没错,但既然不支持,自然有它的道理内部的sort在遇到大数据时,远不如 将数据拷贝到vector中,由vector使用sort排序,再将排序后的数据恢复成list 的效率高当然,小数据的时候就不需要这些麻烦的操作了,这时候内部的sort还是很方便嘟 模拟实现 注意点 迭代器封装结点封装(以及进行了重命名,会有各种嵌套)结点类中有前后指针数据,list类中有头结点指针结点个数,迭代器是结点指针包装后的产物 const迭代器的实现 (模板参数)两种迭代器 在list类中传参重命名 实例化,可以传指针构造,也有拷贝构造 - 符号的重载 (-重载函数返回指针,因此访问迭代器的实际语法应为 it - -begin(),是编译器简化成了只有一个-)list的多种拷贝构造 代码
#include iostream
#include assert.h
#include stringusing namespace std;namespace bit
{// List的节点类template class Tstruct ListNode // struct默认公有(因为不会有人去访问结点成员的){typedef ListNodeT *PNode;ListNode(const T val T()): _ppre(nullptr), _pnext(nullptr), _val(val){};PNode _ppre;PNode _pnext;T _val;};// List的迭代器类 -- 因为无法直接使用指针作为迭代器,需要手动添加功能template class T, class Ref, class Ptr // ref用于标记*时对象的const属性,ptr用于标记-时返回对象的const属性class ListIterator{public:typedef ListNodeT *PNode; // 指针重命名typedef ListIteratorT, Ref, Ptr Self; // 迭代器重命名PNode _pNode; // 将指针作为迭代器的底层public:ListIterator(PNode pnode nullptr): _pNode(pnode){};ListIterator(const Self l): _pNode(l._pNode){};T operator*(){return _pNode-_val;}T *operator-(){return (_pNode-_val);}Self operator(){_pNode _pNode-_pnext;return (*this);}Self operator(int){Self tmp(*this);_pNode _pNode-_pnext;return tmp;}Self operator--(){_pNode _pNode-_ppre;return (*this);}Self operator--(int){Self tmp(*this);_pNode _pNode-_ppre;return tmp;}bool operator!(const Self l){return _pNode ! l._pNode;}bool operator(const Self l){return _pNode l._pNode;}};// list类template class Tclass mylist{typedef ListNodeT Node;typedef Node *PNode;public: // 两种迭代器typedef ListIteratorT, T , T * iterator;typedef ListIteratorT, const T , const T const_iterator;public:// List的构造mylist(){CreateHead();}mylist(int n, const T value T()){CreateHead();PNode p _pHead;for (size_t i 0; i n; i){push_back(value);}_size n;}template class Iteratormylist(Iterator first, Iterator last){CreateHead();while (first ! last){push_back(*first);first;}}mylist(const mylistT l){CreateHead();for (auto c : l){push_back(c);}}mylistT operator(const mylistT l){swap(l);return (*this);}~mylist(){// clear();// delete[] _pHead;while (!empty()){erase(begin());}}// List Iteratoriterator begin(){return iterator(_pHead-_pnext);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead-_pnext);}const_iterator end() const{return const_iterator(_pHead);}// List Capacitysize_t size() const{return _size;}bool empty() const{return _size 0;}// List AccessT front(){return *begin();}const T front() const{return *begin();}T back(){return *(--end());}const T back() const{return *(--end());}// List Modifyvoid push_back(const T val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){PNode cur pos._pNode;PNode pre cur-_ppre;PNode newnode new Node(val);newnode-_pnext cur;pre-_pnext newnode;cur-_ppre newnode;newnode-_ppre pre;_size;return newnode;}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){PNode cur pos._pNode;PNode pre cur-_ppre, next cur-_pnext;pre-_pnext cur-_pnext;cur-_pnext-_ppre pre;delete cur;--_size;return next;}void clear(){PNode cur _pHead-_pnext;while (cur ! _pHead){PNode tmp cur;cur cur-_pnext;delete tmp;}_size 0;// iterator it begin();// while (it ! end())// {// it erase(it);// }}void swap(mylistT l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:void CreateHead(){_pHead new Node;_pHead-_pnext _pHead;_pHead-_ppre _pHead;_size 0;}PNode _pHead;size_t _size;};
};
