C++ STL::list常用操作及底层实现（中2）——实现list常用操作之删除(erase、remove、pop_front、pop_back、clear)
#ifndef _MY_LIST_H
#define _MY_LIST_H
template <typename T>
class Mylist;
template <typename T>
class Iterator;
//定义双向链表的结点类
template <typename T>
class ListNode
{
friend class Mylist<T>;//Mylist类为ListNode类的友元，从而可以访问其私有成员
friend class Iterator<T>;//迭代器类Iterator为ListNode类的友元，从而可以访问其私有成员
private:
T data;
ListNode<T> * leftlink;
ListNode<T> * rightlink;
ListNode() :leftlink(nullptr), rightlink(nullptr){};
ListNode(T _data) :data(_data), leftlink(nullptr), rightlink(nullptr){}
};
//定义双向链表类
template <typename T>
class Mylist
{
public:
Mylist();
~Mylist();
Iterator<T> Begin();
Iterator<T> End();
/********************插入**********************/
Iterator<T> Insert(Iterator<T> it, const T& _data);//插入数据
Iterator<T> Insert(Iterator<T> it, int n, const T& _data);//插入数据
template <class Iter>
Iterator<T> Insert(Iterator<T> it, Iter first, Iter last);//插入数据
void Push_front(const T& _data);//在表头插入
void Push_back(const T& _data);//在末尾插入
void Splice(Iterator<T> it, Mylist<T> & x);
void Splice(Iterator<T> it, Mylist<T> & x,Iterator<T> i);
void Splice(Iterator<T> it, Mylist<T> & x, Iterator<T> first, Iterator<T> last);
/*******************删除**********************/
Iterator<T> erase(Iterator<T> it);
Iterator<T> erase(Iterator<T> first, Iterator<T> last);
void Remove(const T& _data);//删除数据
void Pop_front();//删除表头元素
void Pop_back();//删除最后一个元素
void Clear();//删除全部数据
bool Empty();
private:
ListNode<T> * first;
};
//定义迭代器iterator
template <typename T>
class Iterator
{
friend class Mylist<T>;//Mylist类为Iterator类的友元，从而可以访问其私有成员
public:
Iterator() :current(nullptr){}
Iterator(ListNode<T> *& node) :current(node){}
//重载解引用符*
T& operator*()
{
return this->current->data;
}
//重载前缀自加运算符++
Iterator<T>& operator++()
{
this->current = this->current->rightlink;
return *this;
}
//重载后缀自加运算符++
Iterator<T> operator++(int)
{
Iterator<T> tmp = *this;
(*this).current = (*this).current->rightlink;
return tmp;
}
//重载前缀自减运算符--
Iterator<T>& operator--()
{
this->current = this->current->leftlink;
return *this;
}
//重载后缀自加运算符--
Iterator<T> operator--(int)
{
Iterator<T> tmp = *this;
(*this).current = (*this).current->leftlink;
return tmp;
}
//重载不等比较运算！=
bool operator!=(const Iterator<T>& it)
{
return this->current != it.current;
}
//重载等于比较运算==
bool operator==(const Iterator<T>& it)
{
return this->current == it.current;
}
//重载->
T* operator->()
{
return &(this->current->data);
}
private:
ListNode<T> * current;//节点指针
};
/***************************构造和析构函数*************************/
template <typename T>
Mylist<T>::Mylist()
{
first = new ListNode<T>;//生成一个表头结点，它里面不带数据
first->leftlink = first->rightlink = first;//左右都指向自己
}
template <typename T>
Mylist<T>::~Mylist()
{
}
/*********************Begin()和End()返回链表头和尾的迭代器***********************/
template <typename T>
Iterator<T> Mylist<T>::Begin()
{
return Iterator<T>(first->rightlink);
}
template <typename T>
Iterator<T> Mylist<T>::End()
{
return Iterator<T>(first);
}
/***************************插入数据Insert()*****************************/
template <typename T>
Iterator<T> Mylist<T>::Insert(Iterator<T> it, const T& _data)
{
ListNode<T> *newNode = new ListNode<T>(_data);//生成一个节点
//1.确定插入节点的指向
newNode->leftlink = it.current->leftlink;
newNode->rightlink = it.current;
//2.改变迭代器it指向节点的指向
it.current->leftlink = newNode;
//3.改变插入节点的前一个节点指向
newNode->leftlink->rightlink = newNode;
return Iterator<T>(newNode);
}
template <typename T>
Iterator<T> Mylist<T>::Insert(Iterator<T> it, int n, const T& _data)
{
for (; n>0; --n)
it = Insert(it, _data);
return it;
}
template <typename T>
template <class Iter>
Iterator<T> Mylist<T>::Insert(Iterator<T> it, Iter first, Iter last)
{
Iter _first = first;
for (; last != first; ++first){
Insert(it, *first);
}
for (; last != _first; ++_first){
it--;
}
return it;
}
/***************************插入数据push_front()\push_back()****************************/
template <typename T>
void Mylist<T>::Push_front(const T& _data)
{
Insert(this->Begin(),_data);
}
template <typename T>
void Mylist<T>::Push_back(const T& _data)
{
Insert(this->End(), _data);
}
/***************************插入数据Splice()****************************/
template <typename T>
void Mylist<T>::Splice(Iterator<T> it, Mylist<T> & x)
{
Splice(it,x,x.Begin(),x.End());
}
template <typename T>
void Mylist<T>::Splice(Iterator<T> it, Mylist<T> & x, Iterator<T> i)
{
Iterator<T> tmp = i;
//检测i是否为x的迭代器
for (Iterator<T> ite = x.Begin(); ite != x.End(); ite++){
if (ite == i){
Splice(it, x, i, ++tmp);
break;
}
}
}
template <typename T>
void Mylist<T>::Splice(Iterator<T> it, Mylist<T> & x, Iterator<T> first, Iterator<T> last)
{
Iterator<T> _first = first;
bool InList = false;
bool OneList = false;
//1.当x和this不是同一个，并且x不为空时，执行操作
if (this != &x && !x.Empty()){
//2.检测first是不是x的迭代器
for (Iterator<T> tmp = x.Begin(); tmp != x.End(); tmp++){
if (tmp == first){
InList = true;
break;
}
}
//3.判断last是否>first,并且判断first到last是不是一条完整的链表
while (InList && first!=last && ++_first != x.End()){
if (_first.current == last.current){
OneList = true;
break;
}
}
if (first != last && _first == x.End() && _first.current == last.current)
OneList = true;
//操作
if (InList == true && OneList == true){
ListNode<T> *lastNodePre = last.current->leftlink;
first.current->leftlink->rightlink = last.current;
last.current->leftlink = first.current->leftlink;
first.current->leftlink = it.current->leftlink;
it.current->leftlink->rightlink = first.current;
it.current->leftlink = lastNodePre;
lastNodePre->rightlink = it.current;
}
}
}
/***************************按迭代器删除数据erase()****************************/
template <typename T>
Iterator<T> Mylist<T>::erase(Iterator<T> it)
{
ListNode<T> *cur = it.current;
for (Iterator<T> i = this->Begin(); i != this->End(); ++i){
if (i == it){
it.current->rightlink->leftlink = it.current->leftlink;
it.current->leftlink-> rightlink = it.current->rightlink;
it++;
delete cur;
break;
}
}
return it;
}
template <typename T>
Iterator<T> Mylist<T>::erase(Iterator<T> first, Iterator<T> last)
{
if (first == this->Begin() && last == this->End()){
Clear();// erase all and return fresh iterator
return last;
}
else{ // erase subrange
while (first != last)
first = erase(first);
return first;
}
}
/***************************按数值删除数据：remove()****************************/
template <typename T>
void Mylist<T>::Remove(const T& _data)
{
for (Iterator<T> i = this->Begin(); i != this->End();){
if (*i == _data){
i = erase(i);
}
else{
++i;
}
}
}
/***************************Pop_front、Pop_back****************************/
template <typename T>
void Mylist<T>::Pop_front()
{
erase(this->Begin());
}
template <typename T>
void Mylist<T>::Pop_back()
{
erase(--this->End());
}
/***************************删除全部数据Clear()****************************/
template <typename T>
void Mylist<T>::Clear()
{
ListNode<T> *cur = first->rightlink;//保存fisrt的下一个节点
first->leftlink = first;//first的左指针指向自己
first->rightlink = first;//first的右指针指向自己
/*释放节点*/
while (cur != first){
ListNode<T> *tmp = cur;
cur = cur->rightlink;
delete tmp;
}
}
template <typename T>
bool Mylist<T>::Empty()
{
return first->rightlink == first;
}
#endif