浦项建设内部网站,安徽省网站建设,wordpress和织梦区别,wordpress function.php目录 list
结点类
结点类的构造函数
list的尾插尾删
list的头插头删
迭代器
运算符重载
--运算符重载
和! 运算符重载
* 和 - 运算符重载 list 的insert
list的erase list
list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要…目录 list
结点类
结点类的构造函数
list的尾插尾删
list的头插头删
迭代器
运算符重载
--运算符重载
和! 运算符重载
* 和 - 运算符重载 list 的insert
list的erase list
list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要存储的信息为:数据、前驱指针、后继指针
而对于该结点类的成员函数来说,我们只需实现一个构造函数即可,因为该结点类只需要根据数据来构造一个结点即可,而结点的释放则由list的析构函数来完成,
结点类
结点类的基本结构 templateclass Tstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _date;ListNode(const T pos T()){_next nullptr;_prev nullptr;_date pos;}};
这里用struct 的原因是因为ListNode 的 每个成员变量都会被频繁调用。
用struct则不需要封装了。
结点类的构造函数
构造函数直接根据所给数据构造一个结点即可,构造出来的结点的数据域存储的就是所给数据,而前驱指针和后继指针均初始化为空指针即可 ListNode(const T pos T()){_next nullptr;_prev nullptr;_date pos;}
list的尾插尾删 templateclass Tclass list{public:typedef ListNodeT node; list():_head(new node){_head-_next _head;_head-_prev _head;}void push_back(const T x){node* head _head;node* tail _head-_prev;node* p new node(x);tail-_next p;p-_prev tail;p-_next head;head-_prev p;}void pop_back(){assert(_head ! _head-_next);node* head _head;node* tail head-_prev;node* newtail tail-_prev;newtail-_next head;head-_prev newtail;delete[] tail;}private:node* _head;};
list的头插头删 templateclass Tclass list{public: typedef ListNodeT node;list():_head(new node){_head-_next _head;_head-_prev _head;}void push_front(const T x){node* newnode new node(x);node* head _head;node* tail _head-_next;head-_next newnode;newnode-_prev head;newnode-_next tail;tail-_prev newnode;}void pop_front(){assert(_head ! _head-_next);node* head _head;node* tail _head-_next;head-_next tail-_next;tail-_next-_prev head;delete[]tail;}private:node* _head;};
迭代器
迭代器有两种实现方式,具体应根据容器底层数据结构实现
原生态指针,比如vector和string -物理空间是连续的因为string和vector对象都将其数据存储在了一块连续的内存空间,我们通过指针进行自增、自减以及解引用等操作,就可以对相应位置的数据进行一系列操作,因此string和vector当中的迭代器就是原生指针。.将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法
指针可以解引用,迭代器的类中必须重载operator*() 指针可以通过-访问其所指空间成员,迭代器类中必须重载oprator-() 指针可以向后移动,迭代器类中必须重载operator()与operator(int) 至于operator--()/operator--(int) 是否需要重载,根据具体的结构来抉择,双向链表可 以向前 移动,所以需要重载,如果是forward_list就不需要重载– 迭代器需要进行是否相等的比较,因此还需要重载operator()与operator!() 但是对于list来说,其各个结点在内存当中的位置是随机的,并不是连续的,我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作,
总结list的迭代器 实际上就是对结点指针进行了封装,对其各种运算符进行了重载,使得结点指针的各种行为看起来和普通指针一样,例如,对结点指针自增就能指向下一个结点 p p-next templateclass T1, class T2struct Reverse_iterator{typedef Reverse_iteratorT1, T2 self;typedef ListNodeT1 node;node* _it;Reverse_iterator(node* pos)self operator()self operator(int)self operator--()self operator--(int)T2 operator*()T2* operator-()bool operator!(const self pos)bool operator(const self pos)}
迭代器模板参数说明
构造函数 迭代器类实际上就是对结点指针进行了封装
其成员变量就是结点指针,所以其构造函数直接根据所给结点指针构造一个迭代器对象即可, Reverse_iterator(node* pos){_it pos;}
拷贝构造,operator,析构函数我们都不需要写,因为成员变量是内置类型(指针), 用编译器默认生成的就可以。
运算符重载 self operator()//前置{_it _it-_prev;return *this;}self operator(int)//后置{self tmp(_it);_it _it-_prev;return tmp;}
前置原本的作用是将数据自增,然后返回自增后的数据,
而对于结点迭代器的前置:应该先让结点指针指向后一个结点.然后再返回“自增”后的结点迭代器即可
后置,先拷贝构造当前迭代器结点, 然后让当前迭代器结点的指针自增指向下一个结点,最后返回“自增”前的结点迭代器即可,
--运算符重载 self operator--()//前置{_it _it-_next;return *this;}self operator--(int)//后置{self tmp(_it);_it _it-_next;return tmp;}
前置- -当前迭代器结点中的指针指向前一个结点,然后再返回“自减”后的结点迭代器即可,
后置--拷贝构造当前迭代器对象 - 当前迭代器结点中的指针自减指向前一个结点 -返回自减前的迭代器。
和! 运算符重载 bool operator!(const self pos){return _it ! pos._it;}bool operator(const self pos){return _it pos._it;}
这里注意形参别写错就好了。
* 和 - 运算符重载
使用解引用操作符时,是想得到该指针指向的数据内容
因此,我们直接返回当前结点指针所指结点的数据即可,这里需要使用引用返回,因为解引用后可能需要对数据进行修改, T2 operator*(){return _it-_date;}
-返回当前迭代器结点的指针所指结点的数据的地址 T2* operator-(){return _it-_date;}
使用场景 list 的insert
insert函数可以在所给迭代器pos之前插入一个新结点,
1.先根据所给迭代器pos得到该位置处的结点指针
2.然后通过该指针找到前一个位置的结点指针last
根据所给数据x构造一个新结点 iterator insert(iterator pos,const T x){node* newnode new node(x);node* next pos._node;node* last next-_prev;last-_next newnode;newnode-_prev last;newnode-_next next;next-_prev newnode;return iterator(newnode);}
list的erase
erase函数可以删除所给迭代器位置的结点,
注意**:pos不可以是哨兵位的迭代器,即不能删除哨兵位 pos迭代器结点中的指针不能为空**
1.根据所给迭代器得到该位置处的结点指针self
2.通过self指针找到前一个位置的结点指针last,以及后一个位置的结点指针next
3.紧接着释放cur结点,最后prev和next结点进行链接 iterator erase(iterator pos){assert(pos._node);assert(_head ! _head-_next);node* self pos._node;node* next self-_next;node* last self-_prev;last-_next next;next-_prev last;delete[] self;return iterator(next);}
关于insert 和 erase 迭代器失效的问题
insert不会导致迭代器失效,因为pos迭代器中的节点指针仍然指向原来的节点。
问:erase之后, pos迭代器是否失效 一定失效,因为此时pos迭代器中的节点指针指向的节点已经被释放了,该指针相当于是野指针。 最后所有代码如下
namespace bit
{templateclass Tstruct ListNode{ListNodeT* _next;ListNodeT* _prev;T _date;ListNode(const T pos T()){_next nullptr;_prev nullptr;_date pos;}};templateclass T1,class T2 T1struct ListIterator{typedef ListIteratorT1,T2 iterator;typedef ListNodeT1 node;node* _node;ListIterator(node* pos){_node pos;}T2 operator*(){return _node-_date;}iterator operator(){_node _node-_next;return *this;} iterator operator(int){iterator tmp(_node);_node _node-_next;return tmp;}iterator operator--(){_node _node-_prev;return *this;}iterator operator--(int){iterator tmp(_node);_node _node-_prev;return tmp;}T2* operator-(){return _node-_date;}bool operator!(const iterator pos){return _node ! pos._node;}bool operator(const iterator pos){return _node pos._node;}};templateclass T1, class T2struct Reverse_iterator{typedef Reverse_iteratorT1, T2 self;typedef ListNodeT1 node;node* _it;Reverse_iterator(node* pos){_it pos;}self operator(){_it _it-_prev;return *this;}self operator(int){self tmp(_it);_it _it-_prev;return tmp;}self operator--(){_it _it-_next;return *this;}self operator--(int){self tmp(_it);_it _it-_next;return tmp;}T2 operator*(){return _it-_date;}T2* operator-(){return _it-_date;}bool operator!(const self pos){return _it ! pos._it;}bool operator(const self pos){return _it pos._it;}};templateclass Tclass list{public:typedef Reverse_iteratorT, T reverse_iterator;typedef Reverse_iteratorT, const T const_reverse_iterator;typedef ListNodeT node;typedef ListIteratorT iterator;typedef ListIteratorT,const T const_iterator;list():_head(new node){_head-_next _head;_head-_prev _head;}list(const list pos){_head new node;_head-_next _head;_head-_prev _head;for (auto e : pos){push_back(e);}}list(initializer_listT il){_head new node;_head-_next _head;_head-_prev _head;for (auto e : il){push_back(e);}}void push_back(const T x){node* head _head;node* tail _head-_prev;node* p new node(x);tail-_next p;p-_prev tail;p-_next head;head-_prev p;}void pop_back(){assert(_head ! _head-_next);node* head _head;node* tail head-_prev;node* newtail tail-_prev;newtail-_next head;head-_prev newtail;delete[] tail;}reverse_iterator rbegin(){return reverse_iterator(_head-_prev);}reverse_iterator rend(){return reverse_iterator(_head);}const_reverse_iterator crbegin()const{return const_reverse_iterator(_head-_prev);}const_reverse_iterator crend()const{return const_reverse_iterator(_head);}iterator begin(){return iterator(_head-_next);}const_iterator begin()const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end()const{return const_iterator(_head);}void push_front(const T x){node* newnode new node(x);node* head _head;node* tail _head-_next;head-_next newnode;newnode-_prev head;newnode-_next tail;tail-_prev newnode;}void pop_front(){assert(_head ! _head-_next);node* head _head;node* tail _head-_next;head-_next tail-_next;tail-_next-_prev head;delete[]tail;}iterator insert(iterator pos,const T x){node* newnode new node(x);node* next pos._node;node* last next-_prev;last-_next newnode;newnode-_prev last;newnode-_next next;next-_prev newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos._node);assert(_head ! _head-_next);node* self pos._node;node* next self-_next;node* last self-_prev;last-_next next;next-_prev last;delete[] self;return iterator(next);}~list(){iterator it1 begin();while (it1 ! end()){it1 erase(it1);}delete _head;_head nullptr;}private:node* _head;};
