网站顾客评价,写文案要看的网站,wordpress添加登入,门户网站建设 必要性前言
上一节我们讲解了list的基本功能#xff0c;那么本节我们就结合底层代码来分析list是怎么实现的#xff0c;那么废话不多说#xff0c;我们正式进入今天的学习#xff1a;#xff09; List的底层结构
我们先来看一下list的底层基本结构#xff1a; 这里比较奇怪的…前言
上一节我们讲解了list的基本功能那么本节我们就结合底层代码来分析list是怎么实现的那么废话不多说我们正式进入今天的学习 List的底层结构
我们先来看一下list的底层基本结构 这里比较奇怪的一点是底层选择了void*来表示链表的指针其实可以不用这么做
接下来是迭代器部分 模拟实现链表难就难在实现迭代器因为链表的物理空间不是连续的所以不能简单的通过typedef一个指针变量来达到实现迭代器的目的
链表为空的初始化 链表为空时不是简单的把所有的指针都赋空指针而是创建一个节点让这个节点的next和prev指针都指向自己。这就是创造了一个头节点这里涉及到数据结构阶段双向带头链表的基本知识 get_node是申请节点调用了内存池由于我们还没有学习内存池所以可以简单地将这里理解为malloc
下面是源代码中的头插尾插接口 通过这些我们可以知道单纯实现链表的功能是没有什么难度的和我们之前实现string和vector差不多难就难在理解迭代器的实现
既然底层结构已经看的差不多了那我们现在就来实现一下list吧
List的模拟实现
节点的基本结构
首先要实现链表的基本结构链表的基本结构是节点 templateclass Tstruct list_node{list_node(const T data T()):_data(data),_next(nullptr),_prev(nullptr){}T _data;list_nodeT* _next;list_nodeT* _prev;};
链表的借本结构
构造函数
先来实现一下构造函数根据底层是双向带头循环链表写出代码如下 templateclass Tclass list{public:typedef list_nodeT Node;list(){_head new Node(T());_head-_next _head;_head-_prev _head;_size 0;}private:Node* _head;size_t _size;}; size和empty函数
实现size和empty函数由于代码很简单就不做讲解了 size_t size(){return _size;}bool empty(){return _size 0;}
迭代器
因为不是每一个STL的容器都是存储在连续的物理空间之中所以并不是每一个容器都支持下标[]访问但是所有的容器都有迭代器都支持范围for因此实现迭代器是很重要的一个步骤我们来逐步分析迭代器的实现
我们知道对于一个节点而言*解引用以后找到的不是节点的值而是节点的地址因为存储空间不连续不能通过来找到下一个节点所以就不能仅通过typedef来实现迭代器此时我们就应该考虑封装运算符重载来实现迭代器主要内容就是重载 * ! 等让其满足与其他迭代器相同的作用 templateclass Tstruct list_iterator{Node* _node;};
迭代器的构造函数 list_iterator(Node* node):_node(node){}
重载* T operator*(){return _node-_data;}
重载前置、--
由于以后返回的数据类型依旧是迭代器为了书写简便一点调用typedef Self operator(){_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}
重载后置、--
因为后置和--是将当前的值使用以后再执行或者--所以我们需要把原本的值拷贝一份用于完成返回操作 Self operator(int){Self tmp(*this);_node _node-_next;return tmp;}Self operator--(int){Self tmp(*this);_node _node-_prev;return tmp;}
重载!、 bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
重载-
先来分析一下为什么需要重载-这个符号
接下来先构造一个使用-的情景
假设有一个这样的结构体 struct AA{int _aa1 1;int _aa2 2;};
此时我们要在链表中存入这个结构体并且打印 listAA ltaa;ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());ltaa.push_back(AA());listAA::iterator itaa ltaa.begin();while (itaa ! ltaa.end()){cout *itaa ;itaa;}cout endl; 此时运行以后发现编译不通过
这里面的itaa通过解引用会得到节点中的datadata的数据类型是T也就是自定义类型AA。因为没有重载流插入所以这里的自定义类型无法打印要想解决这个问题有两种方法
第一种方法给AA重载流插入
第二种方法逐一访问结构体中的元素 listAA::iterator itaa ltaa.begin();while (itaa ! ltaa.end()){cout (*itaa)._aa1 and (*itaa)._aa2 endl;itaa;}cout endl; 此时代码就成功运行了
但是这样写就很麻烦此时就可以重载-这个运算符这里先把代码写出来再对其进行分析 T* operator-(){return _node-_data;} listAA::iterator itaa ltaa.begin();while (itaa ! ltaa.end()){cout itaa-_aa1 and itaa-_aa2 endl;itaa;}cout endl; 疑难解答为什么operator- 操作符重载函数返回值 T* 而不是 T
在 list_iterator 这个迭代器类模板中operator- 操作符重载函数设计为返回 T* 而不是 T这与 operator- 操作符的特殊语义和 C 语言的规定有关
在 C 中operator- 操作符有特殊的处理规则。当我们使用 - 操作符时编译器会尝试不断应用 - 操作直到得到一个非指针类型的对象
简单地说就是当你使用迭代器 it 调用 it-member 时编译器会先调用 it.operator-()如果 operator-() 返回的是一个指针那么就直接访问该指针指向对象的成员如果返回的不是指针编译器会再次对返回值应用 -
我们可以分两点来说明返回 T* 的合理性
1. 符合使用习惯
迭代器的 operator- 操作符通常用于模拟指针的行为返回 T* 可以让迭代器像指针一样使用
例如对于一个存储自定义类型 MyClass 的链表使用迭代器访问 MyClass 的成员时我们希望能够像使用指针一样直接通过 - 操作符访问成员如下所示
namespace xiaobai
{templateclass Tstruct list_node{list_node(const T data T()): _data(data), _next(nullptr), _prev(nullptr) {}T _data;list_nodeT* _next;list_nodeT* _prev;};templateclass Tstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT Self;list_iterator(Node* node) : _node(node){}T operator*() {return _node-_data;}Self operator() {_node _node-_next;return *this;}bool operator!(const Self s) {return _node ! s._node;}T* operator-() {return _node-_data;}Node* _node;};
}int main()
{xiaobai::list_nodeMyClass node(MyClass(10));xiaobai::list_iteratorMyClass it(node);// 使用迭代器的 - 操作符访问成员std::cout it-value std::endl;return 0;
}
在这个例子中it-value 能够正常工作因为 operator-() 返回的是 MyClass* 类型的指针编译器可以直接通过该指针访问 value 成员
2. 避免额外的复杂度
如果 operator-() 返回 T编译器会再次对返回的引用应用 - 操作这会导致代码逻辑变得复杂而且可能不符合用户的预期
例如若T是一个自定义类型由于T不是指针类型编译器会尝试调用 T 类型的 operator-() 函数这可能会引发编译错误或意外的行为
所以T* operator-() 是为了让迭代器能够像指针一样使用符合用户的使用习惯并且遵循了 C 中 operator- 操作符的特殊语义。而 T operator-() 会破坏这种语义导致代码逻辑复杂且不符合预期因此通常不这样设计 这段代码初步看起来会很奇怪它这里实际应该是两个箭头但是为了可读性省略了一个箭头
具体细节请浏览上面的疑难解答
cout itaa.operator-()-_aa1 and itaa.operator-()-_aa2 endl;
第一个箭头是运算符重载返回的是AA*类型的变量
第二个箭头是原生指针通过这个箭头就可以访问到list中的数据了 迭代器代码初步集合
到这里我们就完成了迭代器 templateclass Tstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT Self;list_iterator(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 s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}T* operator-(){return _node-_data;}Node* _node;};
此时再去链表的类中typedef迭代器简化书写 templateclass Tclass list{public:typedef list_nodeT Node;typedef list_iteratorT iterator;//.......private:Node* _head;size_t _size;}; 重载打印容器以及对迭代器的修缮
实现了迭代器就满足了范围for遍历此时就可以写一个访问容器的接口因为所有容器都具有迭代器所以这个接口也可以访问其他STL容器 templateclass Containervoid print_container(const Container con){for (auto e : con){cout e ;}cout endl;}
现在测试一下这个打印 listint lt;ltaa.push_back(1);ltaa.push_back(2);ltaa.push_back(3);ltaa.push_back(4);print_container(lt);
此时运行代码却发现编译报错了为什么函数外面使用范围for可以打印但是print_container函数里面使用范围for却打印不了这是为什么呢
因为函数里面的参数是const参数函数外面是普通的参数我们还没有实现const迭代器所以这里就会报错
再来分析一下const迭代器的特征先思考一下const迭代器为什么是const_iterator而不是普通的iterator加上前置的const修饰?
要想想清楚这个问题我们首先需要明白const迭代器是自身不能修改还是指向的内容不能修改。这里我们结合指针不同位置的const意义来理解
T* const ptr;
const T* ptr;
第一种指针本身不允许改变
第二种指针指向的内容不允许改变
很明显的const迭代器是想完成第二种功能如果是const iterator的话const的作用是确保iterator本身不被修改迭代器本身不能修改的话就无法实现遍历。const迭代器的产生是为了在保证遍历的前提之下保证迭代器指向的内容也不被修改
那么该怎么修改代码来完成这一目的呢
我们在实现迭代器这一个类时对数据的修改接口是operator*以及operator-对于const迭代器而言返回类型就应该加上const const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}
所以这里就需要拷贝之前的普通迭代器代码再在*和-的重载中加上const完成const迭代器 templateclass Tstruct list_const_iterator{typedef list_nodeT Node;typedef list_iteratorT Self;list_iterator(Node* node):_node(node){}const 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 s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}const T* operator-(){return _node-_data;}Node* _node;};
此时在重载一下begin和end函数给一个const迭代器版本并且在list类中typedef const迭代器
普通迭代器可以调用const迭代器的begin和end因为权限可以缩小反之const迭代器无法调用普通迭代器的begin和end因为权限不能放大 templateclass Tclass list{public:typedef list_nodeT Node;typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;iterator begin(){return _head-_next;}iterator end(){return _head;}const_iterator begin() const{return _head-_next;}const_iterator end() const{return _head;}//........private:Node* _head;size_t _size;};**************************************************************************************************************
在 list 类中重载 begin 和 end 函数即提供 const 和非 const 版本是为了支持对 const 对象和非 const 对象的迭代操作下面详细解释原因
1. 支持非 const 对象的迭代
当你有一个非 const 的 list 对象时你可能希望能够修改列表中的元素。此时你需要使用非 const 迭代器因为非 const 迭代器允许对其所指向的元素进行修改。非 const 版本的 begin 和 end 函数返回的就是非 const 迭代器
2. 支持 const 对象的迭代
当你有一个 const 的 list 对象时你不应该修改列表中的元素因为这违反了 const 限定的语义。此时你需要使用 const 迭代器const 迭代器只能用于访问元素而不能修改元素。const 版本的 begin 和 end 函数返回的就是 const 迭代器
3. 函数重载的实现
通过函数重载编译器会根据对象是否为 const 来选择合适的 begin 和 end 函数版本。如果对象是 const 的编译器会调用 const 版本的 begin 和 end 函数返回 const 迭代器如果对象是非 const 的编译器会调用非 const 版本的 begin 和 end 函数返回非 const 迭代器。
重载 begin 和 end 函数是为了提供对 const 对象和非 const 对象的一致迭代接口同时保证 const 对象的元素不被意外修改遵循了 C 的 const 正确性原则使得代码更加安全和灵活。
************************************************************************************************************** 此时用一个很特别的用例来测试一下代码这里修改了一下print_container函数 templateclass Containervoid print_container(const Container con){listint::const_iterator it con.begin();while(it ! con.end()){*it 10;cout *it ;it;}cout endl;for (auto e : con){cout e ;}cout endl;}void test_list01(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;} 可以看到这里非常奇怪明明我们故意在打印容器代码里面修改了const迭代器指向的内容想让它报错但是代码却成功运行了这是为什么呢
这就涉及到我们之前提及的按需实例化这里的代码存在着编译错误 *it 10 中的*it返回的数据类型应该是const T对其进行10操作本身是应该编译报错的但是这里非但没有报错反而还运行成功了
之所以产生这样的结果是因为模板和类模板都会走按需实例化。模板不能被直接调用模板用于将对应类型的代码实例化出来实例化出来的代码才能够使用
因为我们在主函数中没有使用print_container函数编译器在编译的过程中就不会去实例化print_container函数里面的内容而没有实例化的代码编译器只会对其进行很简单的语法检查比如语句结束没加分号对于细枝末节的操作编译器不会检查。
此时如果使用print_container函数就会报错 listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;print_container(lt); 对迭代器代码的简化
刚才那种实现方式我们的确能成功的完成任务但是const迭代器和普通迭代器除了operator*和-的代码有区别以外其他地方的代码一模一样这么设计的话在代码长度上就会非常的冗余我们去底层观察一下是怎么实现迭代器的 可以看到它没有将迭代器和const迭代器定义为两个类而是同一个类模板。而且它除了传入了 T 还传入了 T 和 T* 这两个参数
如果是普通迭代器它的中的参数是 T T T* 分别传给了参数 T Ref Ptr 而 Ref 和 Ptr 分别被重命名为 reference 和 pointer 而 reference 和 pointer 分别又是 operator* 和 operator- 的返回值
如果是const迭代器它的中的参数是 T 、const T、 const T* 分别传给了参数 T Ref Ptr Ref 和 Ptr 分别被重命名为 reference 和 pointer 而 reference 和 pointer 分别又是 operator* 和 operator- 的返回值
通过这种形式就控制住了operator*和-的返回值
虽然这两种写法在本质上没有区别只是之前的写法是自己写了两个类而这种方法是实现了一个类模板并且传了不同的模板参数给编译器通过编译器来实例化出两个类。通过这样的方法我们就可以实现精简代码的需求
那么就根据底层实现的原理来完善一下原来的代码吧 templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}//.......Node* _node;};templateclass Tclass list{public:typedef list_nodeT Node;typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;//.......private:Node* _head;size_t _size;}; 迭代器代码的最终整合 templateclass T, class Ref, class Ptrstruct list_iterator{typedef list_nodeT Node;typedef list_iteratorT, Ref, Ptr Self;list_iterator(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 s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}Ptr operator-(){return _node-_data;}Node* _node;}; begin、end函数
begin函数用于返回链表第一个元素 iterator begin(){iterator it(_head-_next);return it;}
也可以用返回匿名对象来简化代码 return iterator(_head-_next);
还有一种更加简单的写法 return _head-_next;
因为这里返回的是一个节点的指针节点的指针是可以隐式类型转换成iterator的单参数的构造函数支持隐式类型的转换 end函数同理 iterator end(){return _head-_prev;} 到这里我们来测试一下 listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl; 这里迭代器的设计相当完美假设链表为空此时就只有一个哨兵位的头节点。由于begin是_head的next此时它指向的还是自己。end是_head也同样指向自己此时it begin() end在条件判断的时候就不会进入循环造成非法访问
我们在实现迭代器的时候没有写拷贝构造函数这就意味着指针在与指针的拷贝的时候进行的是浅拷贝那么浅拷贝会不会出现问题呢
答案是不会我们就以上面的测试代码为例我们给it赋了头节点此时我们期望的就是it也指向原来的头节点就是需要浅拷贝而不是开一个新的链表指向新的链表中的头节点
这里的迭代器只是一个访问和遍历链表的工具它不像vector、string等容器一样它所指向的资源并不是属于它自己的它指向的资源是属于list的。所以它也不要写析构函数它不能去释放list的空间 insert函数
insert函数用于在pos位置之前插入数据要想实现这个功能还是比较简单的仅需要通过简单的修改指针指向即可 void insert(iterator pos, const T x){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(x);newnode-_next cur;cur-_prev newnode;newnode-_prev prev;prev-_next newnode;} push_back和push_front函数
可以通过复用insert函数完成这两个函数 void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);} erase函数
erase函数用于删除pos位置的节点这个函数的实现也很简单也是只需要修改指针指向再释放节点即可
注意erase不能删除哨兵位的头节点在这里加上assert断言 void 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;} pop_back和pop_front函数
通过复用erase即可实现这两个函数 void pop_back(iterator pos){erase(--end());}void pop_front(iterator pos){erase(begin());}
结尾
因为链表很多接口的实现非常简单这里就没有把所有接口的实现代码一一列举出来了下一节我们接着分析链表我们将会分析迭代器失效并且完善list。那么本节的内容就到此结束了谢谢您的浏览
