本文主要是介绍【C++】list类:模拟实现(适合新手的手撕list),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
提示:在开始模拟实现list前,最好先熟悉下list相关接口:
【C++】容器list常用接口详解-CSDN博客https://blog.csdn.net/2301_80555259/article/details/141756824?spm=1001.2014.3001.5501
目录
一.基本结构
二.构造函数
三.析构函数
四.迭代器的实现
五.const迭代器
六.修改操作
七.list和vector对比
一.基本结构
list类是一个带头双向循环链表,因此在定义list类前,先要定义节点类
节点类中的成员都是要面向外部访问的,因此都应该设置为public类,所以干脆这里直接定义为struct(成员都是public的class类)
template<class T>
struct list_node
{T _data;list_node* _prev;list_node* _next;list_node(const T& x = T()):_data(x),_prev(nullptr),_next(nullptr){}
};
在list类中,由于链表都是些链接关系,所以list类中只需要定义一个头结点head即可,当然此处为了方便后续操作,加入了size
list类的基本框架
template<class T>
class list
{//简化下list_nodetypedef list_node node;
public://各种函数private:node* _head;//头结点size_t _size;//有效数据个数
};
二.构造函数
如何初始化head?头结点一开始prev和next都是指向本身的
因此,无参构造能很轻易地写出来
//无参构造
list()
{_head = new node;_head->_prev = _head;_head->_next = _head;_size = 0;
}//当然更这样写更好
//创建并初始化哨兵卫头结点,方便给构造和拷贝复用
void emptyinit()
{head = new node;_head->_prev = _head;_head->_next = _head;_size = 0;
}//无参构造
list()
{emptyinit();
}
无参的构造写好以后,接下来就可以仿照STL库中的带参构造,写一个用迭代器区间初始化的构造函数:
//迭代器区间构造
template<class InputIterator>
list(InputIterator first, InputIterator last)
{emptyinit();while (first != last){push_back(*first);++first;}
}
拷贝构造有很多写法,这里给出两种写法:
//直接拷贝构造
list(const list& x)
{empty_init();for (auto e : x){push_back(e);}
}
//利用临时对象拷贝构造
list(const list& x)
{emptyinit();//利用迭代器区间构造出一个临时对象tmplist tmp(x.begin(), x.end());std::swap(_head, tmp._head);std::swap(_size, tmp._size);
}
利用临时对象来进行拷贝构造实际上是一种精妙的方法,它先定义了一个临时变量tmp,利用迭代器区间构造深拷贝了x的所有值,随后将新创建节点的_head以及_size跟tmp交换即可,同时,出了作用域以后tmp作为临时对象就会销毁,调用析构函数,由于此时已经交换了,那么此时实际实在销毁原先新节点的内存。
三.析构函数
在实现析构函数前,可以先实现下clear函数,析构函数实际可以复用clear
//清空出了头节点外的数据
void clear()
{iterator it = begin();while (it != end()){it = erase(it);//erase会返回下一个节点的迭代器}_size = 0;
}
//清理头节点
~list()
{clear();delete _head;_head = nullptr;
}
四.迭代器的实现
之前模拟vector和string的时候,两者底层都是连续的,想要得到下一个数据直接++即可,想要得到数据直接*解引用即可
然而这对于list是不行的,因为它底层不连续,此时就需要我们重载各种运算符了,但由于其底层仍然是一个指针(内置类型,不能重载),因此我们就将其封装进一个类来重载
template<class T>
struct list_iterator
{//这里要加<T>typedef list_node<T> node;typedef list_iterator iterator;//成员变量node* _node;//成员函数
};
1.构造函数
//构造函数
list_iterator(node* node):_node(node)
{}
2. 前置++/--和后置++/--
//前置++
iterator operator++()
{_node = _node->_next;return *this;
}
//后置++
iterator operator++(int)
{iterator tmp = *this;_node = _node->_next;return tmp;
}
//前置--
iterator operator--()
{_node = _node->_prev;return *this;
}
//后置--
iterator operator--(int)
{iterator tmp = *this;_node = _node->_prev;return tmp;
}
3.等于和不等于
//等于
bool operator==(const iterator& it)const
{return _node == it._node;
}
//不等于
bool operator!=(const iterator& it)const
{return _node != it._node;
}
4.解引用和箭头操作
迭代器的使用都是相同的,与指针相同,所以解引用迭代器得到的应该是节点数据。此外,当list存储的类型是结构体时,还应该支持->箭头操作。
T& operator*()
{return _node->_data;
}
T* operator->()
{return &_node->_data;
}
指的注意的是,本来使用该迭代器需要用第一个->来找到data(当储存结构体类型时),然后再使用一个->才能查找到结构体内部的数据,但编译器为了代码的可读性,帮助我们省略了一个箭头,只需要一个箭头就可以访问数据了
做完这些后就可以将迭代器映射到list类当中了,在list类中复用迭代器类
typedef list_iterator iterator;
iterator begin()
{//使用匿名对象return iterator(_head->next);
}
iterator end()
{return iterator(_head);
}
五.const迭代器
const迭代器和普通迭代器的区别是什么?const迭代器是为const对象准备的,const对象进行了限制,不能修改对象里的数据,那么,什么操作会因此数据的改变呢?很明显是解引用操作和箭头->,它们一个返回值的引用(T&),一个返回的指针(T*),都具备修改的可能,当然,begin()和end()也可能修改
大家第一时间想到的可能是再重写一个const迭代器的类,里面的实现和普通迭代器都一样,唯一不同的点在于赋值重载*和->时,返回的const修饰的值
然而这样做就会显得很臃肿,代码重复度很高,仔细观察不同点,仅仅在于T*和T&,那么不妨在原先的迭代器模板中再加入两个模板参数,只有在编写这两个函数时用到这两个参数
template<class T, class Ref, class Ptr>
struct list_iterator
{//...Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
}
此时就能在list类中将普通迭代器和const迭代器区分开了,当使用const对象时 ,直接返回const迭代器,使用普通对象,就返回普通迭代器
template<class T>
class list
{//这里要加<T>typedef list_node<T> node;
public:typedef list_iterator<T,T&,T*> iterator;typedef list_iterator<T, const T&, const T*> const_iterator;//...private:node* _head;size_t _size;
};
iterator begin()
{//使用匿名对象return iterator(_head->next);
}
iterator end()
{return iterator(_head);
}
const_iterator begin()const
{return const_iterator(_head->next);
}
const_iterator end()const
{return const_iterator(_head);
}
六.修改操作
void push_back(const T& x)
{node* newnode = new node(x);node* tail = _head->_prev;tail->_next = newnode;_head->_prev = newnode;newnode->_prev = tail;newnode->_next = _head;++_size;
}iterator insert(iterator pos, const T& x)
{//pos是公开类,内部的_node可以用.访问node* prev = pos._node->_prev;node* next = pos._node;node* newnode = new node(x);newnode->_prev = prev;newnode->_next = next;prev->_next = newnode;next->_prev = newnode;++_size;return iterator(newnode);
}iterator erase(iterator pos)
{assert(pos != end());node* prev = pos._node->_prev;node* next = pos._node->_next;prev->_next = next;next->_prev = prev;delete pos._node;--_size;return iterator(next);
}//直接复用erase
void pop_back()
{erase(--end());
}
void pop_front()
{erase(begin());
}
七.list和vector对比
至此,list我们已经模拟完成,有没有加深一下对list的理解呢?在这里我们再对比一下list和vector的区别:
目录 | vector | list |
---|---|---|
底层结构 | 顺序表,物理空间连续 | 带头双向循环链表,物理空间不连续 |
随机访问 | 支持,效率为O(1) | 不支持,访问效率为O(N) |
插入和删除 | 任一位置插入删除效率低 | 任一位置插入删除效率高 |
空间利用率 | 连续空间,缓存利用率高 | 不连续空间,容易造成内存碎片 |
迭代器 | 原生的指针 | 对原生指针的封装 |
迭代器失效 | 插入和删除都会失效 | 只有删除会失效 |
使用场景 | 高效储存,支持随机访问 | 有大量插入和删除操作,不关心随机访问 |
这篇关于【C++】list类:模拟实现(适合新手的手撕list)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!