1、什么是list
list是一个带头结点的双向循环链表模版容器，可以存放任意类型，需要显式定义
2、list的使用
有了前面学习string和vector的基础，学习和使用list会方便很多，因为大部分的内容依然是高度重合的。
与顺序表不同，链表是以结点形式进行链接和存储，其地址并不是连续的，因此进行插入和删除操作不需要进行大量的数据挪动，只需要改变指针的指向即可，方便很多。
使用push_back()和push_front()可以分别实现尾插和头插
list<int> lt;
lt.push_back(1);
lt.push_back(2);
lt.push_back(3);
lt.push_back(4);
lt.push_front(5);
lt.push_front(6);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;也可以使用insert实现在某一位置的插入，erase实现在某一位置的删除
lt.insert(lt.begin(), 9);
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
lt.erase(lt.begin());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;然而由于迭代器的失效问题，erase会返回被删除元素的下一个位置，因此，当进行连续删除时，我们可以使用迭代器来直接对此返回值进行接收来实现
list<int>::iterator it = ++lt.begin();
while (it != lt.end())
{
cout << (*it) << " ";
it=lt.erase(it);
}
cout << endl;
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;同时，由于list底层结构的不同，不能像string和vector一样去实现迭代器，因为string和vector在底层结构中是连续的，可以直接用指针去访问得到相应位置的元素内容，对指针进行++或者--操作又可以直接到达下一位置或者前一位置，list中存放的是一个一个不连续的结点，对迭代器的实现时需要进行相应的重载，使用也会受限，比如在上述代码中就无法使用lt.begin()+3等，更多内容在进行list的模拟实现中可以得到更多的体会
reverse()用于逆置，库里有实现公用的reverse，不过list里面也有提供自己的逆置，如果使用公用的则需要使用两个参数指定逆置的范围，如果使用的是自己的逆置则不需要传参
reverse(lt.begin(), lt.end());
lt.reverse();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;对于排序，之前的vector可以直接调用库中的sort()函数实现排序，实际sort()排序使用的是快排进行排序，而对于数组这种结构来说快排会很方便，而对于链表来说则比较困难，代价较高，因此库中的排序函数并不能对list进行排序，list内部自己有实现一个排序，可以进行使用并完成排序。不过对于list来说，排序始终代价较大，如果需要频繁使用排序应该使用其他的结构来存放数据，所以库里的sort()函数实质上也是对程序员的一种约束。
//sort(lt.begin(), lt.end());
lt.sort();
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;find()函数是库里实现的公用函数，list也可以使用，同时会返回寻找元素的位置
auto it=find(lt.begin(), lt.end(), 3);
cout << *it;splice()可以用于将某一部分的内容转移至其他list中，也可以转移给自身的其他地方
list<int> lt2 = { 10,20,30 };
//全部转移
//lt2.splice(lt2.begin(), lt);
//部分转移
//lt2.splice(lt2.begin(), lt, ++lt.begin());//转移某一位置的内容
lt2.splice(lt2.begin(), lt,++lt.begin(),--lt.end());//转移某一段位置的内容
//lt2.splice(++lt2.begin(), lt2, lt2.begin(), lt2.end());
for (auto e : lt)
{
cout << e << " ";
}
cout << endl;
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;
lt2.splice(lt2.begin(), lt2, ++lt2.begin(), lt2.end());
for (auto e : lt2)
{
cout << e << " ";
}
cout << endl;以上就是list的一些较常用的使用，那么在对list及其使用都有了解后就可以进行模拟实现
3、list的模拟实现
不得不说，我觉得list的实现比前面的string和vector的实现难很多，主要是迭代器的原因会上很大难度，很难以理解，所以直到勉强实现出来以后也还是处于一个似懂非懂的状态里，希望后面能继续加强自己的技术，实现轻松手撕
#include<iostream>
#include<list>
#include<algorithm>
using namespace std;
namespace bit
{
template<class T>
struct ListNode
{
ListNode(const T& val = T())
:_prev(nullptr)
,_next(nullptr)
,_val(val)
{}
ListNode* _prev;
ListNode* _next;
T _val;
};
template<class T,class Ref,class Ptr>
struct List_iterator
{
typedef ListNode<T> Node;
typedef List_iterator<T, Ref,Ptr> Self;
Node* _node;
List_iterator(Node* node)
:_node(node)
{}
Ref operator*()
{
return _node->_val;
}
Ptr operator->()
{
return &_node->_val;
}
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;
}
bool operator!=(const Self& it)
{
return _node != it._node;
}
bool operator==(const Self& it)
{
return _node == it._node;
}
};
template<class T>
class List
{
public:
typedef ListNode<T> Node;
typedef List_iterator<T, T&, T*> iterator;
typedef List_iterator<T, const T&, const T*> const_iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
const_iterator begin() const
{
return _head->_next;
}
const_iterator end() const
{
return _head;
}
List()
{
empty_init();
}
//list(const list<T>& lt)
//{
// empty_init();
// for (auto& e : lt)
// {
// push_back(e);
// _size++;
// }
//}
size_t size()
{
return _size;
}
void empty_init()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
_head->_val = 0;
_size = 0;
}
void push_back(const T& x)
{
insert(end(), x);
//Node* newnode = new Node;
//_head->_prev->_next = newnode;
//newnode->_prev = _head->_prev;
//newnode->_next = _head;
//_head->_prev = newnode;
//newnode->_val = x;
//_size++;
}
void push_front(const T& x)
{
insert(++end(), x);
//Node* newnode = new Node;
//_head->_next->_prev = newnode;
//newnode->_next = _head->_next;
//_head->_next = newnode;
//newnode->_prev = _head;
//newnode->_val = x;
//_size++;
}
void pop_back()
{
erase(--end());
}
void pop_front()
{
erase(++end());
}
void clear()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
_size = 0;
}
iterator insert(iterator pos,const T& x)
{
Node* newnode = new Node;
Node* cur = pos._node;
newnode->_prev = cur->_prev;
cur->_prev->_next = newnode;
cur->_prev = newnode;
newnode->_next = cur;
newnode->_val = x;
_size++;
return newnode;
}
iterator erase(iterator pos)
{
Node* cur = pos._node;
cur->_next->_prev = cur->_prev;
cur->_prev->_next = cur->_next;
pos._node = cur->_next;
delete cur;
_size--;
return pos;
}
void swap(List<T> tmp)
{
std::swap(_head, tmp._head);
std::swap(_size, tmp._size);
}
List<T>& operator=(List<T> tmp)
{
swap(tmp);
return *this;
}
List(const List<T>& lt)
{
empty_init();
//const_iterator it = lt.begin();
//while (it != lt.end())
//{
// push_back(*(it));
// it++;
//}
//_size = lt._size;
for (auto& e : lt)
{
push_back(e);
}
}
~List()
{
clear();
delete _head;
_head = nullptr;
}
private:
Node* _head;
size_t _size;
};
}