模拟实现c++中的list模版

                ☺☺☺☺☺☺☺☺☺☺  点击 进入杀马特的主页☺☺​​​​​​​☺​​​​​​​☺​​​​​​​☺​​​​​​​☺​​​​​​​☺​​​​​​​☺​​​​​​​☺​​​​​​​☺

目录

一·list简述：

二·库内常用接口函数使用：

1·reverse():

 2.sort():

 3.merge():

 4.unique():

5.splice():

三·list的模拟实现相关函数接口：

1.创建头结点和无参构造：

2·有参构造： 

3·拷贝构造：

4·赋值重载的现代版本实现：

5.析构函数：

6·list的迭代器类模版内接口函数的实现：

7.insert的接口函数的实现：

8.push_back和push_front的实现：

9·erase的接口函数的实现：

10·pop_front和pop_back的实现：

11·size和empty的实现： 

 12·front和back的实现：

13·不同容器利用迭代器打印数据：

 

---

一·list简述：

即相当于一个放入任意类型的一个容器，底层就是链表。即是与vector的区别。

二·库内常用接口函数使用：

这里简单介绍一下除了下面要实现的接口函数还有些其他接口函数：

1·reverse():

对于以前的vector和string，它们用的是算法库里的，故括号里还要传迭代器区间，而list库自己实现了，可以不传参：

list<int> lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);lt.reverse();
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {cout << *it << " ";it++;
}

 2.sort():

对于list库里的sort（）是默认升序。

list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list<int>::iterator itt = ltt.begin();
while (itt != ltt.end()) {cout << *itt << " ";itt++;
}

当然也可以也可以这样完成升降序：

 

 

同理，这里其实也可以不创建对象，直接匿名对象也可以。

 3.merge():

即把两个list对象按升序拼接起来（前提是两个对象都是有序的，不是的话要提前给它sort一下），最后拼到前者对象，后者对象清空，如：

list<int> lt;
lt.emplace_back(1);
lt.emplace_back(2);
lt.emplace_back(3);
lt.emplace_back(4);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
ltt.sort();
list<int>::iterator it = lt.begin();
lt.merge(ltt);
it = lt.begin();
while (it != lt.end()) {cout << *it << " ";it++;
}
cout << endl;

 4.unique():

去重复操作，但是要求list对象要有序：

///去重操作：
list<int> lt;
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(1);
lt.emplace_back(2);
lt.unique();
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {cout << *it << "";it++;
}
cout << endl;

5·remove():

删除链表中值为val的节点：

//删除指定元素，只删除找到一个即可：
list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
lt.remove(2);
list<int>::iterator it = lt.begin();
it = lt.begin();
while (it != lt.end()) {cout << *it << "";it++;
}

5.splice():

本意是粘连的意思，可以给某个位置前面粘连一个对象的链表也可以给某个位置前粘连任意一个对象的迭代器区间：

一个对象给另一个对象粘：

list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt);
it = lt.begin();
while (it != lt.end()) {cout << *it << " ";it++;
}

给pos位置前粘一个迭代器区间：

list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(it, lt, ++lt.begin(), lt.end());
it = lt.begin();//这里会把242转移粘在5的前面，故要重新给begin赋值
while (it != lt.end()) {cout << *it << " ";it++;}

 

粘连别人的迭代器区间：

list<int> lt;
lt.emplace_back(5);
lt.emplace_back(2);
lt.emplace_back(4);
lt.emplace_back(2);
list<int> ltt;
ltt.emplace_back(5);
ltt.emplace_back(3);
ltt.emplace_back(7);
ltt.emplace_back(10);
list<int>::iterator it = lt.begin();
lt.splice(++lt.begin(), ltt, ++ltt.begin(), ltt.end());
it = lt.begin();
while (it != lt.end()) {cout << *it << " ";it++;}

 

 

三·list的模拟实现相关函数接口：

框架构造：list是吧每个节点连接起来，故首先把节点封装成一个类，接着由于迭代器相当于节点指针，即双向迭代器，只能是++或者--无-，+即还要对迭代器去遍历链表，可以把迭代器封装也成一个类。如：

节点类：

namespace li {template<class T>struct list_node {list_node* _pre;list_node* _next;T _val;list_node(const T _val = T()):_val(_val), _pre(nullptr), _next(nullptr) { }};

迭代器 类：

template<class T,class ref,class ptr >struct list_iterator {typedef list_node<T> Node;Node* _node;list_iterator( Node* node):_node(node){}
};

它们没有资源产生和释放，故只用写所需要的构造函数即可。 

这里的template<class T,class ref,class ptr >是为了少写一次const迭代器的类，而多加了对原来的类的模版参数可以实例化出const和普通的迭代器类。

list框架：

template<class T>class list {public:typedef list_node<T> Node;typedef list_iterator<T,  T&,  T*> iterator;typedef  list_iterator<T,const T&,const T*> const_iterator;
private:Node* _head;int _size;};

1.创建头结点和无参构造：

void empty_init(){_head = new Node;_head->_next = _head;_head->_pre = _head;_size = 0;}list() {empty_init();}

由于后面等有参构造list的时候也是需要构造出头结点，故可以把它封装成一个empty_init函数。 

2·有参构造： 

list( initializer_list<T> m)//这个模版化出的m对象可以想象成一个数组{empty_init();for (auto& e : m){push_back(e);}}

initializer_list<int> il = { 10, 20, 30 };li::list<int> llt(il);//拷贝构造：li::list<int>lt1({ 1,22,223 });//先是隐式类型转换生成的临时对象再拷贝构造给lt1//隐式类型转换：const li::list<int>&lt2={ 1,22,223 };//直接隐式类型转换生成临时对象，由于是给临时对象引用（起别名）故临时对象只能读不能写，故用const

这里可以用 initializer_list这个模版来进行{}的初始化。

3·拷贝构造：

list(const list<T>& lt){empty_init();//创建链表的头结点for (auto& e : lt){push_back(e);}}

4·赋值重载的现代版本实现：

void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt；{swap(lt);return *this;}

5.析构函数：

void clear(){auto it = begin();while (it != end()){it = erase(it);}}//利用迭代器遍历链表删除各个节点~list() {clear();delete _head;_head = nullptr;}

6·list的迭代器类模版内接口函数的实现：

ref operator*() {return _node->_val;}ptr operator->() {return &(_node->_val) ;}list_iterator<T,ref, ptr> &operator++(int) {list_iterator<T,ref,ptr> tmp = *this;++*this;return tmp;}list_iterator<T,ref, ptr>&operator--(int) {list_iterator<T,ref,ptr> tmp = *this;--*this;return tmp;}list_iterator<T,ref, ptr>& operator++(){_node = _node->_next;return *this;}list_iterator<T,ref, ptr>& operator--(){_node = _node->_pre;return *this;}bool operator!=(const  list_iterator<T,ref,ptr>& s) const{return _node != s._node;}bool operator==(const  list_iterator<T,ref,ptr>& s) const{return _node == s._node;}

这里需要说的也就是里面对->的重载运算符函数的实现，这样返回节点内数据的地址作用在哪？

其实是为了：如果这里面的val放的自定义类型如：

 

 

struct AA {int a1 = 1;int a2 = 2;
};

这时候这个操作就可以直接访问到val里的a1，a2，而不用再有通过AA的对象再去访问a1和a2。

li::list<AA> at;at.push_back(AA());at.push_back(AA());at.push_back(AA());at.push_back(AA());li::list<AA>::iterator ait = at.begin();cout << (ait-> a1 )<<" ";//如果是自定义类型则迭代器（也就是节点的指针）可以直接访问到此自定义类型的变量。//如果没有这个重载：cout << ((ait._node)->_val.a1 )<< " ";//重载后把两个->省略成一个cout << (ait.operator->()->a1) << " ";

7·begin（）和end（）的实现：

这里是list直接访问的，故放在list类模版的函数里。

iterator begin() {return _head->_next;//隐式类型转换，直接传递对应类的构造参数}iterator end() {return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const//对应的迭代器实例化出的普通和const类型{return _head;}

7.insert的接口函数的实现：

iterator  insert(iterator pos, const T& x) {//在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针Node* pre = pos._node->_pre ;Node* cur = pos._node;Node* pnode = new Node(x);pnode->_next = cur;cur->_pre = pnode;pre->_next = pnode;pnode->_pre = pre;_size++;return pnode;}

这里其实和vector的迭代器不一样，这里插入不会导致迭代器失效，因为它所指向的对象并没有改变，而只是在它前面插入新节点。 

8.push_back和push_front的实现：

void push_back(const T& x) {insert(end(), x);}void push_front(const T& x) {insert(begin(), x);}

9·erase的接口函数的实现：

这里如果删除了就会导致迭代器失效，故要利用返回值接收再次使用。

iterator erase(iterator pos) {assert(pos != end());Node* pre = pos._node->_pre;Node* next = pos._node->_next;delete pos._node ;pre->_next = next;next->_pre = pre;_size--;return next;}

10·pop_front和pop_back的实现：

void pop_front() {erase(begin());}void pop_back() {erase(--end());}

11·size和empty的实现： 

size_t size() const{return _size;}bool empty() const{return _size == 0;}

 12·front和back的实现：

T& front() {return begin()._node->_val;}const T& front()const {return begin()._node->_val;}T& back() {return (--end())._node->_val;}const T& back()const {return --end()._node->_val;}//分别是拿到val可修改与不可修改

13·不同容器利用迭代器打印数据：

//不同容器的打印
template<class Container>
void  con_print(const Container & con) {typename Container::const_iterator it = con.begin();//告诉未实例化的模版是类型//auto it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}

14.list实现代码汇总：

#include<iostream>
#include<string>
#include<assert.h>
using namespace std;
namespace li {template<class T>struct list_node {list_node* _pre;list_node* _next;T _val;list_node(const T _val = T()):_val(_val), _pre(nullptr), _next(nullptr) { }};template<class T,class ref,class ptr >struct list_iterator {typedef list_node<T> Node;Node* _node;list_iterator( Node* node):_node(node){}ref operator*() {return _node->_val;}ptr operator->() {return &(_node->_val) ;}list_iterator<T,ref, ptr> &operator++(int) {list_iterator<T,ref,ptr> tmp = *this;++*this;return tmp;}list_iterator<T,ref, ptr>&operator--(int) {list_iterator<T,ref,ptr> tmp = *this;--*this;return tmp;}list_iterator<T,ref, ptr>& operator++(){_node = _node->_next;return *this;}list_iterator<T,ref, ptr>& operator--(){_node = _node->_pre;return *this;}bool operator!=(const  list_iterator<T,ref,ptr>& s) const{return _node != s._node;}bool operator==(const  list_iterator<T,ref,ptr>& s) const{return _node == s._node;}};template<class T>class list {public:typedef list_node<T> Node;typedef list_iterator<T,  T&,  T*> iterator;typedef  list_iterator<T,const T&,const T*> const_iterator;void empty_init(){_head = new Node;_head->_next = _head;_head->_pre = _head;_size = 0;}list() {empty_init();}list( initializer_list<T> m)//这个模版化出的m对象可以想象成一个数组{empty_init();for (auto& e : m){push_back(e);}}list(const list<T>& lt){empty_init();for (auto& e : lt){push_back(e);}}void swap(list<T>& lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list<T>& operator=(list<T> lt)//不是引用传参故不会改变lt：{swap(lt);return *this;}void clear(){auto it = begin();while (it != end()){it = erase(it);}}~list() {clear();delete _head;_head = nullptr;}iterator begin() {return _head->_next;//隐式类型转换，直接传递对应类的构造参数}iterator end() {return _head;}const_iterator begin() const{return _head->_next;}const_iterator end() const{return _head;}iterator  insert(iterator pos, const T& x) {//在pos和pos前的位置插入数据，故先保存这两个位置。以防后面找不到，然后在连接指针Node* pre = pos._node->_pre ;Node* cur = pos._node;Node* pnode = new Node(x);pnode->_next = cur;cur->_pre = pnode;pre->_next = pnode;pnode->_pre = pre;_size++;return pnode;}void push_back(const T& x) {insert(end(), x);}void push_front(const T& x) {insert(begin(), x);}iterator erase(iterator pos) {assert(pos != end());Node* pre = pos._node->_pre;Node* next = pos._node->_next;delete pos._node ;pre->_next = next;next->_pre = pre;_size--;return next;}void pop_front() {erase(begin());}void pop_back() {erase(--end());}size_t size() const{return _size;}bool empty() const{return _size == 0;}// List AccessT& front() {return begin()._node->_val;}const T& front()const {return begin()._node->_val;}T& back() {return (--end())._node->_val;}const T& back()const {return --end()._node->_val;}private:Node* _head;int _size;};
}//不同容器的打印
template<class Container>
void  con_print(const Container & con) {typename Container::const_iterator it = con.begin();//auto it = con.begin();while (it != con.end()){cout << *it << " ";++it;}cout << endl;}