C++——list的简要介绍

list的介绍

详细请看（https://cplusplus.com/reference/list/list/?kw=list）

1.list是一个可以在常数范围内在任意位置，进行插入和删除的序列式容器，并且此容器可以前后双向迭代。

2.list的底层实质是一个双向链表结构，双向链表里每个元素的存放都互不相关，在节点中可以通过指针来指向前一个元素和后一个元素

3.相对于vector等序列式容器，list在任意位置上的插入、删除元素的效率会更高。

4.但是list与其他序列式容器相比，最大缺陷是不支持任意位置的随机访问，必须要从已知位置迭代到当前的位置，只有这样才可以进行数据的读取。

简要使用

建立及其数据的尾插

void test_list1()
{list<int> l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);list<int>::iterator it = l1.begin();//读取需要用迭代器读取，不能用下标while (it != l1.end()){cout << *it << " ";++it;}cout << endl;for (auto e : l1){cout << e << " ";}cout << endl;
}

排序

list<int> l1;
l1.push_back(1);
l1.push_back(2);
l1.push_back(3);
l1.push_back(4);
l1.push_back(5);l1.reverse();//进行了逆序
l1.sort();//默认升序//降序
greater<int> gt;
l1.sort(gt);//传入这个即可l1.sort(greater<int>());//也可以用匿名函数//升序限定范围
sort(v.begin(), v.end());

数据的拷贝

lt2.assign(v.begin(), v.end());//粘贴

去重函数

list<int> L;
L.push_back(1);
L.push_back(4);
L.push_back(3);
L.push_back(3);L.unique();
//但在注意的是，去重函数本质是用一个双指针进行删除，连续相同的会留下一个，若是多个重复数据，若不是连//续的，那么结果还是会出现重复的元素。
//——所以需要先进行排序sort

分割函数

list<int> l1, l2;
for (int i = 1; i <= 4; i++)
{l1.push_back(i);
}
for (int i = 5; i <= 8; i++)
{l2.push_back(i);
}auto it = l1.begin();
l1.splice(it, l2);//将l2中的数据，全部插入到l1的it处

list的模拟实现

现在复现list类的简要底层代码——实现的结构体逻辑和用C实现相似。

namespace bit
{template<class T>struct list_node//节点的结构,并且对节点进行初始化{T _data;list_node<T>* _next;list_node<T>* _prev;list_node(const T& x = T())
//给缺省值，由于不知道是什么类型，所以用模板名T进行位置类型变量的初始化(作为缺省)->T():_data(x),_next(nullptr),_prev(nullptr){}};template<class T>class list//链表的结构，需要一个头结点即可{typedef list_node<T> Node;public:private:Node* _head;};
}

构造函数

void empty_init()
{_head=new Node;_head->_next=_head;_head->_prev=_head;
}list()
{empty_init();
}

尾插

void push_back(const T& x)
{Node*tail=_head->_prev;Node* newnode=new Node(x);//建立一个包含x的节点tail->_next=newnode;newnode->_prev=tail;newnode->_next=_head;_head->_prev=newnode;++_size;
}

节点迭代器

倘若我们有以下的代码

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

这样子会显示报错？这是为什么？——结构体存放的是结点，解引用出来的是一整个结构体

而且节点存放的空间不是连续存放的，所以需要写一个结构体，进行对于' 节点的指针 '的封装。

template<class T>
struct _list_iterator
{    typedef _list_iterator<T> self;typedef list_node<T> Node;Node* _node;//结构体里存放的就是节点
}

迭代器的构造

_list_iterator(Node* node)//此迭代器的本质也就是用节点的指针:_node(node)
{}

节点指针++

 self& operator()
{_node=_node->next;return *this;
}

解引用获取数据

T& operator*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T
{return _node->_data;	
}

指针的比较

bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称
{return _node != s._node;
}

list类

有了迭代器之后，对于list类作补充

template<class T>
class list
{
public:typedef _list_iterator<T> iterator;iterator begin(){return _head->_next;}iterator end(){return _head;}}

插入

iterator insert(iterator pos, const T& val)//由于插入是利用节点之间的连接进行的，且需要用迭代器
{Node* cur=pos._node;Node* newnode=new Node(val);Node* prev=cur->_prev;prev->_next=newnode;newnode->_prev=prev;newnode->_next=cur;cur->_prev=newnode;++_size;return iterator(newnode);//insert插入函数的结果会返回插入节点的位置
}

删除

iterator erase(iterator pos)
{Node* cur=pos._node;Node* prev=cur->_prev;Node* next=cur->_next;delete cur;prev->_next=next;next->_prev=prev;--_size;return iterator(next);//erase要返回下一个元素的指针
}

有了insert和erase后，可以方便地实现其他函数

void push_front(const T& x)//头插
{insert(begin(), x);
}
void pops_front(const T& x)//头删
{erase(begin());
}
void pops_back(const T& x)//尾删
{erase(end());
}

清理函数

void clear()
{iterator it=begin();while(it!=end()){it=erase(it);//erase会返回一个指向下一个位置的地址，用erase可以减少代码量}
}

拷贝重载/赋值拷贝

void swap(list<T>& lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}list<int>& operator=(list<int>& lt)
{swap(lt);return *this;
}list(const list<T>& lt)
{empty_init();for (auto e : lt){push_back(e);//直接用push_back进行数据的插入即可，不需要再作拷贝结点}
}

析构函数

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

完善节点指针的结构体

template<class T>//用一个迭代器的结构体进行结点的封装 ++
//struct 默认公有，但是class类需要做些声明
struct _list_iterator
{typedef list_node<T> Node;typedef _list_iterator<T> self;Node* _node;//创造一个结点_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器:_node(node)//传入begin，就会有对应位置的一个初始化结点出来{}self& operator++()//迭代器++{_node = _node->_next;return *this;}self operator++(int)//后置++{self tmp(*this);//进行拷贝_node = _node->_next;return tmp;}self& operator--()//迭代器++{_node = _node->_prev;return *this;}self operator--(int)//后置--{self tmp(*this);//进行拷贝_node = _node->_prev;return tmp;}T& operator*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T{return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node != s._node;}bool operator==(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node == s._node;}
};

const迭代器

我们知道，若无const修饰，那么就可以进行' 读写 '，若有const修饰，那么就只能进行' 读 '。

倘若用const修饰迭代器呢？(const iterator)——err，这样子会是迭代器本身不能修改，那么应该怎么表示？

——const_iterator 重新定义的一个类型，这样本身可以修改，指向的内容不能修改。

那么可以在迭代器基础上进行修改，成为const迭代器

template<class T>//用一个迭代器的结构体进行结点的封装 ++
//struct 默认公有，但是class类需要做些声明
struct _list_const_iterator
{typedef list_node<T> Node;typedef _list_const_iterator<T> self;Node* _node;_list_const_iterator(Node* node):_node(node){}self& operator++()//迭代器++{_node = _node->_next;return *this;}self operator++(int)//后置++{self tmp(*this);//进行拷贝_node = _node->_next;return tmp;}self& operator--()//迭代器++{_node = _node->_prev;return *this;}self operator--(int)//后置--{self tmp(*this);//进行拷贝_node = _node->_prev;return tmp;}//加上const修改后，迭代器里的内容就不能被修改const T& operator*()//解引用也要进行一个函数的封装,要的是这个数据，所以用T{return _node->_data;}const T* operator->(){return &_node->_data;}bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node != s._node;}bool operator==(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node == s._node;}
};

现在有了两个迭代器，但是这两个迭代器高度相似，仅有两个成员函数的返回值类型不同，那么有什么方法可以像模板那样子实现类型的简化呢？——同一个类模板，实例化参数不同，就是完全不同的类型。

改进

两个类归为一类

template<class T,class Ref,class Ptr>
struct _list_iterator
{typedef list_node<T> Node;typedef _list_iterator<T,Ref,Ptr> self;//模板中的类型T，可以用Ref和Ptr来分别取代//其中，T& 又可以被Ref代替  T* 可以被Ptr代替Node* _node;//创造一个结点_list_iterator(Node* node)//用一个结点的指针就能够造出一个迭代器:_node(node)//传入begin，就会有对应位置的一个初始化结点出来{}self& operator++()//迭代器++{_node = _node->_next;return *this;}self operator++(int)//后置++{self tmp(*this);//进行拷贝_node = _node->_next;return tmp;}self& operator--()//迭代器++{_node = _node->_prev;return *this;}self operator--(int)//后置--{self tmp(*this);//进行拷贝_node = _node->_prev;return tmp;}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node != s._node;}bool operator==(const self& s)//结点之间比较，所以用迭代器的结构体名称{return _node == s._node;}
};

那么对于list类，要通过两个模板参数进行相关的控制

class list
{typedef list_node<T> Node;
public:typedef _list_iterator<T,T&,T*> iterator;typedef _list_iterator<T, const T&, const T*> const_iterator;iterator begin(){return iterator(_head->_next);//两种写法}iterator end(){return _head;}const_iterator begin()const{return const_iterator(_head->_next);}const_iterator end()const{return _head;}
....//
}