网站换域名只做首页301,软件定制开发公司地址,免费建手机商城网站,wordpress 建站赚钱模拟实现list 引言#xff08;实现概述#xff09;list迭代器实现默认成员函数operator* 与 operator-operator 与 operator--operator 与 operator!迭代器实现概览 list主要接口实现默认成员函数构造函数析构函数赋值重载 迭代器容量元素访问数据修改inserterasepush_ba… 模拟实现list 引言实现概述list迭代器实现默认成员函数operator* 与 operator-operator 与 operator--operator 与 operator!迭代器实现概览 list主要接口实现默认成员函数构造函数析构函数赋值重载 迭代器容量元素访问数据修改inserterasepush_back 与 push_frontpop_back 与 pop_frontclearswap 源码概览总结 引言实现概述
在前面我们介绍了list的使用 戳我看list的介绍与使用详解哦
在本篇文章中将重点介绍list的接口实现通过模拟实现可以更深入的理解与使用list 我们模拟实现的 list 底层是一个带头双向循环链表
在实现list时我们首先需要一个结构体以表示链表中结点的结构list_node大致包括数据与指向前后结点的指针
templateclass T
struct list_node //结点类
{list_nodeT* _prev;list_nodeT* _next;T _date;list_node(const T date T()) //匿名对象: _prev(nullptr), _next(nullptr), _date(date){}
};在有了结点之后还需要一个 list类包括双向链表的头结点指针_pHead链表中的元素个数_size
templateclass T
class list //带头双向循环链表
{typedef list_nodeT Node;
private:Node* _pHead;size_t _size;
};大致结构如下 关于带头双向循环链表的实现可以参考之前的C语言版本实现在本篇文章中结构将不是最重点的内容戳我看C语言实现带头双向循环链表详解哦
与vector相同list是一个类模板其声明与定义不能分离。我们将模拟实现的list放在我们创建的命名空间内以防止与库发生命名冲突。 在list的模拟实现中我们只实现一些主要的接口包括默认成员函数、迭代器、容量、元素访问与数据修改
list迭代器实现
与vector不同list的迭代器是指针的封装通过运算符重载来实现原生指针的功能。 我们可以通过封装结点的指针即list_nodeT*来实现迭代器
默认成员函数
对于默认成员函数其实我们只需要实现构造函数即可这个__list_iterator类的属性只有一个结构体指针并不存在类中申请的资源所以编译器生成的析构函数与赋值运算符重载就够用了不需要再实现了。
默认构造 对于默认构造函数我们可以使用缺省参数即参数类型为结构体指针缺省值为nullptr。 直接在初始化列表中用参数初始化类属性即可 __list_iterator(Node* pNode nullptr):_pNode(pNode){}拷贝构造 对于拷贝构造参数必须是类类型的引用可以加上const修饰我们可以在类中将类类型__list_iteratorT, Ref, Ptr重命名为self以方便书写 在函数中直接赋值即可 __list_iterator(const self it){_pNode it._pNode;}operator* 与 operator-
迭代器使用时应该是与指针基本类似的所以也需要重载*与-。
重载 * 指针当然可以进行解引用的操作指向容器中元素的指针。对这个指针进行解引用操作结果就应该是该指针指向的元素。对于list的迭代器而言解引用该迭代器的结果就应该是结点中的_data元素的引用类型为T 我们可以为模板参数加上一个参数即Ref它表示T Ref operator*(){return _pNode-_date;}重载- 当T是自定义类型时其指针还可以通过-直接访问到T类型对象_data中的元素起指针作用的迭代器自然也需要实现这个功能。 但是对于这个运算符重载而言它并不知道要返回T类型对象中的什么元素所以这个operator-函数可以直接返回该迭代器对应的结点中的_data元素的指针然后在调用的时候再通过-来访问其中元素it--a;通过迭代器it访问T类型对象中的a元素。 但是这样的形式访问又与指针的用法不一致所以这里有一个特殊的规定即规定需要使用it-a;的方式通过迭代器访问T类型对象中的元素以获得与原生指针相同的使用方式 我们可以为模板参数加上一个参数即Ptr它表示T* Ptr operator-(){return (_pNode-_date);}operator 与 operator–
重载 操作即实现迭代器的指向向后移动一个元素list的迭代器底层是一个结构体指针所以只需要将当前_pNode-_next 赋值给_pNode即可 且分为前置与后置在区别这两个的实现时前面类和对象时已经详细介绍过了即给后置增加一个参数int但是不传参只用于区分前置与后置。 另外后置需要创建临时对象在*this后必须要返回临时对象而非引用 self operator(){_pNode _pNode-_next;return *this;}self operator(int){self temp(*this);_pNode _pNode-_next;return temp;}重载 -- 重载--与前面的类似即将_pNode-_prev 赋值给_pNode即可 self operator--(){_pNode _pNode-_prev;return *this;}self operator--(int){self temp(*this);_pNode _pNode-_prev;return temp;}operator 与 operator!
对于与! 重载即判断两个迭代器对象的属性是否相等即可 bool operator(const self it){return _pNode it._pNode;}bool operator!(const self it){return _pNode ! it._pNode;}迭代器实现概览 templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _pNode;__list_iterator(Node* pNode nullptr):_pNode(pNode){}__list_iterator(const self it){_pNode it._pNode;}Ref operator*(){return _pNode-_date;}Ptr operator-(){return (_pNode-_date);}self operator(){_pNode _pNode-_next;return *this;}self operator(int){self temp(*this);_pNode _pNode-_next;return temp;}self operator--(){_pNode _pNode-_prev;return *this;}self operator--(int){self temp(*this);_pNode _pNode-_prev;return temp;}bool operator(const self it){return _pNode it._pNode;}bool operator!(const self it){return _pNode ! it._pNode;}};list主要接口实现
在实现list之前我们可以对一些较为麻烦的类型进行重命名以方便书写
typedef list_nodeT Node;
typedef __list_iteratorT, T, T* iterator;
typedef __list_iteratorT, const T, const T* const_iterator;默认成员函数
构造函数
实现构造函数时我们需要实现无参构造、n个指定元素构造、迭代器区间构造以及拷贝构造
无参构造 由于我们模拟实现的list底层为带头双向循环链表所以在无参构造时虽然没有在list中放入元素但是还使需要先放入一个空结点作为头节点。 创建头节点的操作在任何构造函数中都要先进行所以我们将其封装为一个init_empty_list函数。这个初始化空list的函数需要new一个结点然后使节点中的_prev与_next都指向它自身最后将_size赋值为0 void init_empty_list(){ _pHead new Node();_pHead-_prev _pHead;_pHead-_next _pHead;_size 0;}list(){init_empty_list();}n个指定元素构造 使用n个指定元素构造有两个参数第一个就是int第二个是const T缺省值为T() 函数中首先调用init_empty_list构建一个头结点 再循环使用push_bake尾插n个指定元素value即可push_back后面会实现 list(int n, const T value T()){init_empty_list();while (n--){push_back(value);}}迭代器区间构造 是用迭代器区间构造函数是一个函数模板可以使用任何容器的迭代器区间来构造list 函数中首先调用init_empty_list构建一个头结点 然后再循环使用push_bake尾插first迭代器的解引用出的元素当first与last相等时出循环 template class Iteratorlist(Iterator first, Iterator last){init_empty_list();while (first ! last){push_back(*first);first;}}拷贝构造 拷贝构造函数的参数是一个const listT 实现时首先调用init_empty_list构建一个头结点 然后范围for使用push_bake将l中的元素逐一尾插到list中 list(const listT l){init_empty_list();for (auto el : l){push_back(el);}}析构函数
析构函数需要实现释放list中的资源。 首先复用clear清空list中的元素。clear中会实现释放结点中的资源后面部分会实现 再delete _pHead;释放头节点中的资源它会调用结点结构体的析构函数 ~list(){clear();delete _pHead;}赋值重载
对于赋值运算符重载我们直接使用新写法即先使用参数l创建一个临时对象 然后使用swap将临时对象与*this交换后面会实现swap函数 最后返回*this即可创建的临时对象就会在函数栈帧销毁时自动释放 listT operator(const listT l) //list operator(const list l) 对于赋值重载这样也可{listT temp(l);swap(temp);return *this;}迭代器
在前面已经实现了list的迭代器它是结点指针的封装
这里暂时只实现begin与end关于反向迭代器的实现在后面会详细介绍。 begin返回首元素的地址即头结点的下一个结点的地址 end返回尾元素下一个位置的地址即头节点的地址他们分别重载有const版本 iterator begin(){return iterator(_pHead-_next);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead-_next);}const_iterator end() const{return const_iterator(_pHead);}容量
在容器部分由于list并没有容量的概念所以我们只需要实现size与empty即可 我们在list的属性中我们设置了_size在插入元素时_size删除元素时_size--所以这里只需要返回_size的值即可 当_size 0时list为空empty返回true否者返回false size_t size() const{return _size;}bool empty() const{if (_size 0)return true;elsereturn false;}元素访问
由于list在任意位置访问元素的成本较高就没有提供operator[]的接口所以我们只需要实现front与back即可。分别返回首尾的元素有普通对象与const对象两个重载版本 在实现时我们可以借助list的属性_pHead即头结点的指针来访问首尾元素 我们模拟实现list的底层是带头双向循环链表所以list中的第一个元素就是_pHead-_next指向的结点中的元素list中的_pHead-_prev指向的结点中的元素
front只需要返回 _pHead-_next-_date 即可 back返回_pHead-_prev-_date即可返回值类型为Tconst版本就返回const T即可 T front(){return _pHead-_next-_date;}const T front()const{return _pHead-_next-_date;}T back(){return _pHead-_prev-_date;}const T back()const{return _pHead-_prev-_date;}数据修改 insert
list 的结构使在任意位置插入数据的效率是较高的只需要创建结点再链接到pos位置前即可
在实现insert时首先new一个结点类型为Node并用val初始化这个Node类型是前面重命名后的类型 这时我们需要记录pos位置的结点指针为curpos位置前面的结点指针为prev以方便后续链接 然后将pos结点的前一个结点与新结点链接即newnode与prev链接 再将pos结点与新结点链接即newnode与cur链接
最后更新_size并返回新结点的迭代器 // 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* newnode new Node(val);Node* cur pos._pNode;Node* prev cur-_prev;newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}erase
erase实现时只需要释放pos位置的结点并链接剩余的结点即可
首先assert判断list是否为空 这时我们需要记录pos位置的结点指针为curpos位置前面的结点指针为prevpos的后一个结点指针为next以方便后续链接 然后直接链接pos位置的前一个结点与后一个结点即链接prev与next即可
最后释放cur指向的结点更新_size并返回next // 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){assert(!empty());Node* cur pos._pNode;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return iterator(next);}push_back 与 push_front
对于头插与尾插的实现复用insert即可
push_front即在首结点的前面一个位置插入一个元素即在begin()迭代器位置插入 push_back即在尾结点的后一个位置插入一个元素即在end()位置插入 void push_back(const T val){insert(end(), val);}void push_front(const T val){insert(begin(), val);}pop_back 与 pop_front
对于头删尾删的实现复用erase即可
pop_front即删除头节点即 erase删除begin()位置的结点 即可 pop_back删除尾结点即 erase删除end()前面一个结点即可但是由于list迭代器不支持-操作所以这里传参为--end() void pop_front(){erase(begin());}void pop_back(){erase(--end());}clear
clear用于清理list中的所有元素可以直接复用erase来实现清理
我们可以通过遍历迭代器的方式逐一释放结点 令it的初始值为begin()循环逐一erase删除当it等于end()的时候终止循环就可以实现删除所有结点并保留头节点 另外由于erase删除某节点后会返回删除节点的下一个位置所以只要把返回值载赋值给it就实现了迭代器的向后移动 void clear(){iterator it begin();while (it ! end()){it erase(it);//erase返回删除的结点的下一个位置的迭代器}}swap
实现list的交换函数时只需要使用库swap交换list的属性即可即交换_pHead与_size void swap(listT l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}源码概览
关于反向迭代器的实现在后面会详细介绍现在可以暂时忽略
#includeiostream
#includecassert
#includemy_reverse_iterator.hnamespace qqq
{templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _date;list_node(const T date T()) //匿名对象: _prev(nullptr), _next(nullptr), _date(date){}};templateclass T, class Ref, class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref, Ptr self;Node* _pNode;__list_iterator(Node* pNode nullptr):_pNode(pNode){}__list_iterator(const self it){_pNode it._pNode;}Ref operator*(){return _pNode-_date;}Ptr operator-(){return (_pNode-_date);}self operator(){_pNode _pNode-_next;return *this;}self operator(int){self temp(*this);_pNode _pNode-_next;return temp;}self operator--(){_pNode _pNode-_prev;return *this;}self operator--(int){self temp(*this);_pNode _pNode-_prev;return temp;}bool operator(const self it){return _pNode it._pNode;}bool operator!(const self it){return _pNode ! it._pNode;}};templateclass Tclass list //带头双向循环链表{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;typedef ReverseIteratoriterator, T, T* reverse_iterator;typedef ReverseIteratorconst_iterator, const T, const T* const_reverse_iterator;public:/ constructor and destructor void init_empty_list(){ _pHead new Node();_pHead-_prev _pHead;_pHead-_next _pHead;_size 0;}list(){init_empty_list();}list(int n, const T value T()){init_empty_list();while (n--){push_back(value);}}template class Iteratorlist(Iterator first, Iterator last){init_empty_list();while (first ! last){push_back(*first);first;}}list(const listT l){init_empty_list();for (auto el : l){push_back(el);}}listT operator(const listT l) //list operator(const list l) 对于赋值重载这样也可{listT temp(l);swap(temp);return *this;}~list(){clear();delete _pHead;}// List Iterator///iterator begin(){return iterator(_pHead-_next);}iterator end(){return iterator(_pHead);}const_iterator begin() const{return const_iterator(_pHead-_next);}const_iterator end() const{return const_iterator(_pHead);}reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}/List Capacity//size_t size() const{return _size;}bool empty() const{if (_size 0)return true;elsereturn false;}///List Access///T front(){return _pHead-_next-_date;}const T front()const{return _pHead-_next-_date;}T back(){return _pHead-_prev-_date;}const T back()const{return _pHead-_prev-_date;}List Modify//void push_back(const T val){insert(end(), val);}void pop_back(){erase(--end());}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}// 在pos位置前插入值为val的节点iterator insert(iterator pos, const T val){Node* newnode new Node(val);Node* cur pos._pNode;Node* prev cur-_prev;newnode-_prev prev;prev-_next newnode;newnode-_next cur;cur-_prev newnode;_size;return iterator(newnode);}// 删除pos位置的节点返回该节点的下一个位置iterator erase(iterator pos){assert(!empty());Node* cur pos._pNode;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;--_size;return iterator(next);}void clear(){iterator it begin();while (it ! end()){it erase(it);//erase返回删除的结点的下一个位置的迭代器}}void swap(listT l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:Node* _pHead;size_t _size;};
};总结
到此关于list的模拟实现就到此结束了 模拟实现容器并不是为了造一个更好的轮子而是为了更好的理解与使用容器
如果大家认为我对某一部分没有介绍清楚或者某一部分出了问题欢迎大家在评论区提出
如果本文对你有帮助希望一键三连哦
希望与大家共同进步哦
