Lesson10—list

第10章 c++的list的使用和实现

---

---

前言

这篇博客写了怎么使用list和怎么实现

---

list和前面的string 和vector 的有很多重复的就不过多赘述

一、list的初始化

vector的底层是数组，list的底层是结构体，所以list不能用下标的方式去访问，因为这样会让效率变的特别低

可以直接用花括号去初始化这样就不要一个个尾插，vector和list都可以

二、list的遍历

1.迭代器

vector的底层是数组，在内存上是连续的但是链表不是，但这里链表依旧可以使用迭代器来遍历，非常的强大

既然可以用迭代器去访问一个在内存上不连续的list那能不能给这个链表用sort排序呢？
答案是不能，因为这样排序效率特别低，如果想要去排序链表，list提供了sort函数

2.范围for

---

有很多和vector重复了就不重复写了感兴趣的可以看我的vector篇

三、list常用的内置函数

1.sort（慎用）

默认是升序加上仿函数是降序

list的排序底层用的不是快排用的是归并排序，如果数据很多又要排序就不要用list用vector

list排序时间是vector的三倍左右，而且特别稳定基本都是三倍左右，虽然归并排序和快排都是nlogn但是list排序还是罗逊vector

甚至把list里面的数据拷贝给vector让vector用快排排序，把排序好的数据在拷贝回来这样会都比list的sort的归并排序快简直拉跨

2.unique

unique的作用是去重但数据必须是排序以后或者连续的

不排序或者不连续就会这样去不干净

3.reverse

逆置这个链表，比较简单

4.merge

合并链表，这里必须是要有序的

5.splice

这个函数差不多就是剪切的意思，第一个参数要迭代器，第二个参数是链表

从迭代器的位置插入一整个链表

还可以这样用

四、模拟实现

模板不建议声明和定义分开会有各种问题，建议直接把定义写在.h文件里面

1.基本框架

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;
};template<class T>
class my_list
{
public:typedef ListNode<T> Node;
private:Node* _head;
};

先把基本的框架写好来

2.构造函数

3.push_back

这里可以画个草图理解，要尾插就要先找尾巴

void push_back(const T& x)
{Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;
}

运行以后会这个错误

编译器给的是这个错误，这是因为，new Node 会去调用 node默认构造函数但是这里没有写

struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr),_prve(nullptr),_data(data){}
};

4. 遍历

链表在逻辑上是连在一起的但是它在物理上就不一定是连续的了是所用它不能想vector一样的用++去遍历vector底层是数组
这里我采用迭代器的方式去遍历，因为指针++需要像数组那样在物理上连续才可以所以这里采用封装然后运算符重载去实现

class ListIterator
{
public:typedef ListNode<T> Node;typedef ListIterator<T> self;Node* _node;ListIterator(Node* node):_node(node){}self& operator++( ){_node = _node->_next;return *this;}T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}
};

这样就可以遍历了，也支持范围for

5.const迭代器

如果有人这样去访问迭代器就会把回来的值改变不安全，有时候还会在不经意间改变原来的值


这里还需要重载一个const迭代器，只能去访问但是不能修改里面的值

template<class T>
class ListConstIterator{
public:typedef ListNode<T> Node;typedef ListConstIterator<T> self;ListConstIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}const T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};

这里只需要复制一份原来的迭代器改下名字就行，然后重载一下

然后加上const就可以了然后再去my_list里面加上就行

加上const迭代器的begin和end


这里就不让改了

6.代码

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr),_prve(nullptr),_data(data){}
};
template<class T>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
template<class T>
class ListConstIterator{
public:typedef ListNode<T> Node;typedef ListConstIterator<T> self;ListConstIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}const T& operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T> iterator;typedef ListConstIterator<T> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const {return const_iterator(_head->_next);}const_iterator end()const {return const_iterator(_head);}my_list(){_head = new Node;_head->_next = _head;_head->_prve = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;}private:Node* _head;
};

7.const迭代器改进

上面const迭代器有一个问题，就是只要解引用那一点点不一样甚至只是返回值加了const代码就边长了那么多这里还可以在优化一下

#pragma once
#include<iostream>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr), _prve(nullptr), _data(data){}
};
template<class T,class Ref>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T,Ref> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}Ref operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T,T&> iterator;typedef ListIterator<T,const T&> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}my_list(){_head = new Node;_head->_next = _head;_head->_prve = _head;}void push_back(const T& x){Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;}private:Node* _head;
};

8.insert

可以画个草图方便理解

iterator insert(iterator pos ,const T& x)
{Node* newnode = new Node(x);Node* cur = pos._node;newnode->_prve = cur->_prve;cur->_prve->_next = newnode;newnode->_next = cur;cur->_prve = newnode;return iterator(newnode);
}

9.erase

iterator erase(iterator pos)
{Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;prve->_next = next;next->_prve = prve;delete cur;return iterator(next);
}

10. pop_back

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

11. push_front

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

12.pop_front

void pop_front()
{erase(begin());
}

13.clear

void clear()
{auto it = begin();while (it !=end()){it=erase(it);}
}

14.析构函数

~my_list()
{clear();delete _head;_head = nullptr;
}

15.拷贝构造

my_list(const my_list<T>& lt)
{_head = new Node;_head->_next = _head;_head->_prve = _head;for (const auto& e : lt){push_back(e);}
}

16.赋值

my_list<T>& operator = (my_list<T> lt)
{swap(lt._head, _head);return *this;
}

17.initializer

my_list(initializer_list<T> il)
{_head = new Node;_head->_next = _head;_head->_prve = _head;for (auto e : il){push_back(e);}
}

五.完整代码

#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct ListNode
{ListNode<T>* _next;ListNode<T>* _prve;T _data;ListNode(const T& data = T()):_next(nullptr), _prve(nullptr), _data(data){}
};
template<class T, class Ref>
class ListIterator{
public:typedef ListNode<T> Node;typedef ListIterator<T, Ref> self;ListIterator(Node* node):_node(node){}Node* _node;self& operator++(){_node = _node->_next;return *this;}self& operator--(){_node = _node->_prve;return *this;}self operator++(int){self tmp(*this);_node = _node->_next;return tmp;}self operator--(int){self tmp(*this);_node = _node->_prve;return tmp;}Ref operator*(){return _node->_data;}bool operator !=(const self& it){return _node != it._node;}bool operator ==(const self& it){return _node == it._node;}
};
//template<class T>
//class ListConstIterator
//
//{
//public:
//
//	typedef ListNode<T> Node;
//	typedef ListConstIterator<T> self;
//	ListConstIterator(Node* node)
//		:_node(node)
//	{
//
//	}
//	Node* _node;
//	self& operator++()
//	{
//		_node = _node->_next;
//		return *this;
//	}
//	self& operator--()
//	{
//		_node = _node->_prve;
//		return *this;
//	}
//	self operator++(int)
//	{
//		self tmp(*this);
//		_node = _node->_next;
//		return tmp;
//	}
//	self operator--(int)
//	{
//		self tmp(*this);
//		_node = _node->_prve;
//		return tmp;
//	}
//	const T& operator*()
//	{
//		return _node->_data;
//	}
//	bool operator !=(const self& it)
//	{
//		return _node != it._node;
//	}
//	bool operator ==(const self& it)
//	{
//		return _node == it._node;
//	}
//};template<class T>
class my_list
{
public:typedef ListNode<T> Node;typedef ListIterator<T, T&> iterator;typedef ListIterator<T, const T&> const_iterator;iterator begin(){return iterator(_head->_next);}iterator end(){return iterator(_head);}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return const_iterator(_head);}void empty(){_head = new Node;_head->_next = _head;_head->_prve = _head;}my_list(){empty();}//lt2(lt1)my_list(initializer_list<T> il){empty();for (auto e : il){push_back(e);}}my_list(const my_list<T>& lt){empty();for (const auto& e : lt){push_back(e);}}~my_list(){clear();delete _head;_head = nullptr;}//lt3 = lt1my_list<T>& operator = (my_list<T> lt){swap(lt._head, _head);return *this;}void push_back(const T& x){/*Node* newnode = new Node(x);Node* tail = _head->_prve;tail->_next = newnode;newnode->_prve = tail;newnode->_next = _head;_head->_prve = newnode;*/insert(end(), x);}iterator insert(iterator pos ,const T& x){Node* newnode = new Node(x);Node* cur = pos._node;newnode->_prve = cur->_prve;cur->_prve->_next = newnode;newnode->_next = cur;cur->_prve = newnode;return iterator(newnode);}iterator erase(iterator pos){assert(pos != end());Node* cur = pos._node;Node* prve = cur->_prve;Node* next = cur->_next;prve->_next = next;next->_prve = prve;delete cur;return iterator(next);}void pop_back(){erase(--end());}void push_front(const T& x){insert(begin(), x);}void pop_front(){erase(begin());}void clear(){auto it = begin();while (it !=end()){it=erase(it);}}
private:Node* _head;
};

总结

例如：以上就是要讲的内容，本文仅仅简单介绍了list的使用和简单的模拟实现