济南做网站的中企网站设计制作是什么

当前位置： 首页 > news >正文

济南做网站的中企,网站设计制作是什么,检测站营销方案,徐州比居网络科技有限公司从此音尘各悄然 春山如黛草如烟 目录 list 的结点设计 list 的迭代器 list 的部分框架 迭代器的实现 容量相关相关函数 实现 insert 在指定位置插入 val 实现 push_back 在尾部进行插入 实现 erase 在指定位置删除 实现 pop_back 在尾部进行删除 实现 list 的头插、头删 实现… 从此音尘各悄然 春山如黛草如烟 目录 list 的结点设计 list 的迭代器 list 的部分框架 迭代器的实现  容量相关相关函数 实现 insert 在指定位置插入 val 实现 push_back 在尾部进行插入 实现 erase 在指定位置删除 实现 pop_back 在尾部进行删除 实现 list 的头插、头删  实现 list 的访问首末元素 实现 list 的清空 clear 实现 list 的迭代器构造 list 的拷贝构造 list 的赋值构造 list 的链式构造 list 的 n 个 val 构造 全部代码展示 契子✨ 上篇我们已经实现了 vector 的部分接口相较于 vector 的连续空间list 就显得复杂的多。主要体现在其迭代器的实现上 我们知道  vector 的空间是连续的所以我们可以直接对原生指针进行操作例如只需 就可以访问当前空间的下一个位置。而 list 因为空间是不连续的所以我们不能直接使用 等迭代器的相关操作必须对迭代器进行重新封装 list 的优点每次安插或者删除一个元素就配置或者释放一个元素的空间。因此 list 对空间的利用率有绝对的精华一点都不浪费。而且对任何位置的元素安插或者元素移除list 永远都是常数时间 list 的结点设计 学过数据结构的我们知道list 的本身与 list 的结点是不同的结点需要分开设计 就是以下的设计设置一个节点的前驱与后继指针、数据域 因为 list 支持所有类型所以我们使用模板即可 ~ 由于我们想要实现默认构造可以由匿名对象 T() 来实现这个效果 T() 如果是自定义类的变量就会自动调用 T类型 的构造函数创造一个匿名对象并用其为给引用 val 做初始化。因为 val 是一个 const 类的引用所以它可以延长匿名对象的生命周期简单来说 const 与 非const 对象都可以使用 templateclass Tstruct ListNode{ListNode(const T data T()):_prev(nullptr),_next(nullptr),_data(data){}ListNodeT* _prev;ListNodeT* _next;T _data;}; ✨ 关于这里为什么用 struct 而不用我们 C 常用的 class因为 struct  没有类域的限制外部能够直接访问而 class 默认就是 private 修饰外部不能直接访问。但是我们 list 的操作需要频繁访问类中成员比如修改结点指向、访问数据域等。虽然我们 calss 可以用 public 进行修饰但是我们 C 的编程习惯就是需要频繁访问的类直接用 struct 就可以了 – 直接访问 list 的迭代器 list 不能够像 vector 一样以原生指针作为迭代器因为其结点不保证在存储空间中连续存在。而 list 迭代器必须具备指向 list 结点并有能力做正确的自增、自减、取值、成员取用等操作。简单来讲就是自增时指向下一个结点自减时指向上一个结点取值时就是访问当前结点的数据域 data 相当于成员取用相当于- 那么我们该如何实现这样看起来很复杂的迭代器呢 我们可以对 list 迭代器的性质进行分装 迭代器的性质在 vector 中我们知道顺序表扩容会导致迭代器失效因为 vector 会导致空间的重新配置。而我们的 list 的扩容操作相当于插入结点这样并不会导致迭代器失效哦 ~ 例如push_back、insert 等操作。但是注意list 的删除操作erase也只有 [被指向删除元素] 的那个迭代器失效其他迭代器不受影响 ~ 废话不多说 ~ 让我们看看怎么实现的 templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr self;Node _node; //迭代器內部当然要有一个原生指针指向 list 的结点ListIterator(Node* node):_node(node){}bool operator(const self x){return _node x._node;}bool operator!(const self x){return _node ! x._node;}//取节点的资料–数据域Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}//自增就是访问下一个结点self operator(){_node _node-_next;return *this;}self operator(int){self tmp *this;*this;return tmp;}//自减就是回退到上一个结点self operator–(){_node _node-_prev;return *this;}self operator–(int){self tmp *this;–this;return tmp;}}; 可能有老铁会问 ~ 为什么我们的模板有三个参数 templateclass T, class Ref, class Ptr 因为我们要设置两个迭代器 const 与 非const  一个模板参数来写的话可以这样 ~ templateclass Tstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT Self;Node _node;ListIterator(Node* node):_node(node){}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;}T operator(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}}; 不过还需在写一个 const 的版本不过我们用三个模板参数就可以避免这个问题 因为只有、-这两种运算符重载需要的返回值不同所以我们只需要针对这两个返回值设置两个模板进行替换即可就像以上操作 这样我们的迭代器已经封装好了接下来我们在具体实现 list 的功能了 list 的部分框架 因为 list 不仅是一个单向的串列而是一个环状单向串列双向链表所以它只需一个指标 _head 便可以完整的表示整个串列 templateclass Tclass list{typedef ListNodeT Node;public:typedef ListIteratorT, T, T iterator;typedef ListIteratorT, const T, const T* const_iterator;void empty_initialize(){_head new Node();_head-_prev _head;_head-_next _head;}//构造函数list(){empty_initialize();}//析构函数~list(){Node* cur _head;while (cur ! _head){Node* next cur-_next;delete cur;cur next;}delete _head;cur _head nullptr;}private:Node* _head;};可能有老铁会问 ~ 为什么我们要用一个函数 empty_initialize() 进行构造原因是我们以后还需要复用所以写成一个函数效率高 指针 _head 相当于我们双向循环链表的哨兵位我们只要让它刻意的指向尾端的一个空白结点便能符合 STL 对 [前闭后开] 的区间要求成为 end() 迭代器而只需从 _head 的下一个结点开始就可以成为 begin() 迭代器 迭代器的实现  iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}然后一些 ~ 相关的接口函数就一并写在这里 容量相关函数 bool empty() const { return _head-_next _head;}size_t size() const{size_t count 0;Node* cur _head-_next;while (cur!_head){cur cur-_next;count;}return count;} 怎么样 ~ 学到这里有没有难住各位老铁们呢 实现 insert 在指定位置插入 val 上图模拟了安插 新结点99 在 结点3 的位置上简单来说 insert 就是插入指定位置之前的位置 虽然我们之前说过 insert 的操作并不会使迭代器失效但是为了使 STL 其中的容器接口统一还是要更新一下迭代器的位置 iterator insert(iterator pos, const T val){Node* cur pos._node;Node* prev cur-_prev;Node* newNode new Node(val);prev-_next newNode;newNode-_next cur;newNode-_prev prev;cur-_prev newNode;return newNode;} 既然写出来了那么最好的验证方法就是测试以下先来测试以下以上的案例 但是呢 ~ 我们的迭代器不支持 哦STL库没有提供 不过呢我们可以借助 find()  不过这个 find() 需要我们自己在库中实现呢 iterator find(iterator first, iterator last, const T val){while (first ! last) {if (first val) return first;first;}return last;} 给两个迭代器的区间范围进行查找并返回查找位置的迭代器即可 我们再来测试一下 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3); str.push_back(4); for (auto i : str){cout i ;}cout endl;listint::iterator it str.find(str.begin(), str.end(), 3);if(it ! str.end())str.insert(it, 99);for (auto i : str){cout i ;}cout endl; } 实现 push_back 在尾部进行插入 因为我们的 insert() 已经完成啦 ~ 所以这里就可以选择直接复用 void push_back(const T val){insert(end(), val);} 当然你想自己写也可以 ~ void push_back(const T val){Node newNode new Node(val);Node* tail _head-_prev;tail-_next newNode;newNode-_prev tail;_head-_prev newNode;newNode-_next _head;} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3); str.push_back(4); for (auto i : str){cout i ;}cout endl; } 实现 erase 在指定位置删除 移除元素对于我们来说还是比较简单的就如下图移除 结点元素1 一样只需找到删除当前的前驱与后继结点然后两个结点相互牵手并与删除结点断掉联系然后 delete 掉删除结点即可 注意需要好好的断言一下哦 ~  不要删到最后出现乱码 因为 erase 操作导致被删除的那个结点的迭代器失效了为了保证迭代器的正确性我们需要提供被删除结点的下一个位置的迭代器 – 才能使迭代器完好 iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;cur nullptr;return next;} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3); str.push_back(4); for (auto i : str){cout i ;}cout endl;listint::iterator it str.find(str.begin(), str.end(), 1);if (it ! str.end())str.erase(it);for (auto i : str){cout i ;}cout endl; } 实现 pop_back 在尾部进行删除 既然我们已经写好 erase 那么们能复用就复用吧 void pop_back(){erase(–end());} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3); str.push_back(4); for (auto i : str){cout i ;}cout endl;str.pop_back();str.pop_back();for (auto i : str){cout i ;}cout endl; } 实现 list 的头插、头删  有道是 能复用绝不会自己写 void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}push_front、pop_front 完全可以借助我们前面的 insert、erase 的操作可以偷懒何乐而不为呢 代码测试 void Test_List() {listint str;str.push_front(0);str.push_front(1);str.push_front(2);str.push_front(3);str.push_front(4);for (auto i : str){cout i ;}cout endl;str.pop_front();str.pop_front();for (auto i : str){cout i ;}cout endl; }实现 list 的访问首末元素 list 底层使用的空间是不连续的因此不能像 vector 那样能依靠下标直接访问空间中的元素 list 中只有首元素和尾元素可以直接访问因为他们都是和头结点直接接触的而其他结点的访问需要遍历链表因此 C 中只给出了首元素和尾元素的访问函数如果要访问其他元素则需要用户自己去遍历 获取首元素 front T front() {assert(size() ! 0);return _head-_next-_data;}const T front()const {assert(size() ! 0);return _head-_next-_data;} 获取末元素 back T back() {assert(size() ! 0);return _head-_prev-_data;}const T back()const {assert(size() ! 0);return _head-_prev-_data;} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);for (auto i : str){cout i ;}cout endl;cout str.front() endl;cout str.back() endl; } 实现 list 的清空 clear 学过之前的知识我们都知道 clear 具有清空的功能而我们链表可以循环删除来实现这个操作不过要注意更新迭代器哦 ~ void clear(){auto it begin();while (it ! end()){it erase(it);}} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);for (auto i : str){cout i ;}cout endl;str.clear();for (auto i : str){cout i ;}cout endl; } 我们的 clear 操作也可以运用到我们的析构函数中 ~list(){clear();delete _head;_head nullptr;} 实现 list 的迭代器构造 与我们之前写的 vector 一样都有一个迭代器构造简单来说也就是说对于一个已经由 list 实例化的 str 可以通过迭代器区间帮助还未初始化的 arr 初始化 首先构造一个 list 的对象再将已知对象的迭代器区间结点尾插到我们需要初始化的对象上 template class Iteratorlist(Iterator first, Iterator last){empty_initialize();while (first ! last){push_back(*first);first;}} 我们浅浅的测试一下 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);for (auto i : str){cout i ;}cout endl;listint arr(str.begin(), –str.end());for (auto i : arr){cout i ;}cout endl; } list 的拷贝构造 在写 list 之前呢 ~ 我们先来实现一下 swap 交换函数吧 void swap(listT li){std::swap(li._head, _head);} 我们实现 list 的拷贝一般都是深拷贝拷贝的空间地址与原空间不一样 所以先构造一个对象在复用我们的迭代器构造最后让我们的 *this 与之交换即可 list(const listT li){empty_initialize();listT tmp(li.begin(), li.end());swap(tmp);} 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);for (auto i : str){cout i ;}cout endl;listint arr(str);for (auto i : arr){cout i ;}cout endl; } 通过调试我们可以看到两块空间的地址是不一样的说明我们的深拷贝是没有问题的 老铁们学废了吗  list 的赋值构造 listT operator(listT li){swap(li);return *this;} 赋值拷贝呢 – 我们可以通过传值的技巧来解决传值传参调用拷贝构造构造出一个临时对象然后将我们的 this 与之交换即可 代码测试 void Test_List() {listint str;str.push_back(0);str.push_back(1);str.push_back(2);str.push_back(3);str.push_back(4);for (auto i : str){cout i ;}cout endl;listint arr;arr str;for (auto i : arr){cout i ;}cout endl; } list 的链式构造 list(initializer_listT il){empty_initialize();for (const auto i : il){push_back(i);}} 代码测试 void Test_List() {listint arr { 1,2,3,4,5,6 };for (auto i : arr){cout i ;}cout endl; } list 的 n 个 val 构造 list(size_t n, const T val T()){empty_initialize();for (size_t i 0; i n; i){push_back(val);}}list(int n, const T val T()){empty_initialize();for (size_t i 0; i n; i){push_back(val);}} 关于我们为什么要写 int 类型的重载可以看看我的上篇文章 因为编译器会调用更匹配的函数 ~ 比如那个迭代器的构造就很合适为了避免这种情况我们选择重载 int 代码测试 void Test_List() {listint arr(10, 1);for (auto i : arr){cout i ;}cout endl; } list 的结构除了迭代器以外 其实与 vector 蛮相似的 全部代码展示 #includeassert.h #includelist using std::initializer_list; namespace Mack {templateclass Tstruct ListNode{ListNode(const T data T()):_prev(nullptr),_next(nullptr),_data(data){}ListNodeT _prev;ListNodeT* _next;T _data;};templateclass T, class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr self;Node* _node;ListIterator(Node* node):_node(node){}bool operator(const self x){return _node x._node;}bool operator!(const self x){return _node ! x._node;}Ref operator*(){return _node-_data;}Ptr operator-(){return (_node-_data);}self operator(){_node _node-_next;return *this;}self operator(int){self tmp *this;*this;return tmp;}self operator–(){_node _node-_prev;return *this;}self operator–(int){self tmp *this;–this;return tmp;}};templateclass Tclass list{typedef ListNodeT Node;public:typedef ListIteratorT, T, T iterator;typedef ListIteratorT, const T, const T* const_iterator;template class Iteratorlist(Iterator first, Iterator last){empty_initialize();while (first ! last){push_back(*first);first;}}void swap(listT li){std::swap(li._head, _head);}list(const listT li){empty_initialize();listT tmp(li.begin(), li.end());swap(tmp);}listT operator(listT li){swap(li);return *this;}void empty_initialize(){_head new Node();_head-_prev _head;_head-_next _head;}list(){empty_initialize();}~list(){clear();delete _head;_head nullptr;}list(initializer_listT il){empty_initialize();for (const auto i : il){push_back(i);}}list(size_t n, const T val T()){empty_initialize();for (size_t i 0; i n; i){push_back(val);}}list(int n, const T val T()){empty_initialize();for (size_t i 0; i n; i){push_back(val);}}iterator begin(){return iterator(_head-_next);}const_iterator begin() const{return const_iterator(_head-_next);}iterator end(){return iterator(_head);}const_iterator end() const{return const_iterator(_head);}void push_back(const T val){insert(end(), val);}iterator find(iterator first, iterator last, const T val){while (first ! last) {if (first val) return first;first;}return last;}iterator insert(iterator pos, const T val){Node cur pos._node;Node* prev cur-_prev;Node* newNode new Node(val);prev-_next newNode;newNode-_next cur;newNode-_prev prev;cur-_prev newNode;return newNode;}void pop_back(){erase(–end());}iterator erase(iterator pos){assert(pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;cur nullptr;return next;}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}bool empty() const { return _head-_next _head;}size_t size() const{size_t count 0;Node* cur _head-_next;while (cur!_head){cur cur-_next;count;}return count;}T front() {assert(size() ! 0);return _head-_next-_data;}const T front()const {assert(size() ! 0);return _head-_next-_data;}T back() {assert(size() ! 0);return _head-_prev-_data;}const T back()const {assert(size() ! 0);return _head-_prev-_data;}void clear(){auto it begin();while (it ! end()){it erase(it);}}private:Node* _head;};} 有不对的地方欢迎指出 ~ ✨