在线做海报的网站,旅游网站功能,建站公司属于什么类型,网站建设自学教程文章目录 list和vector的迭代器对比list的实现过程完整代码 本篇是关于vector和list的模拟实现中#xff0c;关于迭代器模块的更进一步理解#xff0c;以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等
本篇是写于前面模拟实现的一段时间后#xff0c;重新回头… 文章目录 list和vector的迭代器对比list的实现过程完整代码 本篇是关于vector和list的模拟实现中关于迭代器模块的更进一步理解以及在前文的基础上增加对于反向迭代器的实现和库函数的对比等
本篇是写于前面模拟实现的一段时间后重新回头看迭代器的实现尤其是在模板角度对list中迭代器封装的部分进行解析希望可以对迭代器的封装实现有更深层次的理解同时将与库内的实现做对比进行优化处理
list和vector的迭代器对比
list和vector的迭代器实现是不一样的在vector中的迭代器就是一个原生指针因此在实现的时候也就是用的原生指针即可但是对于list来说不能这样list的迭代器中例如和--这样的操作是不能和vector中的原生指针一样直接去实现的而是需要用next或者是prior来模拟这个过程还有例如*和-这样的访问数据的模式因此在list的迭代器实现中是使用了封装来进行实现的
STL中有六大组件其中迭代器算其中一个那么也就意味着迭代器具有通用的功能例如下面的代码在使用构造函数时可以使用迭代器进行构造而这个构造的过程使用的迭代器对于各种容器来说都是通用的
#include iostream
#include vector
#include list
using namespace std;int main()
{vectorint v1{ 1,2,3,4,5,3,2,2 };vectorint v2(v1.begin(), v1.end());listint l1(v1.begin(), v1.end());return 0;
}那么就意味着在实现迭代器的过程中也是就可以根据迭代器来进行不同容器间的构造
list的实现过程
首先在list的实现过程中要有下面几个部分组成list中包含的节点list的迭代器访问list的节点之间的关系
那么首先就是list中节点的定义用到了模板现在再对该部分进行解析其实就是在创建的时候可以根据需要的内容开辟出对应的节点类型
templateclass T
struct list_node
{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}
};有了节点信息就可以对list做一些基础的操作例如头插头删尾插尾删等操作但对于insert和erase这些操作还不能够实现因此就要实现迭代器模块的内容
不管是对于vector还是list迭代器的本质就是用一个原生指针去进行访问等等但是list和vector不同的是list的存储地址并不是连续的因此在访问的过程中就需要对迭代器进行一定程度的封装例如在或者--的操作符上可以进行一些体现因此list迭代器的实现是需要进行单独的封装的
// 定义正向迭代器
template class T, class Ref, class Ptr
class __list_iterator
{
public:typedef list_nodeT Node;typedef __list_iteratorT, T, T* self;__list_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator !(const self s){return _node ! s._node;}bool operator (const self s){return _node s._node;}Node* _node;
};上面的片段对list进行了一些封装实现了它的一些基础功能从代码中也能看出来迭代器的本质确确实实就是指针用指针来进行一系列的操作对下面这几个片段单独进行解析 Ptr operator-(){return _node-_data;}这是对于迭代器中解引用的运算符重载这里使用的是_node-_data的写法看似很怪但是实际上这里的函数调用过程应该是这样 也就是说这里对于-进行运算符重载后还需要进行解引用这个运算符重载函数返回的是一个指针而这个指针还要继续进行解引用才能得到用户想要得到的值编译器在这里进行了特殊处理两个-使得可读性下降因此将两个-进行了一定程度的合并只需要一个-就可以实现解引用的目的
其次是对模板的使用部分
template class T, class Ref, class Ptrtypedef list_nodeT Node;typedef __list_iteratorT, T, T* self;这里在最开始定义的时候就定义了数据类型引用和指针三种模板参数借助这个参数就可以用模板将复杂的内容实现简单化只需要一份代码模板就可以直接实例化出用户在调用的时候需要的代码在进行封装const迭代器的时候只需要提供的参数改为const版本就可以实现目的很便捷
这样就实现了正向迭代器的普通版本而对于const迭代器的版本也只需要进行不同的模板参数就可以实例化出const版本的迭代器
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;有了迭代器在实现链表的各种函数功能就更加方便例如可以实现erase和insert的操作实现了这两个函数在进行头插头删尾插尾删的时候就更加方便只需要进行原地的调用即可 // Modifiersvoid push_front(const T val){//Node* newnode new Node;//newnode-_data val;//newnode-_next _head-_next;//_head-_next-_prev newnode;//_head-_next newnode;//newnode-_prev _head;//_size;insert(begin(), val);}void pop_front(){//Node* delnode _head-_next;//_head-_next _head-_next-_next;//_head-_next-_prev _head;//delete delnode;//delnode nullptr;//_size--;erase(begin());}void push_back(const T val){//Node* newnode new Node;//newnode-_data val;//newnode-_prev _head-_prev;//_head-_prev-_next newnode;//newnode-_next _head;//_head-_prev newnode;//_size;insert(end(), val);}void pop_back(){//Node* delnode _head-_prev;//delnode-_prev-_next _head;//_head-_prev delnode-_prev;//delete delnode;//delnode nullptr;//_size--;erase(--end());}iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);_size;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;cur nullptr;_size--;prev-_next next;next-_prev prev;return iterator(next);}那么上面是对前面已经有过的内容进行的重新温故但是上面的代码其实是没有实现反向迭代器的而在STL的库中反向迭代器的定义和正向迭代器其实并不相同它是直接借助正向迭代器对反向迭代器进行适配有些类似于用vectorlist或者deque对栈和队列进行的适配也体现了封装和代码复用
templateclass Iterator, class Ref, class Ptr
class ReverseIterator
{
public:typedef ReverseIteratorIterator, Ref, Ptr Self;ReverseIterator(Iterator it):_it(it){}Self operator(){--_it;return *this;}Ref operator*(){return *_it;}Ptr operator-(){return _it.operator-();}bool operator!(const Self s){return _it ! s._it;}
private:Iterator _it;
};上面的代码就是对于反向迭代器的封装从中可以看出反向迭代器是使用了正向迭代器的并且在它的基础上进行的修改因此这个反向迭代器是可以适配于vector也可以适配于list的
整体来说对于反向迭代器就是用正向迭代器进行适配出来的体现了模板的好处
完整代码
#pragma oncenamespace mylist
{// 定义节点内容template class Tstruct list_node{list_node(const T x T()):_data(x), _next(nullptr), _prev(nullptr){}T _data;list_nodeT* _next;list_nodeT* _prev;};// 定义正向迭代器template class T, class Ref, class Ptrclass __list_iterator{public:typedef list_nodeT Node;typedef __list_iteratorT, T, T* self;__list_iterator(Node* node):_node(node){}self operator(){_node _node-_next;return *this;}self operator(int){self tmp(*this);_node _node-_next;return tmp;}self operator--(){_node _node-_prev;return *this;}self operator--(int){self tmp(*this);_node _node-_prev;return tmp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator !(const self s){return _node ! s._node;}bool operator (const self s){return _node s._node;}Node* _node;};// 定义反向迭代器templateclass Iterator, class Ref, class Ptrclass reverse_iterator{typedef reverse_iteratorIterator, Ref, Ptr self;public:reverse_iterator(Iterator it):_it(it){}self operator(){_it--;return *this;}self operator(int){self tmp(*this);_it--;return tmp;}self operator--(){_it;return *this;}self operator--(int){self tmp(*this);_it;return tmp;}Ref operator*(){Iterator cur _it;return *(--cur);}Ptr operator-(){return (operator*());}bool operator !(const self s){return _it ! s._it;}bool operator (const self s){return _it s._it;}Iterator _it;};// 定义链表template class Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef reverse_iteratoriterator, T, T* reverse_iterator;//typedef reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;// Constructorlist(){empty_init();}list(const listT lt){for (auto x : lt){push_back(x);}}list(iterator begin, iterator end){empty_init();while (begin ! end){push_back(begin._node-_data);begin;}}//list(reverse_iterator rbegin, reverse_iterator rend)//{// empty_init();// while (rbegin ! rend)// {// push_back(rbegin._node-_data);// rbegin;// }//}// Destructor~list(){clear();delete _head;_head nullptr;}// OperatorlistT operator(const listT lt){swap(lt);return *this;}// Iteratorsiterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}//const_reverse_iterator rbegin() const//{// return const_reverse_iterator(end());//}//const_reverse_iterator rend() const//{// return const_reverse_iterator(begin());//}// Capacitybool empty(){return _size 0;}size_t size(){return _size;}// Element accessT front(){return begin()._node-_data;}T back(){return (--end())._node-_data;}// Modifiersvoid push_front(const T val){//Node* newnode new Node;//newnode-_data val;//newnode-_next _head-_next;//_head-_next-_prev newnode;//_head-_next newnode;//newnode-_prev _head;//_size;insert(begin(), val);}void pop_front(){//Node* delnode _head-_next;//_head-_next _head-_next-_next;//_head-_next-_prev _head;//delete delnode;//delnode nullptr;//_size--;erase(begin());}void push_back(const T val){//Node* newnode new Node;//newnode-_data val;//newnode-_prev _head-_prev;//_head-_prev-_next newnode;//newnode-_next _head;//_head-_prev newnode;//_size;insert(end(), val);}void pop_back(){//Node* delnode _head-_prev;//delnode-_prev-_next _head;//_head-_prev delnode-_prev;//delete delnode;//delnode nullptr;//_size--;erase(--end());}iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);_size;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;cur nullptr;_size--;prev-_next next;next-_prev prev;return iterator(next);}void swap(const listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}void clear(){Node* cur _head-_next;while (cur ! _head){Node* next cur-_next;delete(cur);cur next;}_head-_next _head;_head-_prev _head;}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_head-_data T();_size 0;}void Print(){Node* cur _head-_next;while (cur ! _head){cout cur-_data -;cur cur-_next;}cout null endl;}private:Node* _head;size_t _size;};void test_iterator(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout iterator constructor:;listint lt1(lt.begin(), lt.end());lt1.Print();cout front(): lt.front() endl;cout back(): lt.back() endl;mylist::__list_iteratorint, int, int* it lt.begin();while (it ! lt.end()){std::cout *it ;it;}cout endl;}void test_clear(){listint lt1;cout push_back: endl;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.Print();lt1.clear();lt1.push_back(5);lt1.push_back(6);lt1.push_back(7);lt1.push_back(8);lt1.Print();}void test_push_pop(){listint lt1;cout push_back: endl;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);lt1.Print();cout pop_back: endl;lt1.pop_back();lt1.Print();listint lt2;cout push_front: endl;lt2.push_front(1);lt2.push_front(2);lt2.push_front(3);lt2.push_front(4);lt2.Print();cout pop_front: endl;lt2.pop_front();lt2.Print();}void test_reverse_iterator(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);cout iterator constructor:;//listint lt1(lt.rbegin(), lt.rend());//lt1.Print();cout front(): lt.front() endl;cout back(): lt.back() endl;mylist::listint::reverse_iterator rit lt.rbegin();while (rit ! lt.rend()){std::cout *rit ;rit;}cout endl;}void test(){test_reverse_iterator();//test_push_pop();//test_clear();}
}
