上一篇我们介绍了插入的常用操作，本文介绍删除的相关操作。
1.erase()：按链表迭代器删除
它有两种函数形式：
格式1：iterator erase (iterator position)
格式2：iterator erase (iterator first, iterator last)
下面分别介绍两种形式的用法，及实现这两种格式。
1.1函数格式1：iterator erase (iterator position)
- 解释：删除position位置的元素，并返回被删除的元素的下一个元素的迭代器
- 举例：有一个链表l：1<->2<->3。执行erase(l.begin())后链表变为2<->3，返回2位置的迭代器。
我的实现：
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;
}
1.2函数格式2：iterator erase (iterator first, iterator last)
- 解释：删除[first,last)位置的元素，并返回被删除的元素的下一个元素的迭代器，也就是last迭代器
- 举例：有一个链表l：1<->2<->3。执行erase(l.begin(),–l.end())后链表变为3，返回3位置的迭代器。
- 使用注意：当first = last时，不删除元素，但是返回的迭代器是last对应的位置。
我的实现：
通过调用erase格式1形式来实现。
Notes：在STL::list实现中，当first = begin()，last = end()时，它调用了clear()函数，所以我也按照它来实现。其实我认为直接用while调用第一种格式的erase也能实现，为什么STL要这么做我现在也不太明白，如果有大佬知道，希望大佬能告知，评论也行，私信也可以。
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;
}
}
2.remove()：按值执行删除操作
函数格式：void remove (const value_type& val)
- 解释：删除链表中值为val的元素
- 举例：有一个链表l：1<->2<->3<->1。执行remove (1)后链表变为2<->3
我的实现：
通过调用第一种格式erase()来实现。
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;
}
}
}
3. pop_front、pop_back：删除链表头和链表尾的元素
- 解释：pop_front删除链表头元素；pop_back删除链表尾部数据。
- 举例：有一个链表l：1<->2<->3<->1。执行pop_front ()后链表变为2<->3<->1；再执行pop_back()，链表变为2<->3
我的实现：
template <typename T>
void Mylist<T>::Pop_front()
{
erase(this->Begin());
}
template <typename T>
void Mylist<T>::Pop_back()
{
erase(--this->End());
}
4. clear：清除链表所有元素
- 解释：清除链表中的所有元素
- 有一个链表l：1<->2<->3<->1。执行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;
}
}
5.完整代码（包括插入和删除）
Mylist.h
#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;
//4.splice操作
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
好了，list的删除操作就完成了，下一篇文章将实现list的一些其他的操作。
如果有疑问，欢迎评论区下方留言；本人水平有限 ，如有错误，也欢迎在评论区下方批评指正。若是喜欢本文，就帮忙点赞吧！
系列文章链接：
C++ STL::list常用操作及底层实现（上）——实现list迭代器
C++ STL::list常用操作及底层实现（中1）——实现list常用操作之插入(insert、push_front、push_back、splice)
C++ STL::list常用操作及底层实现（中2）——实现list常用操作之删除(erase、remove、pop_front、pop_back、clear)
C++ STL::list常用操作及底层实现（下）——实现list其他常用操作(reverse、assign、front、back)
