企业网站租服务器,wordpress dux1.3,台州网站关键字优化,门户网站建设厂商名录【C】—— list 模拟实现 1 list 基础结构2 默认构造3 迭代器3.1 整体框架3.2 成员函数3.3 begin() 与 end() 的实现3.4 operator- 的实现3.5 const 迭代器3.5.1 const 迭代器为什么命名 const_iterator3.5.2 const 迭代器的实现3.5.3 合并两个迭代器 4 源码 1 list 基础结… 【C】—— list 模拟实现 1 list 基础结构2 默认构造3 迭代器3.1 整体框架3.2 成员函数3.3 begin() 与 end() 的实现3.4 operator- 的实现3.5 const 迭代器3.5.1 const 迭代器为什么命名 const_iterator3.5.2 const 迭代器的实现3.5.3 合并两个迭代器 4 源码 1 list 基础结构 l i s t list list 的底层就是我们之前学过的双向链表它由一个哨兵位头结点 _pHead 和记录链表长度的 _size 组成。 而链表中的每个节点都是由两个自身类型指针和一个存储数据的变量组成的。因此我们不仅要定义链表的类还要定义节点的类 下面是 l i s t list list 的成员变量和整体框架
namespace my_list
{templateclass Tstruct ListNode{ListNode* _prev;ListNode* _next;T _val;//默认构造ListNode(const T val T()):_prev(nullptr),_next(nullptr),_val(val){}};templateclass Tclass list{typedef ListNodeT Node;//给节点重命名//成员函数···private:Node* _pHead;//哨兵位头结点指针size_t _size;}
}因为我们要频繁访问节点因此我们直接用 s t r u c t struct struct 定义节点其成员变量默认全公有。
2 默认构造 我们先写一个简单的无参默认构造出来。 默认构造可以直接这样写吗
list():_pHead(nullptr),_size(0)
{}不可以的因为双向链表有个哨兵位。即使链表中没有任何数据头节点指针也是指向哨兵位而不是空所以我们应创建哨兵位并将其初始化 而哨兵位的前驱指针 _ p r e v prev prev 和后继指针 _ n e x t next next因为整个链表只有它自己它的前一个和后一个节点都是自己因此 _ p r e v prev prev 和 _ n e x t next next 都是指向哨兵位自己
list()
{_pHead new Node;_pHead-_next _pHead;_pHead-_prev _pHead;_size 0
}其是不仅仅是无参的构造所有的构造函数第一步都是初始化哨兵位因此我们不妨单独写一个函数出来
list()
{CreateHead()
}void CreateHead()
{_pHead new Node;_pHead-_next _pHead;_pHead-_prev _pHead;_size 0;
}这里有个问题就是CreateHead()是非 c o n s t const const 成员函数那定义 c o n s t const const 成员是否还能来调用呢答案自然是可以的因为 c o n s t const const 变量在定义的时候是不具有 c o n s t const const 属性的定义完成之后才有。比如说
//如果在定义之前就具有const属性那么n就无法赋值
//const变量只有在定义时可以被赋值
const int n 10;
const listint l1;3 迭代器 要模拟实现 l i s t list list 迭代器的实现是其中的重中之重。 前面我们模拟实现 s t r i n g string string 和 v e c t o r vector vector他们的迭代器都是原生指针他们的原生指针完美符合迭代器的所有要求。其本质是因为他们底层物理空间是连续的。 但 l i s t list list 不像 s t r i n g string string 和 v e c t o r vector vector 那样天生丽质它的底层结构是一个一个节点并不连续无法满足迭代器的要求比如 我们希望的是迭代器跳到下一个节点如果使用原生指针因为不是连续的物理空间当前节点 大概率是个野指针。 但没关系 l i s t list list 可以通过封装通过运算符重载来满足迭代器的要求。
3.1 整体框架 迭代器其本身就是模拟指针的行为既然节点的原生指针无法满足迭代器的要求我们对节点指针进行封装通过运算符重载让其满足迭代器的需求
templateclass T
struct ListIterator
{typedef ListIteratorT Self;//给自身类(迭代器)重命名短一点方便typedef ListNodeT Node;//节点重命名//成员变量节点的指针Node* pNode;//成员函数//··· };因为待会链表中要大量访问成员变量我们直接用默认全公有的 s t r u c t struct struct 到现在我们一共实现了三个类为什么要实现三个类呢我们先把每个类的作用过一遍 class list链表这个类是链表的基本结构指向哨兵位的头结点管理这整个链表struct ListNode节点这个类是因为链表中每个节点都是自定义类型每个数据都是存在一个独立的结构体里面struct ListIterator迭代器这个类遍历整个链表本来是用节点的指针但是节点的指针是不符合我们的预期我们希望有一个迭代器统一的方式进行遍历因此我们用一个结构去封装节点的指针封装以后通过重载运算符使节点的指针能达到迭代器那样的行为 3.2 成员函数 有了迭代器这个类我们就可以运用运算符重载满足迭代器的行为啦
templateclass T
struct ListIterator
{typedef ListIteratorT Self;typedef ListNodeT Node;//成员变量Node* pNode;//解引用T operator*(){return pNode-_val;}//前置Self operator(){pNode pNode-_next;return *this;}//后置Self operator(int){Self tmp *this;pNode pNode-_next;return tmp;}//前置--Self operator--(){pNode pNode-_prev;return *this;}//后置--Self operator--(int){Self tmp *this;pNode pNode-_prev;return tmp;}//不等于bool operator!(const Self x){return pNode ! x.pNode;}//等于bool operator(const Self x){return pNode x.pNode;}
}3.3 begin() 与 end() 的实现 迭代器的基本行为实现了我们也可以在list类中实现begin()、end()等函数了 begin()函数是返回第一个迭代器我们要构造第一个位置的迭代器那怎么构造呢我们用第一个节点的指针即_pHead-_next就能构造第一个迭代器但现在ListIterator类中还缺少一个构造函数
//默认构造
ListIterator(Node* p nullptr):pNode(p)
{}//拷贝构造
ListIterator(const ListIterator x)
{pNode x.pNode;
}其实上述拷贝构造可以不用实现编译器会自己生成一个拷贝构造完成浅拷贝指向链表的节点。 这里不要认为有指针指向资源就要自己实现深拷贝而是看指针所指向的资源是不是属于自己的。像 s t r i n g string string、 v e c t o r vector vector 那些就需要自己实现深拷贝但迭代器指向的是链表的资源并不是迭代器自己的并且迭代器本身的目标就是指向链表的节点以此来访问遍历链表因此浅拷贝即可。 所以赋值重载和析构与不需要写 现在万事具备只欠东风我们还要在list类中将ListIterator类 t y p e d e f typedef typedef 成 i t e r a t o r iterator iterator
templateclass T
class list
{typedef ListNodeT Node;typedef ListIteratorT iterator;//重命名为iterator//成员函数···private:Node* _pHead;size_t _size;
}下面是begin()的实现
iterator begin()
{iterator it(_pHead-_next);return it;
}上述是有名对象的写法我们可以用匿名对象的写法
iterator begin()
{ return iterator(_pHead-_next);
}甚至我们可以用隐式类型转换直接传指针就好啦 迭代器本身就是节点的指针指针节点指针本身不满足迭代器的那些需求所以我们才用一个类把他封装一层用重载运算符使其达到迭代器的要求。 iterator begin()
{return _pHead-_next;
}end()是最后一个数据的下一个位置就是哨兵位的头结点
iterator end()
{return _pHead;
}3.4 operator- 的实现 既然迭代器模拟的是指针的行为那它还要实现 operator- 什么情况下用到 - 运算符呢 现在我们定义一个类型 AA链表中存储的数据是 AA 类型我们想依次遍历链表打印每个节点 AA 中的两个成员变量
struct AA
{int _a1 1;int _a2 2;
}void test1()
{listAA lta;lta.push_back(AA());lta.push_back(AA());lta.push_back(AA());listAA::iterator it lta.begin();while (it ! lta.end()){cout (*it)._a1 (*it)._a2 endl;cout it-_a1 it-_a2 endl;}
}上述(*it)._a1与it-_a1的写法是等价的但现在还没重载-运算符 下面是operator-的实现方式
T* operator-()
{return (pNode-_val);
}operator-的实现方式非常奇怪返回的是T* 其实这里省略了一个 -因为太难看了为了可读性省略了一个 -
cout it-_a1 it-_a2 endl;//本质是这样的
cout it--_a1 it--_a2 endl;第一个-是运算符重载出来的第二个则是普通的- 本质是这样的:
cout it.operator-()-_a1 it.operator-()-_a2 endl;cout (pNode-_val)-_a1 (pNode-_val)-_a2 endl;3.5 const 迭代器
3.5.1 const 迭代器为什么命名 const_iterator 首先问大家一个问题 c o n s t const const 迭代器为什么是const_iterator而不是const iterator呢 c o n s t const const 迭代器是自身不能修改还是指向的内容不能修改呢 就和指针一样指针的 c o n s t const const 有两个一个在 * 之前一个在 * 之后
T* const ptr1//指针本身不能修改
const T* ptr2//指向的内容不能修改如果是 const iterator const 直接修饰一个变量就是这个变量本身不能修改即迭代器本身不能修改而我们 c o n s t const const 迭代器是要指向的内容不能修改所以const_iterator更合适
3.5.2 const 迭代器的实现 那我们如何让迭代器指向的内容不能修改呢 迭代器修改我们指向的内容是怎么修改的通过operator* 和operator-那我们在其返回值上加上 c o n s t const const 就不能修改了
const T operator*()
{return pNode-_val;
}const T* operator-()
{return (pNode-_val);
}那我们就再自己实现一个 c o n s t const const 迭代器的封装吧
templateclass T
struct const_ListIterator
{typedef const_ListIteratorT Self;typedef ListNodeT Node;Node* pNode;const_ListIterator(Node* p nullptr):pNode(p){}const T operator*(){return pNode-_val;}const T* operator-(){return (pNode-_val);}Self operator(){pNode pNode-_next;return *this;}Self operator(int){Self tmp *this;pNode pNode-_next;return tmp;}Self operator--(){pNode pNode-_prev;return *this;}Self operator--(int){Self tmp *this;pNode pNode-_prev;return tmp;}bool operator!(const Self x){return pNode ! x.pNode;}bool operator(const Self x){return pNode x.pNode;}
};3.5.3 合并两个迭代器 上面我们再重新封装了一个const_iterator基本满足了需求但是代码太冗余了除了operator* 和operator- 的返回值类型不一样其他代码全是一样的有什么办法将他们合二为一呢 我们来看一下库中是怎么实现的 库中的__list_iterator类用了三个模板参数新增了 Ref 与 Ptr 两个参数。 在 l i s t list list 类中将__list_iteratorT, T, T* t y p e d e f typedef typedef 成 i t e r a t o r iterator iterator将__list_iteratorT, const T, const T* t y p e d e f typedef typedef 成 c o n s t const const_ i t e r a t o r iterator iterator。 也就是说 i t e r a t o r iterator iterator 的 R e f Ref Ref 参数即 T P t r Ptr Ptr 即参数 T* c o n s t const const_ i t e r a t o r iterator iterator 的 R e f Ref Ref参数即 c o n s t const const T P t r Ptr Ptr 参数即 c o n s t const const T*
以operator* 举例 T 传给RefRef 即referenceoperator*的返回值是reference替换过来operator*的返回值就是 T 对 c o n s t const const_ i t e r a t o r iterator iterator c o n s t const const T 传给 R e f Ref Ref替换过来operator*的返回值就是 c o n s t const const T 其实这种写法与上面我们自己实现两个类模板并没有本质区别他们实例化出来都是两个不同的类。不同的是第一种写法是我们自己写了两个不同的类而第二种是我们通过控制模板参数让编译器实例化出两个不同的类把我们干的活交给了编译器 代码如下
templateclass T, class Ref, class Ptr
struct ListIterator
{typedef ListIteratorT, Ref, Ptr Self;typedef ListNodeT Node;Node* pNode;ListIterator(Node* p nullptr):pNode(p){}Ref operator*(){return pNode-_val;}Ptr operator-(){return (pNode-_val);}Self operator(){pNode pNode-_next;return *this;}Self operator(int){Self tmp *this;pNode pNode-_next;return tmp;}Self operator--(){pNode pNode-_prev;return *this;}Self operator--(int){Self tmp *this;pNode pNode-_prev;return tmp;}bool operator!(const Self x){return pNode ! x.pNode;}bool operator(const Self x){return pNode x.pNode;}
};4 源码
对于 l i s t list list 的其他成员函数与前面的 s t r i n g string string、 v e c t o r vector vector 实现起来都大同小异这里就不再赘述了我们直接看源码
#pragma once
#includeiostream
#includeassert.husing namespace std;namespace my_list
{templateclass Tstruct ListNode{ListNode* _prev;ListNode* _next;T _val;ListNode(const T val T()):_prev(nullptr),_next(nullptr),_val(val){}};templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListIteratorT, Ref, Ptr Self;typedef ListNodeT Node;Node* pNode;ListIterator(Node* p nullptr):pNode(p){}Ref operator*(){return pNode-_val;}Ptr operator-(){return (pNode-_val);}Self operator(){pNode pNode-_next;return *this;}Self operator(int){Self tmp *this;pNode pNode-_next;return tmp;}Self operator--(){pNode pNode-_prev;return *this;}Self operator--(int){Self tmp *this;pNode pNode-_prev;return tmp;}bool operator!(const Self x){return pNode ! x.pNode;}bool operator(const Self x){return pNode x.pNode;}};templateclass Tclass list{typedef ListNodeT Node;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T, const T* const_iterator;list():_pHead(nullptr), _size(0){CreateHead();}list(int n, const T value T()){CreateHead();while (n--){push_back(value);}}template class Iteratorlist(Iterator first, Iterator last){CreateHead();Iterator it first;while (it ! last){push_back(*it);it;}}list(const listT l){CreateHead();const_iterator it l.begin();while (it ! l.end()){push_back(*it);it;}}listT operator(listT l){swap(l);return *this;}~list(){clear();delete _pHead;_pHead nullptr;}iterator begin(){return _pHead-_next;}iterator end(){return _pHead;}const_iterator begin() const{return _pHead-_next;}const_iterator end() const{return _pHead;}size_t size()const{return _size;}bool empty()const{return _size 0;}T front() {return _pHead-_next-_val;}T back(){return _pHead-_prev-_val;}const T front() const{return _pHead-_next-_val;}const T back() const{return _pHead-_prev-_val;}void push_back(const T val){Node* p new Node(val);p-_next _pHead;_pHead-_prev-_next p;p-_prev _pHead-_prev;_pHead-_prev p;_size;}void pop_back(){Node* p _pHead-_prev;p-_prev-_next _pHead;_pHead-_prev p-_prev;delete p;--_size;}void push_front(const T val){Node* p new Node(val);p-_next _pHead-_next;p-_prev _pHead;_pHead-_next p;p-_next-_prev p;_size;}void pop_front(){Node* p _pHead-_next;_pHead-_next p-_next;p-_next-_prev _pHead;delete p;--_size;}iterator insert(iterator pos, const T val){Node* p new Node(val);p-_next pos.pNode;p-_prev pos.pNode-_prev;pos.pNode-_prev-_next p;pos.pNode-_prev p;_size;return pos;}iterator erase(iterator pos){assert(pos ! end());iterator ret pos.pNode-_next;pos.pNode-_prev-_next pos.pNode-_next;pos.pNode-_next-_prev pos.pNode-_prev;delete pos.pNode;--_size;return ret;}void clear(){iterator it begin();while (it ! end()){iterator cur it;delete cur.pNode;}_pHead-_next _pHead;_pHead-_prev _pHead;_size 0;}void swap(listT l){std::swap(_pHead, l._pHead);std::swap(_size, l._size);}private:Node* _pHead;size_t _size;void CreateHead(){_pHead new Node;_pHead-_next _pHead;_pHead-_prev _pHead;_size 0;}};
}templateclass Container
void print_container(const Container v)
{auto it v.begin();while (it ! v.end()){cout *it ;it;}cout endl;
}好啦本期关于 l i s t list list 的知识就介绍到这里啦希望本期博客能对你有所帮助。同时如果有错误的地方请多多指正让我们在 C 的学习路上一起进步
