list 简单模拟实现

 

目录

1. list的节点

2. 迭代器实现

(1). 主体与构造函数

(2). 解引用运算符与成员访问运算符重载

(3). 迭代器的自增自减与判断是否相等

(4). const迭代器

(5). 模板实现复用

3. lsit主体

(1). 构造、析构函数与成员变量

(2). begin 与 end

(3). 返回元素个数与判空

(4). 插入删除操作

(5). 交换函数

(6). 赋值重载

4. 整体代码

---

list的底层是用双向链表实现的

1. list的节点

由于要存储多个值所以我们使用一个模板类来实现(就像C语言中用结构体一样)

	template<typename T>class Node{public:Node(const T& v=T()):val(v),next(nullptr),qrev(nullptr){}T val;Node* next;Node* qrev;};

(此处也可以直接用struct，因为这个类成员变量是都可以访问的)

这个类中存储节点的值，下一个节点的地址与上一个节点的地址

2. 迭代器实现

我们将节点与自身通过typedef进行重命名，重命名时不要忘记将类名后的<类型>加上

(1). 主体与构造函数

	template<typename T>class listiterator{public:Node* p;typedef Node<T> Node;typedef listiterator<T> Self;listiterator(Node* tmp = nullptr){p = tmp;}listiterator(const Self& it){p = it.p;}};

实现了拷贝构造与默认构造函数，成员变量p存储节点的地址

(2). 解引用运算符与成员访问运算符重载

		T& operator* (){return p->val;}T* operator->()//如果存储的是一个类，迭代器打印会用到{return &p->val;}

第一个会返回值的引用，第二个会返回值的地址，所以存储类的话可以通过这个来访问类的成员

(3). 迭代器的自增自减与判断是否相等

		Self& operator++(){p = p->next;return *this;}Self operator++(int){Self tmp(*this);p = p->next;return tmp;}Self& operator--(){p = p->qrev;return *this;}Self operator--(int){Self tmp(*this);p = p->qrev;return tmp;}bool operator!=(const Self& it){return p != it.p;}bool operator==(const Self& it){return p == it.p;}

注意后置的++与--不可以返回引用因为我们是用一个临时的对象记录下来原来的值

(4). const迭代器

实现代码如下

	template<typename T>class constlistiterator{public:Node* p;typedef Node<T> Node;typedef constlistiterator<T> Self;constlistiterator(Node* tmp = nullptr){p = tmp;}constlistiterator(const Self& it){p = it.p;}const T& operator* ()//{return p->val;}//const T* operator->()//如果存储的是一个类，迭代器打印会用到{return &p->val;}Self& operator++(){p = p->next;return *this;}Self operator++(int){Self tmp(*this);p = p->next;return tmp;}Self& operator--(){p = p->qrev;return *this;}Self operator--(int){Self tmp(*this);p = p->qrev;return tmp;}bool operator!=(const Self& it) const{return p != it.p;}bool operator==(const Self& it) const{return p == it.p;}};

我们发现const的实现与普通迭代器的实现基本相同就是多了一些const限定符

于是我们可以考虑用模板解决这一问题

(5). 模板实现复用

我们可以从两个类的成员函数不同的返回值入手将不同的返回值变为模板其他参数

R来代表T&，L来代表T*

	template<typename T, typename R, typename L>class listiterator{public:typedef Node<T> Node;typedef listiterator<T, R, L> Self;Node* p;listiterator(Node* tmp=nullptr){p = tmp;}listiterator(const Self& it){p = it.p;}R operator* ()//R代表T&{return p->val;}//L代表T*L operator->()//如果存储的是一个类，迭代器打印会用到{return &p->val;}Self& operator++(){p = p->next;return *this;}Self operator++(int){Self tmp(*this);p = p->next;return tmp;}Self& operator--(){p = p->qrev;return *this;}Self operator--(int){Self tmp(*this);p = p->qrev;return tmp;}bool operator!=(const Self& s) const{return p != s.p;}bool operator==(const Self& s) const{return p == s.p;}};

3. lsit主体

(1). 构造、析构函数与成员变量

template<typename T>
class list
{
public:typedef Node<T> Node;//typedef Node<T>* pNode;//typedef listiterator<T> iterator;//typedef constlistiterator<T> const_iterator;typedef listiterator<T,T&,T*> iterator;typedef listiterator<T, const T&, const T*> const_iterator;void InitCode(){	head = new Node;head->next = head;head->qrev = head;_size = 0;}list(){InitCode();}list(const list<T>& l){InitCode();for (auto& t : l){push_back(t);}}list(initializer_list <T> il){InitCode();for (auto& t : il){push_back(t);}}~list(){Node* tmp = head;Node* next = head->next;size_t t = size();for(size_t i=0;i<=t;i++){delete tmp;tmp = next;next = next->next;}}list<T>& operator=(list<T> l){swap(l);return *this;}
private:Node* head;size_t _size;
};

head为哨兵位，我们分别实现了，无参默认构造，拷贝构造函数

还有list(initializer_list <T> il)

能够接受一个由花括号 {} 包围的初始化列表作为参数

是列表支持以下初始化

		 //直接构造list<int> lt0({ 1,2,3,4,5,6 });// 隐式类型转换list<int> lt1 = { 1,2,3,4,5,6,7,8 };const list<int>& lt3 = { 1,2,3,4,5,6,7,8 };auto il1 = { 10, 20, 30 };

(2). begin 与 end

我们上面的代码根据模板参数将迭代器分别重名为iterator和const_iterator

		iterator begin(){return head->next;}iterator end(){return head;}const_iterator begin() const{return head->next;}const_iterator end() const{return head;}

(3). 返回元素个数与判空

		size_t size() const{//Node* cur = head->next;//size_t s = 0;//while (cur != head)//{//	cur = cur->next;//	s++;//}return _size;}bool empty() const{return _size == 0;}

我们用一个成员记录链表节点个数，这样就方便许多

(4). 插入删除操作

		void push_back(const T& val){Node* qrev = head->qrev;Node* newNode = new Node;newNode->val = val;_size++;qrev->next = newNode;newNode->next = head;newNode->qrev = qrev;head->qrev = newNode;}void pop_back(){if (head->qrev != head){Node* qrev = head->qrev->qrev;Node* era = head->qrev;_size--;qrev->next = head;head->qrev = qrev;delete era;}}void push_front(const T& val){Node* next = head->next;Node* newnode = new Node;newnode->val = val;_size++;head->next = newnode;next->qrev = newnode;newnode->next = next;newnode->qrev = head;}void pop_front(){if (head->next != head){Node* next = head->next->next;Node* era = head->next;_size--;next->qrev = head;head->next = next;delete era;}}iterator insert(iterator pos,const T& val){Node* qrev = pos.p->qrev;Node* newnode = new Node(val);_size++;pos.p->qrev = newnode;newnode->next = pos.p;newnode->qrev = qrev;qrev->next = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* qrev = pos.p->qrev;Node* next = pos.p->next;qrev->next = next;next->qrev = qrev;delete pos.p;_size--;return next;}void clear(){Node* cur = head->next;Node* next = cur->next;while (cur != head){delete cur;cur = next;next = next->next;}//auto it = begin();//while (it != end())//{//	it = erase(it);//}}

清空元素注意不要把哨兵位给释放了，不然再push节点就会出现问题

(5). 交换函数

		void swap(list<T>& l){std::swap(this->head, l.head);std::swap(this->_size, l._size);}

相比std标准库里更加高效，直接就是头指针(哨兵位)互相交换，与元素个数互相交换()

(6). 赋值重载

我们实现了交换函数就可以顺便实现赋值重载

		list<T>& operator=(list<T> l){swap(l);return *this;}

将自己与临时对象交换，临时对象出函数时就销毁

4. 整体代码

#include<iostream>
#include<assert.h>
using namespace std;
namespace Pc
{template<typename T>class Node{public:Node(const T& v=T()):val(v),next(nullptr),qrev(nullptr){}T val;Node* next;Node* qrev;};template<typename T, typename R, typename L>class listiterator{public:typedef Node<T> Node;typedef listiterator<T, R, L> Self;Node* p;listiterator(Node* tmp=nullptr){p = tmp;}listiterator(const Self& it){p = it.p;}R operator* ()//R代表T&{return p->val;}//L代表T*L operator->()//如果存储的是一个类，迭代器打印会用到{return &p->val;}Self& operator++(){p = p->next;return *this;}Self operator++(int){Self tmp(*this);p = p->next;return tmp;}Self& operator--(){p = p->qrev;return *this;}Self operator--(int){Self tmp(*this);p = p->qrev;return tmp;}bool operator!=(const Self& s) const{return p != s.p;}bool operator==(const Self& s) const{return p == s.p;}};template<typename T>class list{public:typedef Node<T> Node;//typedef Node<T>* pNode;//typedef listiterator<T> iterator;//typedef constlistiterator<T> const_iterator;typedef listiterator<T,T&,T*> iterator;typedef listiterator<T, const T&, const T*> const_iterator;void InitCode(){	head = new Node;head->next = head;head->qrev = head;_size = 0;}list(){InitCode();}list(const list<T>& l){InitCode();for (auto& t : l){push_back(t);}}list(initializer_list <T> il){InitCode();for (auto& t : il){push_back(t);}}~list(){Node* tmp = head;Node* next = head->next;size_t t = size();for(size_t i=0;i<=t;i++){delete tmp;tmp = next;next = next->next;}}list<T>& operator=(list<T> l){swap(l);return *this;}iterator begin(){return head->next;}iterator end(){return head;}const_iterator begin() const{return head->next;}const_iterator end() const{return head;}size_t size() const{//Node* cur = head->next;//size_t s = 0;//while (cur != head)//{//	cur = cur->next;//	s++;//}return _size;}bool empty() const{return _size == 0;}void push_back(const T& val){Node* qrev = head->qrev;Node* newNode = new Node;newNode->val = val;_size++;qrev->next = newNode;newNode->next = head;newNode->qrev = qrev;head->qrev = newNode;}void pop_back(){if (head->qrev != head){Node* qrev = head->qrev->qrev;Node* era = head->qrev;_size--;qrev->next = head;head->qrev = qrev;delete era;}}void push_front(const T& val){Node* next = head->next;Node* newnode = new Node;newnode->val = val;_size++;head->next = newnode;next->qrev = newnode;newnode->next = next;newnode->qrev = head;}void pop_front(){if (head->next != head){Node* next = head->next->next;Node* era = head->next;_size--;next->qrev = head;head->next = next;delete era;}}iterator insert(iterator pos,const T& val){Node* qrev = pos.p->qrev;Node* newnode = new Node(val);_size++;pos.p->qrev = newnode;newnode->next = pos.p;newnode->qrev = qrev;qrev->next = newnode;return newnode;}iterator erase(iterator pos){assert(pos != end());Node* qrev = pos.p->qrev;Node* next = pos.p->next;qrev->next = next;next->qrev = qrev;delete pos.p;_size--;return next;}void clear(){Node* cur = head->next;Node* next = cur->next;while (cur != head){delete cur;cur = next;next = next->next;}//auto it = begin();//while (it != end())//{//	it = erase(it);//}}void swap(list<T>& l){std::swap(this->head, l.head);std::swap(this->_size, l._size);}private:Node* head;size_t _size;};

---

这篇就到这里啦

(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤