编织网站建设,虾皮这种网站根本不值得做,一网通办 上海,四川建设厅官方网站查询目录
一、list和vector区别
二、list模拟实现过程
1. 构造函数
2. 尾插 push_back
3. 迭代器
4. 任意位置插入 insert
5.删除指定位置的节点 erase
6. 复用
7. 链表节点个数
8. 析构函数
9. 拷贝构造函数
10. 赋值运算符重载
11.多参数构造 正文#xff1a; 本次…目录
一、list和vector区别
二、list模拟实现过程
1. 构造函数
2. 尾插 push_back
3. 迭代器
4. 任意位置插入 insert
5.删除指定位置的节点 erase
6. 复用
7. 链表节点个数
8. 析构函数
9. 拷贝构造函数
10. 赋值运算符重载
11.多参数构造 正文 本次list详解主要放在迭代器和类封装部分特别是迭代器。
一、list和vector区别
1在两者的底层数据结构中
vector动态数组元素在内存中连续存储。
list双向链表元素通过指针非连续存储每个节点包含前驱和后继指针。
2迭代器支持
vector支持随机访问迭代器可跳跃访问。
list仅支持双向迭代器只能逐元素移动。
3内存占用
vector内存紧凑仅存储元素缓存友好预取效率高。
list每个元素额外占用两个指针空间前驱/后继内存碎片可能更多。
4使用场景
选择vector1需要频繁随机访问2 内存连续性对性能关键如缓存优化3尾部操作为主中间插入较少。
选择list1避免扩容导致的开销或迭代器失效2不需要随机访问3频繁在任意位置插入/删除。
二、list模拟实现过程
list带头双向循环链表底层是由一个一个节点构成。
可以理解为有多个节点再把节点串起来就形成链表。list 类的成员变量通常是一个节点类型的头指针_head指向链表的首节点通过不断插入节点和更改指针之间指向形成一个链表结构而每个节点是一个独立单元通常包含数据部分存储元素值、前驱指针、后继指针在 C 实现中节点用类实现。
list类模版如下
节点的类模板用struct可以直接访问内部数据模版一般声明定义不分离。外部包了一层zss命名空间防止在大项目中因命名冲突引发报错 1. 构造函数
目的是对list进行初始化由于后面可能出现单独调用初始化功能所以将初始化的步骤单独提出写成一个函数让构造函数内部调用实现初始化。
目前实现的链表是带头链表创建链表第一步是开一个Node大小的空间作为哨兵节点当没有节点插入时它的前驱和后继都是指向自己已通过typedef把节点模版命名为Node 接下来实现的方法除非有特别声明位置不然都在public下
2. 尾插 push_back
链表的底层是节点尾插一个数得创建一个节点把这个数存到节点中才能插入。 3. 迭代器
迭代器本质:不暴露容器底层结构用户不需要关心底层结构让使用变得简单
在vector中迭代器的底层结构是原生指针int* 但是list不能直接用node*
因为node*解引用后是节点不是数据达不到我们要的效果。需要用一个类去封装节点指针然后进行运算符的重载按我们要求实现。 迭代器的类型分为普通迭代器、const迭代器、反向迭代器
本次以普通迭代器和const迭代器为主const迭代器并不是在函数名前面加个const就行这样const修饰的是函数本身不能修改我们需要函数的内容不修改本身可以改变。所以要同时实现两个迭代器类模版如下图
两个迭代器模版只有名字不同其他重复度太高因此可合成一个模版。通过参数不同来判断调什么类型迭代器。 使用同一个模版后
先定造一个迭代器模版迭代器本质是封装了节点指针的类通过运算符重载模拟指针行为。
使用 Ref引用和 Ptr指针模板参数统一普通迭代器和 const 迭代器的实现。 list 类通过 typedef 定义迭代器类型并暴露 begin()/end() 接口。 为什么 operator- 返回 Ptr指针 为了支持 it-method() 的语法编译器会隐式转换为 Ptr-method()。
4. 任意位置插入 insert
只要插入就要创建节点改变指向逻辑。 5.删除指定位置的节点 erase
由于编译器的强制机制erase后的迭代器可能失效所以要更新一下迭代器erase后返回pos位置的下一个迭代器。
删除节点之前要先把指针指向调整好为了防止调整过程中的思维混乱通过定义变量记录下每个节点。 6. 复用
头插、尾插、头删、尾删的复用插入、删除和迭代器功能都已经实现这几个就可巧妙复用。 7. 链表节点个数
由于有成员变量_size插入删除中都有对应/--当要求链表节点个数时直接返回就行。 8. 析构函数
在对整个链表析构前要先清空数据链表的数据是节点清空数据的方法可能被单独调用所以提取出来写成一个clean()函数。clean后再删除头结点将其置空。
clean内部直接复用erase进行链表中节点数据的清理由于上面提到erase后迭代器会失效所以然it重新赋值一下erase的返回值。 9. 拷贝构造函数
此处就体现了文章开头为什么要把初始化方法单独写成一个函数而不是在构造函数中实现的重要性因为在拷贝构造中就出现被单独调用了
拷贝构造用一个已存在的对象listT lt 构造一个新对象。可以直接巧妙用范围for遍历 lt 对象然后尾插形成新对象。 10. 赋值运算符重载
此处建议用现代写法通过浅拷贝传参lt里面就是我想要的数据利用swap直接将数据交换给自己函数运行结束后lt会自动销毁。 11.多参数构造
这个是C11中的一种构造方式。
initializer_list允许用花括号 {} 初始化对象如容器、自定义类。
头文件#include initializer_list 以上十几点就是list的一些比较常用的方法实现小伙伴们要是有兴趣可以对应去看一下list的原码和一些更详细的方法。下面把整个list实现代码附上
#pragma once
#includeiostream
#includeassert.h
#includealgorithm
#includevector
using namespace std;namespace zss
{templateclass Tstruct list_Node{list_NodeT* _next;list_NodeT* _prev;T _date;//拷贝构造list_Node(const T x T()):_next(nullptr), _prev(nullptr), _date(x){}};//3.迭代器templateclass T,class Ref,class Ptrstruct list_iterator{//迭代器本质还是节点typedef list_NodeT Node;typedef list_iteratorT, Ref, Ptr Self;Node* _node;list_iterator(Node* node):_node(node){}//解引用Ref operator*(){return _node-_date;}Ptr operator-(){return _node-_date;}//迭代器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 it){return _node ! it._node;}bool operator(const Self it){return _node it._node;}};template class Tclass list{typedef list_NodeT Node;public:/*typedef list_iteratorT iterator;typedef list_const_iteratorT const_iterator;*/typedef list_iteratorT,T,T* iterator;typedef list_iteratorT, const T, const T* const_iterator;//普通迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//const迭代器const_iterator begin()const{return const_iterator(_head-_next);}const_iterator end()const{return const_iterator(_head);}//1.构造函数void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}//19.拷贝构造lt2(lt1)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}//10.赋值重载:lt1 lt3void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}listT operator(listT lt){//超绝现代写法swap(lt);return *this;}//11.多参数构造list(initializer_listT lt){//凡是链表的构造先想是否可以范围for尾插实现empty_init();for (auto e : lt){push_back(e);}}//8.析构~list(){//先清数据再删节点clear();delete _head;_head nullptr;}//清理数据函数可能单独调用void clear(){iterator it begin();while (it ! end()){//迭代器失效更新it erase(it);}}//2.push_backvoid push_back(const T x){//先建个节点/*Node* newnode new Node(x);Node* tail _head-_prev;tail-_next newnode;newnode-_next _head;_head-_prev newnode;*///复用大法insert(end(), x);}//4.增insertvoid insert(iterator pos,const T x){//先创个节点出来Node* newnode new Node(x);//改变指向逻辑Node* cur pos._node;Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;_size;}//5.删eraseiterator erase(iterator pos){//断言防止把头删了assert(pos ! end());Node* cur pos._node;//改变指向逻辑Node* prev cur-_prev;Node* newpos cur-_next;prev-_next newpos;newpos-_prev prev;--_size;delete cur;//迭代器失效问题所以返回pos的下一个位置return iterator(newpos);}//6.复用void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}void pop_back(){erase(--end());}//7.sizesize_t size(){return _size;}private:Node* _head;size_t _size;};
}
文章中有理解错误、文字错误欢迎指出
list的方法实现1-11并不是固定的顺序~ 完结~感谢观看
