list 的实现

目录

list

结点类

结点类的构造函数

list的尾插尾删

list的头插头删

迭代器

++运算符重载

--运算符重载

==和!= 运算符重载

* 和 -> 运算符重载

 list 的insert

list的erase

---

list

list实际上是一个带头双向循环链表,要实现list,则首先需要实现一个结点类,而一个结点需要存储的信息为:数据、前驱指针、后继指针

而对于该结点类的成员函数来说,我们只需实现一个构造函数即可,因为该结点类只需要根据数据来构造一个结点即可,而结点的释放则由list的析构函数来完成,

结点类

结点类的基本结构：

	template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _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的尾插尾删

	template<class T>class list{public:typedef ListNode<T> 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的头插头删

	template<class T>class list{public:	typedef ListNode<T> 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;};

迭代器

迭代器有两种实现方式,具体应根据容器底层数据结构实现：

1. 原生态指针,比如：vector和string ->物理空间是连续的，因为string和vector对象都将其数据存储在了一块连续的内存空间,我们通过指针进行自增、自减以及解引用等操作,就可以对相应位置的数据进行一系列操作,因此string和vector当中的迭代器就是原生指针。
2. .将原生态指针进行封装,因迭代器使用形式与指针完全相同,因此在自定义的类中必须实现以下方法：

指针可以解引用,迭代器的类中必须重载operator*()
指针可以通过->访问其所指空间成员,迭代器类中必须重载oprator->()
指针可以++向后移动,迭代器类中必须重载operator++()与operator++(int)
至于operator--()/operator--(int) 是否需要重载,根据具体的结构来抉择,双向链表可
以向前 移动,所以需要重载,如果是forward_list就不需要重载–
迭代器需要进行是否相等的比较,因此还需要重载operator==()与operator!=()
但是对于list来说,其各个结点在内存当中的位置是随机的,并不是连续的,我们不能仅通过结点指针的自增、自减以及解引用等操作对相应结点的数据进行操作,

总结：list的迭代器 实际上就是对结点指针进行了封装,对其各种运算符进行了重载,使得结点指针的各种行为看起来和普通指针一样,（例如,对结点指针自增就能指向下一个结点 p = p->next）

	template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> 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
{template<class T>struct ListNode{ListNode<T>* _next;ListNode<T>* _prev;T _date;ListNode(const T& pos = T()){_next = nullptr;_prev = nullptr;_date = pos;}};template<class T1,class T2 = T1>struct ListIterator{typedef ListIterator<T1,T2> iterator;typedef ListNode<T1> 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;}};template<class T1, class T2>struct Reverse_iterator{typedef Reverse_iterator<T1, T2> self;typedef ListNode<T1> 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;}};template<class T>class list{public:typedef Reverse_iterator<T, T> reverse_iterator;typedef Reverse_iterator<T, const T> const_reverse_iterator;typedef ListNode<T> node;typedef ListIterator<T> iterator;typedef ListIterator<T,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_list<T> 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;};