怎么样给公司做网站,成都注册公司代理公司,如何制作视频短片,如何用c语言做网站目录
编辑
一#xff0c; List的模拟实现
二#xff0c;代码实现
三、list和vector的区别 一#xff0c; List的模拟实现 List 是一个双向循环链表,由于List的节点不连续#xff0c;不能用节点指针直接作为迭代器#xff0c;因此我们要对结点指针封装#xff0c;来…
目录
编辑
一 List的模拟实现
二代码实现
三、list和vector的区别 一 List的模拟实现 List 是一个双向循环链表,由于List的节点不连续不能用节点指针直接作为迭代器因此我们要对结点指针封装来实现迭代器的作用。
迭代器有两种实现方式具体应根据容器底层数据结构实现 1. 原生态指针比如vector 2. 将原生态指针进行封装因迭代器使用形式与指针完全相同因此在自定义的类中必须实现以下方法 1. 指针可以解引用迭代器的类中必须重载operator*() 2. 指针可以通过-访问其所指空间成员迭代器类中必须重载oprator-() 3. 指针可以向后移动迭代器类中必须重载operator()与operator(int) 至于operator--()/operator--(int)释放需要重载根据具体的结构来抉择双向链表可以向前 移动所以需要重载如果是forward_list就不需要重载-- 4. 迭代器需要进行是否相等的比较因此还需要重载operator()与operator!() 二代码实现
#pragma once
#includeassert.h
#includeiostream
#include initializer_list
#includealgorithm
using namespace std;namespace BMH
{templateclass Tstruct ListNode{typedef ListNodeT Node;Node* _prev;Node* _next;T _data;ListNode(const T data T()):_prev(nullptr), _next(nullptr), _data(data){}};templateclass T, class Ref, class Ptrstruct ListIterator{//正向迭代器typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;// Ref 和 Ptr 类型需要重定义下实现反向迭代器时需要用到public:typedef Ref Ref;typedef Ptr Ptr;Node* _node;ListIterator(Node* node nullptr):_node(node){}//itSelf operator(){_node _node-_next;return *this;//it 返回自己迭代器}//--itSelf operator--(){_node _node-_prev;return *this;}//itSelf operator(int){Self tmp(*this);_node _node-_next;return tmp;}//it--Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}//// 具有指针类似行为//*it 返回值Ref operator*(){return _node-_data;;}//it- 返回指针Ptr operator-(){return (_node-_data);}////// 迭代器支持比较bool operator (const Self it){return _node it._node;}bool operator ! (const Self it){return _node ! it._node;}};templateclass Tclass List{public:typedef ListNodeT Node;typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;/////初始化创建头结点void empty_init(){_head new Node();_head-_prev _head;_head-_next _head;}//构造函数List(){empty_init();}List(int n, const T value T()){empty_init();for (int i 0; i n; i)push_back(value);}//用下面拷贝构造函数来实现构造函数拷贝构造函数是构造函数的一种。//Listint lt2(lt1)//List(const ListT lt)//{// empty_init();// for (const auto e : lt)// {// Push_Back(e);// }//}//Listint lt1 {1,2,3,4}List(initializer_listT il)//不用引用的原因il本身是两个指针拷贝代价小{empty_init();for (const auto e : il){Push_Back(e);}}templateclass Inputiterator List(Inputiterator p1, Inputiterator p2){empty_init();while (p1 ! p2){Push_Back(*p1);p1;}}//拷贝构造//lt2(lt1)List(const ListT lt){empty_init();for (const auto e : lt){Push_Back(e);}}//赋值重载//lt1lt2ListT operator(ListT lt){swap(_head, lt._head);return *this;}void clear(){iterator it begin();while (it ! end()){it erase(it);//用erase时会发生迭代器失效}}~List(){clear();delete _head;_head nullptr;}/////迭代器iterator 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);}///// 容量相关//尾插void Push_Back(const T x){Node* tail _head-_prev;Node* newnode new Node(x);newnode-_prev tail;tail-_next newnode;newnode-_next _head;_head-_prev newnode;}void Pop_Back(){erase(--end());}void Push_Front(const T x){insert(begin(),x);}void Pop_Front(){erase(begin());}//之前插入无迭代器失效iterator insert(iterator pos ,const T data ){Node* cur pos._node;//pos是迭代器找到其中的节点地址即可Node* newnode new Node(data);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur- _prev newnode;return iterator(newnode);}//有迭代器失效,返回删除节点下一个的迭代器iterator erase(iterator pos){assert(pos! (*this).end());//防止将Node* cur pos._node;Node* next cur-_next;Node* prev cur-_prev;prev-_next next;next-_prev prev;delete cur;return iterator(next);}private:Node* _head;}; 三、list和vector的区别 1、任意位置插入删除时list可以随意插入删除但是vector任意位置的插入删除效率低需要挪动元素尤其是插入时有时候需要异地扩容就需要开辟新空间拷贝元素释放旧空间效率很低 2、访问元素时vector支持随机访问但是list不支持随机访问 3、迭代器的使用上vector可以使用原生指针但是list需要对原生指针进行封装 4、空间利用上vector使用的是一个连续的空间空间利用率高而list使用的是零碎的空间空间利用率低 这个博客如果对你有帮助给博主一个免费的点赞就是最大的帮助❤
欢迎各位点赞收藏和关注哦❤
如果有疑问或有不同见解欢迎在评论区留言哦❤
后续我会一直分享双一流211西北大学软工C数据结构CLinuxMySQL的学习干货以及重要代码的分享
