一、list节点
list是一个双向循环带头的链表,所以链表节点结构如下:
template<classT>structListNode{
T val;
ListNode* next;
ListNode* prve;ListNode(int x){
val = x;
next = prve =this;}};
二、list迭代器
2.1、list迭代器与vector迭代器区别
list迭代器与vector迭代器不一样,不能使用简单的原生指针了;
vector中迭代器可以使用原生指针,因为vector的存储空间是连续的,可以通过指针+/-/++/–找到下一个(上一个)位置;而list(链表)我们知道存储空间是不连续的,不能通过指针++/—找到下一个(上一个)节点;那我们就不能使用原生指针。
2.2、list迭代器实现
既然原生指针不能满足我们的需求,那我们就要用其他的方法来实现迭代器,这时候类的封装的意义就体现出来了;我们只需要对原生指针进行封装,然后使用运算符重载来修改迭代器++/–这些行为,这样就可以满足我们的需求了。
具体代码如下:
template<classT,classRef,classStr>classlist_iterator{typedef ListNode Node;typedef list_iterator iterator;public:list_iterator(Node* node){
_node = node;}//前置++
iterator operator++(){
Node tmp(_node);
_node = _node->_next;return tmp;}//后置++
iterator operator++(int){
_node = _node->_next;return*this;}//前置--
iterator operator--(){
Node tmp(_node);
_node = _node->_prve;return tmp;}
iterator operator++(int){
_node = _node->_prve;return*this;}booloperator==(const iterator& it){return _node == it._node;}booloperator!=(const iterator& it){return _node != it._node;}
Ref operator*(){return _node->val;}
Ptr operator->(){return&(_node->_val);}private:
Node* _node;};
三、list实现
3.1、构造函数
先看一下list构造函数的接口
构造函数接口说明**list()默认构造函数,构造一个空的listlist (size_type n, const value_type& val =value_type())用n个val值构造listlist (InputIterator first, InputIterator last)还有一段迭代器区间初始化list (const list& x)**拷贝构造函数
这里我们实现的list是带头双向循环链表,具体结构与之前的双向链表相同。
在构造之前,我们需要先构造一个头结点,这里就写一个函数 empty_init 来构造这个头结点。
empty_init(){
_head =newNode();
_head->_next = _head;
_head->_prve = _head;}
默认构造函数
list(){empty_init();
_size =0;}
用n个val值构造
list(size_t n,const T& val){/*_head = new Node();
_head->_next = _head;
_head->_prve = _head;*/empty_init();for(size_t i =0; i < n; i++){
Node* newnode =newNode(val);
newnode->_next = _head->_next;
newnode->_prve = _head->_next;
_head->_next->_prve = newnode;
_head->_next = newnode;}
_size = n;}
迭代器区间构造
使用迭代器区间构造,这里复用一下后面的push_back直接尾插来构造。
template<classInputIterator>list(InputIterator first, InputIterator last){empty_init();
_size =0;while(first != last){push_back(*first);
_size++;}}voidpush_back(const T& val){
Node* newnode =newNode(val);
newnode->_next = _head;
newnode->_prve = _head->_prve;
_head->_prve->_next = newnode;
_head->_prve = newnode;}
拷贝构造函数
拷贝构造,这里直接复用上面迭代器构造即可。
list(const list& l){empty_init();list(l.begin(), l.end());
_size = l.size();}
3.2、迭代器
//iterator
iterator end(){//return _head->_next;returniterator(_head);}
iterator begin(){//return _head;returniterator(_head->_next);}
const_iterator end()const{//return _head->_next;returnconst_iterator(_head);}
const_iterator begin()const{//return _head;returnconst_iterator(_head->_next);}
这里迭代器返回值,可以直接返回节点指针(因为单参数的构造函数支持隐式类型转换)。
3.3、Capacity
主要就是empty和size(判断空和数据个数)
//Capacityboolempty(){return _head == _head->_next;}
size_t size(){/*size_t ret = 0;
Node* ptail = _head->_next;
while (ptail != head)
{
ret++;
ptail = ptail->_next;
}
return ret;*/return _size;}
这里遍历链表来计算数据个数,代价太大了,我们直接写一个成员变量,在初始化,插入和删除时修改,会方便很多。
3.4、增删查改
这里增删查改就实现其中的一部分,其他的不太常用。
3.4.1、push_back、push_front、pop_back、pop_front
头插尾插,头删尾删,对于list而言,只需要修改指针的指向;
voidpush_back(const T& val){
Node* newnode =newNode(val);
newnode->_next = _head;
newnode->_prve = _head->_prve;
_head->_prve->_next = newnode;
_head->_prve = newnode;
_size++;}voidpush_front(const T& val){
Node* newnode =newNode(val);
newnode->_next = _head->_next;
newnode->_prve = _head;
_head->_next->_prve = newnode;
_head->_next = newnode;
_size++;}//删voidpop_back(){if(!empty()){
Node* del = _head->_prve;
_head->_prve->_prve->_next = _head;
_head->_prve = _head->_prve->_prve;delete del;
_size--;}}voidpop_front(){if(!empty()){
Node* del = _head->_next;
_head->_next->_next->_prve = _head;
_head->_next = _head->_next->_next;delete del;
_size--;}}
3.4.2、insert
insert在指定位置插入数据,看它的参数列表,大概就知道,要在迭代器position 迭代器位置(之前)插入数据(1个或者n个),或者插入一段迭代器区间的数据。
//insertvoidinsert(iterator pos,const T& val){
Node* newnode =newNode(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;
tmp->_prve->_next = newnode;
tmp->_prve = newnode;++_size;}voidinsert(iterator pos, size_t n,const T& val){for(size_t i =0; i < n; i++){
Node* newnode =newNode(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;
tmp->_prve->_next = newnode;
tmp->_prve = newnode;}
_size+=n;}voidinsert(iterator pos,int n,const T& val){for(size_t i =0; i < n; i++){
Node* newnode =newNode(val);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;
tmp->_prve->_next = newnode;
tmp->_prve = newnode;}}
这里需要注意:
看到这里可能会疑惑,为什么实现了两个插入n个数据 的insert函数;
因为,当数据类型是int时,下面模版实例化出的函数(iterator , int , int)比这里实现的(iterator , size_t , int)更加匹配;编译器就会去调用更加匹配的函数,就会出错。这里就是为了防止这种出错。
插入迭代器的数据,与使用迭代器区间构造初始化相似,list只需改变指针指向即可。
template<classInputIterator>voidinsert(iterator pos, InputIterator first, InputIterator last){while(first != last){
Node* newnode =newNode(*first);
Node* tmp = pos._node;
newnode->_next = tmp;
newnode->_prve = tmp->_prve;
tmp->_prve->_next = newnode;
tmp->_prve = newnode;++first;}}
3.4.3、erase
erase删除一个节点,我们要修改前后节点的指针指向。
iterator erase(iterator pos){assert(pos !=end());
Node* del = pos._node;
Node* next = del->_next;
Node* prve = del->_prve;
next->_prve = prve;
prve->_next = next;delete del;return next;}
在我们删除节点之后,之前的迭代器就会失效,为了解决迭代器失效问题,我们就使用返回值,返回新的迭代器。
3.4.4、swap
这里实现的list只有一个成员函数(头结点的指针),直接交换即可。
voidswap(list& l){
std::swap(_head, l._head);}
3.4.5、clear
clear函数,清理数据,(保留头结点)。
//清除数据voidclear(){
iterator it =begin();while(it !=end()){
it =erase(it);}}
3.5、析构函数
析构函数相对就比较简单了,我们清理完数据,再释放头结点即可。
~list(){clear();delete _head;}
到这里,list的模拟实现就完成了;这里只是实现了其中的一部分内容,感兴趣的可以继续深入了解学习。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
ear函数,清理数据,(保留头结点)。
//清除数据voidclear(){
iterator it =begin();while(it !=end()){
it =erase(it);}}
3.5、析构函数
析构函数相对就比较简单了,我们清理完数据,再释放头结点即可。
~list(){clear();delete _head;}
到这里,list的模拟实现就完成了;这里只是实现了其中的一部分内容,感兴趣的可以继续深入了解学习。
我的博客即将同步至腾讯云开发者社区,邀请大家一同入驻:https://cloud.tencent.com/developer/support-plan?invite_code=2oul0hvapjsws
版权归原作者 努力学习的小廉 所有, 如有侵权,请联系我们删除。