公司网站建设需要收集什么信息,建设开发网站,常州网站建设系统,微信辅助网站制作#x1f388;个人主页:#x1f388; :✨✨✨初阶牛✨✨✨ #x1f43b;强烈推荐优质专栏: #x1f354;#x1f35f;#x1f32f;C的世界(持续更新中) #x1f43b;推荐专栏1: #x1f354;#x1f35f;#x1f32f;C语言初阶 #x1f43b;推荐专栏2: #x1f354;… 个人主页: :✨✨✨初阶牛✨✨✨ 强烈推荐优质专栏: C的世界(持续更新中) 推荐专栏1: C语言初阶 推荐专栏2: C语言进阶 个人信条: 知行合一 金句分享: ✨即使人生还有无数次失望的可能性,✨ ✨但我还是想活在理想主义的乌托邦里.✨ 目录 一、list底层框架(1) 节点类(2) 迭代器类(3) list类 二、构造函数(1) 无参构造(2) n个value构造(3) 迭代器区间构造(4) 拷贝构造 三、迭代器迭代器的实现① 构造② *和-③ 前置与后置④ 前置--与后置--⑤ 比较运算符 list类中的迭代器front和back 四、Modifiers:(1) insert()(2) erase()(3) push_back() 和 push_front()(4) pop_back() 和 pop_front()(5) clear()(6) swap() 结语 本篇通过模拟实现list的构造函数,迭代器,和部分成员函数以帮助大家更加深层的理解list的原理,希望看完这篇文章使得友友们对list有了更加深层的理解.
一、list底层框架
list的底层是一个带头双向循环链表.
(1) 节点类
因为list中节点可能存储各种类型的值,所以这里使用了一个模板参数T. list int listdoubel … // List的节点类templateclass Tstruct list_node{list_node(const T val T()):_val(val){}//这里的 T() 表示使用类型 T 的默认构造函数创建一个对象//它将调用 T 类型的默认构造函数来初始化 val。如果类型 T 没有提供默认构造函数那么代码将无法编译通过。list_nodeT* _prevnullptr; //指向前驱结点list_nodeT* _nextnullptr; //指向后继结点T _val; //存储数据};(2) 迭代器类
很多小伙伴会疑问,为什么一个迭代器类却使用了三个模板参数,是不是有些多余呢?
其实不然,牛牛依次为大家解释. class T: 是结点类的存储不同数据所需要使用的模板参数.该模板参数表示要处理的元素的类型。它可以是任意类型例如整数、浮点数、自定义类等等。在模板实例化时需要提供一个具体的类型。 Ref: 该模板参数表示指向元素类型 T 的引用。它定义了对元素的引用类型在实例化模板时将使用指定的引用类型来操作元素。 Ptr: 该模板参数表示指向元素类型 T 的指针。它定义了指向元素的指针类型在实例化模板时将使用指定的指针类型来操作元素。
templateclass T, class Ref, class Ptr 意味着 list_iteratorT, const T, const T*;
list的迭代器用来遍历链表中的元素,外部通过迭代器的和--进行链表的元素访问,这是一种封装,隐藏内部list的实现细节,外部只能通过迭代器的方式访问. //迭代器类templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr self;//self表示自己list_iterator(Node* node); //构造list_iterator(const self list); //拷贝构造Ref operator*();Ptr operator-();//前置self operator(); //后置self operator(int);//前置--self operator--();//后置--self operator--(int);bool operator!(const self list) const; bool operator(const self list);//成员变量Node* _node;};(3) list类 templateclass Tclass list{typedef list_nodeT Node;public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;list()//(无参构造)//n个value构造list(int n, const T value T());//迭代器区间构造template class Iteratorlist(Iterator first, Iterator last); //拷贝构造list(const listT list);//各种成员函数/...//析构函数~list();iterator begin(); iterator end();//常属性迭代器const_iterator begin()const;const_iterator end()const; private:Node* _head;size_t _size;};二、构造函数
对于带头双向循环链表,它的初始化操作是必须的,因为必须创建一个头指针. 对于list的构造函数,它是很多种方式的,例如:无参构造,n个val构造,迭代器区间构造等. 对于每个构造,必须前进行最初的初始化操作,为了避免代码冗余,我们将这个部分单独写成一个初始化操作的函数.
如下: void Init_List(){_head new Node; //创建头指针_head-_prev _head;_head-_next _head;_size 0;}
(1) 无参构造
调用Init_List();初始化函数即可. list()//初始化很重要(无参构造){Init_List();}(2) n个value构造
进行初始化操作.尾插n个value. //n个value构造list(int n, const T value T()){Init_List();while (n--){push_back(value);}}(3) 迭代器区间构造
进行初始化操作.利用迭代器的特性,一次将区间中的数据尾插入链表.
//迭代器区间构造template class Iteratorlist(Iterator first, Iterator last){Init_List();while (first ! last){push_back(*first);first;}}(4) 拷贝构造
链表在物理空间上是不连续的,所以,对于参数是另一个链表的拷贝构造,只能遍历链表进行依次插入数据. //拷贝构造list(const listT list){Init_List();auto it list.begin();while (_size!list._size){push_back(*it);it;}}三、迭代器
迭代器的实现
① 构造
迭代器本质就是一个 Node* _node;结点类的指针. 对于迭代器的构造函数,只需要将结点的地址传过来即可.
list_iterator(Node* node) //默认构造:_node(node) {}
list_iterator(const self list) //拷贝构造:_node(list._node){}② *和-
(1) * *运算符重载,表示对迭代器进行解引用. 使用场景:
listint::iterator it L1.begin();
int start*it;很明显,*运算符是需要获取结点所存储的数据.为了减少拷贝以及对数据进行修改,这里采用传引用(Ref )返回. Ref operator*() {return _node-_val;//获取该结点的数据}(2) -
上面链表中的数据是简单的类型int
Ptr operator-() {return _node-_val;// 等价于 return (_node-_val);}③ 前置与后置
对于链表,迭代器表示向后访问下一个(后继)结点.学过链表的友友们应该知道. 也就是 _node _node-_next;
前置,返回后的结点的迭代器 后置,返回前的结点的迭代器 //前置self operator() {_node _node-_next;return *this;}//后置self operator(int) {Node* tmp_node; //保存之前的值_node _node-_next;return tmp; //返回之前的值}④ 前置–与后置–
同理,返回当前结点迭代器的前驱结点. 也就是:_node _node-_prev;
前置–,返回–后的结点的迭代器 后置–,返回–前的结点的迭代器 //前置--self operator--(){_node _node-_prev;return *this;}//后置--self operator--(int){Node* tmp _node; //保存 -- 之前的值_node _node-_prev;return tmp; //返回 -- 之前的值}⑤ 比较运算符
比较迭代器是否相等,实际就是比较迭代器所指向的结点是否相等. bool operator!(const self list) const{return _node ! list._node;}bool operator(const self list){return _node list._node;}list类中的迭代器 iterator begin(): 返回第一个有效元素位置的迭代器 iterator end(): 返回最后一个有效元素位置的迭代器 typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;iterator begin(){return _head-_next;//也可以强转一下//return iterator(_head-_next);}iterator end(){return _head;//也可以强转一下// return iterator(_head);}//常属性迭代器const_iterator begin()const{return _head-_next;}const_iterator end()const{return _head;}front和back T front(){return _head-_next-_val;//返回值}const T front()const{return _head-_next-_val;}T back(){return _head-_prev-_val;}const T back()const{return _head-_prev-_val;}四、Modifiers:
其实带头双向循环链表的增删改查较于单链表,更加简单,我们画图分析还是很容易实现的.
(1) insert() (图片为博主原创,不得随意截图使用) 特殊情况:这是尾插: (图片为博主原创,不得随意截图使用) 代码示例 // 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){//pos.node 而不是pos-nodeNode* newnode new Node(val);Node* _prev_node pos._node-_prev; //pos位置结点的 原前置 结点Node* _cur_node pos._node; //pos位置的结点_prev_node-_next newnode;newnode-_prev _prev_node;_cur_node-_prev newnode;newnode-_next _cur_node;_size;//有效数据的个数1.return newnode;}(2) erase() // 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){Node* _prev_node pos._node-_prev; //pos位置结点的 原前置(prev) 结点Node* _next_node pos._node-_next; //pos位置结点的 原后置(next) 结点_next_node-_prev _prev_node;_prev_node-_next _next_node;delete pos._node;--_size;return _next_node;}(3) push_back() 和 push_front() //尾插//void push_back(const T val)//{// Node* newnode new Node(val);// Node* _tail_node _head-_prev; // 原尾结点// _tail_node-_next newnode;// newnode-_prev _tail_node;// _head-_prev newnode;// newnode-_next _head;// // _size;//有效数据的个数1.//}//复用insert更加方便void push_back(const T val){insert(end(),val);//在头结点前面插入,即为尾插}//头插void push_front(const T val) { insert(begin(), val);}
(4) pop_back() 和 pop_front()
复用即可,不过多介绍了. //尾删void pop_back() { erase(--end()); }//头删void pop_front() { erase(begin()); }(5) clear()
clear:清除list中的有效数据 遍历链表进行依次删除结点,并将size置为0. void clear(){iterator it begin();while (it ! end()){it erase(it);}_size 0;}(6) swap()
交换两个链表的成员变量即可. void swap(listT list){swap(_head, list._head);swap(_size, list._size);}结语
看完这篇文章,相信大家对list有了更加深层的理解,对于list的迭代器,它并不像前面的string和vector那种原生指针,而是封装成了类,使得链表的迭代器也可以执行和--等操作,因为迭代器类重载了这些运算符.
今天就分享到这里了,如果觉得有帮助的话,可以给牛牛来一个一键三连吗?谢谢支持!
