前言:这篇文章我们继续进行C++容器类的分享——list,也就是数据结构中的链表,而且是带头双向循环链表。
一.基本框架
namespace Mylist
{
template<class T>
//定义节点
struct ListNode
{
ListNode<T>* _next;
ListNode<T>* _prev;
T _data;
ListNode(const <T>& x = T())
:_next(nullptr)
,_prev(nullptr)
,_data(x)
{}
};
template<class T>
class list
{
typedef ListNode<T> Node;
public:
//构造函数
list()
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
}
//析构函数
~list()
{
iterator it = begin();
while (it != end())
{
it = erase(it);
}
delete _head;
_head = nullptr;
}
//数据个数
size_t size()
{
iterator it = begin();
size_t Size = 0;
while (it != end())
{
Size++;
it++;
}
return Size;
}
private:
Node* _head;
};
}
由于要满足存储任意类型的数据,所以我们必须要使用模版来进行定义。
迭代器
关于list类中的最难之处,就是迭代器了。
因为迭代器的原理即为指针,对于string和vector这种创建的对象的物理空间是连续的类来说,我们可以直接对迭代器进行“++”、“--”等数学运算。
而对于本质为链表的list来说,由于每个节点的物理空间都是随机创建,各个节点的地址并不连续,所以我们没法直接进行迭代器的数学运算,而需要对迭代器的各种功能进行重新定义,所以我们创建一个专门为迭代器服务的类:
//迭代器
template<class T>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T> Self;
ListIterator(Node* node)
:_node(node)
{}
//解引用
T& operator*()
{
return _node->_data;
}
//前置++
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;
}
Node* _node;
};
随后在list类中将该类名重定义为iterator,便可正常使用迭代器了:
typedef ListIterator<T> iterator;
iterator begin()
{
return _head->_next;
}
iterator end()
{
return _head;
}
这里值得注意的是,因为是带头双向循环链表,所以链表的开始即哨兵位的下一个,而结尾就是哨兵位。
但是现在的迭代器是存在问题的,它并不能实现对const修饰的数据的操作,所以我们还需要一个const迭代器。因为我们的普通迭代器就是用模版来实现的,所以这里可以直接通过模版来实现const迭代器:
//迭代器
template<class T,class Ref>
struct ListIterator
{
typedef ListNode<T> Node;
typedef ListIterator<T,Ref> Self;
//构造函数
ListIterator(Node* node)
:_node(node)
{}
//解引用
Ref operator*()
{
return _node->_data;
}
//前置++
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;
}
Node* _node;
};
typedef ListIterator<T,T&> iterator;
typedef ListIterator<T,const T&> const_iterator;
这里有一个细节,因为T同时还要服务于Node类,所以不能直接对其进行修改,而是另用一个模版参数。
因为const对象与非const对象最大的不同之处在于对数据的访问,所以定义一个名为Ref(引用)的模版参数,来对解引用运算符重载函数进行改造。
二.常用操作
1.插入
先来看任意位置的插入,需要传入某个位置的指针pos:
//pos前插入
void insert(iterator pos, const T& val)
{
Node* cur = pos._node;
Node* newnode = new Node(val);
Node* prev = cur->_prev;
prev->_next = newnode;
newnode->_next = cur;
cur->_prev = newnode;
newnode->_prev = prev;
}
现在对于我们来说就是非常简单,测试如下:
这里有一个小细节,如果我们插入的位置是第一个节点之前,由于it迭代器的指向并未改变,所以如果进行遍历,他就不会遍历出我们新插入的数据,所以需要更新一下it。
有了pos位置的插入之后,就可以用它来扩展头插和尾插:
//尾插
void push_back(const T& x)
{
insert(end(), x);
}
//头插
void push_front(const T& x)
{
insert(begin, x);
}
2.删除
我们同样先写出pos位置的删除:
//pos删除
iterator erase(iterator pos)
{
Node* cur = pos._node;
Node* next = cur->_next;
Node* prev = cur->_prev;
next->_prev = prev;
prev->_next = next;
delete cur;
return iterator(next);
}
由于删除会导致迭代器成为野指针,所以我们要对其进行更新, 测试如下:
同样由其扩展出头删和尾删:
//头删
void pop_front()
{
erase(begin());
}
//尾删
void pop_back()
{
erase(--end());
}
3.拷贝
和string和vector一样,list的拷贝也需要使用深拷贝,那么它的拷贝构造函数该怎么写?
同样是要开辟新的空间,需要一个自己的头结点,随后按照被拷贝的链表的数据进行尾插即可:
//拷贝构造
list(const list<T>& lt)
{
_head = new Node;
_head->_next = _head;
_head->_prev = _head;
for (auto& e : lt)
{
push_back(e);
}
}
测试如下:
此外,还有“=”运算符重载的方法:
//交换
void swap(list<T>& it)
{
std::swap(_head, it._head);
}
//=运算符重载
list<T>& operator=(list<T> lt)
{
swap(lt);
return *this;
}
这里仍然是巧妙的运用swap函数,因为lt是一个临时拷贝,有自己的空间和地址,所以直接让两者进行交换,lt在退出函数时即被销毁,而拷贝者则继承了它的地址空间,测试如下:
总结
关于list类的基本知识就分享到这里啦。
因为与string和vector都存在很多相似之处,所以建议将这三者放在一起学习。文章来源:https://www.toymoban.com/news/detail-846938.html
喜欢本篇文章记得一键三连,下期再见!文章来源地址https://www.toymoban.com/news/detail-846938.html
到了这里,关于C++——list类及其模拟实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!