龙华区城市建设局网站,wordpress更换域名后台登不进去,常平镇网站仿做,广告设计宣传画册list容器模拟实现函数解析 文章目录list容器模拟实现函数解析一、list容器使用介绍二、list容器模拟实现及函数解析2.1 list结构体创建2.2 迭代器封装2.21 构造函数#xff1a;2.22 前置和后置及- -2.23 解引用2.24 判断相等2.25 箭头重载2.26 第二个和第…list容器模拟实现函数解析 文章目录list容器模拟实现函数解析一、list容器使用介绍二、list容器模拟实现及函数解析2.1 list结构体创建2.2 迭代器封装2.21 构造函数2.22 前置和后置及- -2.23 解引用2.24 判断相等2.25 箭头重载2.26 第二个和第三个模板参数以应对const情况2.3 在pos位置插入2.4 头插2.5 尾插2.6 删除pos位置2.7 尾删2.8 头删2.9 析构和清理函数3.1 swap交换函数3.2 拷贝构造函数3.3 使用迭代器进行初始化构造3.4 构造的list中包含n个值为val的元素3.5 赋值重载函数三、list迭代器失效四、list模拟实现代码(1)simulate_list(2)test.cpp(3)测试结果五、vector和list容器对比六、总结与补充一、list容器使用介绍
(1)list介绍:
概念 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list指针使用类来封装的。 对比 list与forward_list非常相似最主要的不同在于forward_list是单链表只能向前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第1个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息。 (2)list使用
1.list的构造 list (size_type n, const value_type val value_type()) 构造的list中包含n个值为val的元素。 list() 构造空的list。 list (const list x) 拷贝构造函数。 list (InputIterator first, InputIterator last) 用[first, last)区间中的元素构造list。 2.list iterator 起始终止使用 begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器。 rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的reverse_iterator,即begin位置。 3.list增删查改 push_front 在list首元素前插入值为val的元素 pop_front 删除list中第一个元素 push_back 在list尾部插入值为val的元素 pop_back 删除list中最后一个元素 insert 在list position 位置中插入值为val的元素 erase 删除list position位置的元素 swap 交换两个list中的元素 clear 清空list中的有效元素 find 查找这个是算法库函数里的不是容器接口 4.list空间增长和个数接口 size 获取数据个数 capacity 获取容量大小 empty 判断是否为空 resize 改变vector的size reserve 改变vector的capacity 二、list容器模拟实现及函数解析
2.1 list结构体创建 templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _data;list_node(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};
因为它是一个带头的双向循环链表里面啊穿件一个next指针和一个前驱指针以及数据data变量并在里面构建默认构造函数里面提供匿名对象因为有可能传的是自定义类型。
2.2 迭代器封装
这里的list迭代器本质上是自定义类型对原生指针的封装模拟指针的行为因为list物理结构是不连续的啊迭代器有或者–这时候需要对它进行重新定义需要进行运算符重载。为了它行为像指针一样只能通过一个类来描述它。所以list的迭代器是一个类对象这里为了能直接访问我们用struct来定义类。 先拿取部分代码如下
templateclass T,class Cst,class Pstruct list_iterator{typedef list_nodeT node;typedef list_iteratorT,Cst,P self;node* _node;list_iterator(node* n):_node(n){}P operator-(){return (_node-_data);}Cst 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;}};templateclass Tclass list{typedef list_nodeT node;public:typedef list_iteratorT,T,T* iterator;typedef list_iteratorT, const T,const T* const_iterator;list(){_head new node;_head-_next _head;_head-_prev _head;}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);}}在代码里面无论是返回类型还是创建的临时变量都需要写一个很长的一个类型名为了使用方便在list中把list中的结点结构体类型list_nodeT和普通迭代器list_iteratorT,T,T* 及const迭代器list_iteratorT, const T,const T*还有迭代器中的list_nodeT和list_iteratorT,Cst,P进行重定义。增加的另外俩个模板参数下面会分析。
2.21 构造函数
里面必须得有构造函数因为编译器自动生成的满足不了我们的需求。要把_node初始化为我们想要的。
2.22 前置和后置及- -
前置返回的是加加后的结果直接先更新_node,再直接返回this指向的内容因为这里的迭代器不会销毁用引用返回。返回的还是一个迭代器直接替换为self。下面也同理。 后置返回的是加加之前的结果所以需要一个临时变量存放之前的结果然后再进行加加。因为这里是一个临时对象出了作用域会销毁所以这里使用引用返回。 前置- -和后置- -出了更新不同它使用的是前驱指针其他逻辑和相同。
2.23 解引用
解引用就直接返回它的数据由于以后会对list中的数据进行访问所以这要引用返回T。
2.24 判断相等
直接返回的时候 判断相等也就是this指向的迭代器和右面传回来的迭代器进行比较。
2.25 箭头重载
普通指针原生指针内置类型的指针就用解引用就可以如果是实例化一个结构体打印的时候自定义类型还需要流插入运算符重载如果是私有必选重载现在里面是公有不想重载这就要用到箭头所以在迭代器里面重载一个operator箭头打印写的时候只需要写一个箭头是了为了提高可读性编译器进行了简化省略一个箭头。 而箭头访问成员变量左面必须得是指针也就是结构指针访问成员而*.是用于结构体变量访问成员在迭代器箭头重载里面通过箭头拿到数据再引用拿到数据的地址即可再加上编译器的增加箭头就可访问具体成员。
2.26 第二个和第三个模板参数以应对const情况
第一个模板参数 使用begin函数时候如果是const对象的时候会发生什么比如下面代码
void input_list(const nza::listint v)
{nza::listint ::iterator p v.begin();while (p ! v.end()){(*p) * 2;cout *p ;p;}cout endl;
}这里编译报错这里权限放大对象调用成员函数得传递this指针这地方的对象是const取地址是const list int* 不能传给普通的this。这里要重载两个函数在beginend成员函数后面加const。就能编译成功。 iterator begin()const{return iterator(_head-_next);}为什么const能构造普通的迭代器按理说这里加了const后它所指向内容就不能修改这里变成可读可写的普通迭代器了但迭代器所因为这里的const修饰的this即this指向的内容它指向的内容是_head指针修饰的是_head指针本身也就是说在const情况下修饰的是_head不能被改变并不是_head指向的内容不能改变所以这个结点的指针是它本身不能改变但是能拷贝给别人。 这里的记结果最终不仅能遍历还能修改它的数据能修改就是因为构造了普通迭代器普通迭代器是可读可写的。 解决 库里面是这样做的如果是一个const对象的时候对它进行了限制const对象调用的是const begin返回的是一个const迭代器。 const迭代器和普通迭代器的区别是指针指向的内容不可修改不能用typedef const iterator const_iterator 这就相当于const修饰的是迭代器这个类而成员变量不可修改成员变量是指针普通跌迭代器相当于T而上面的是相当于T* const这个意思是保证迭代器本身不会被修改内容可修改我们想要的是指向的内容不可修改。
只需要在解引用前面加上const控制这个返回值不一样但是不能在同一个类中增加一个const 函数因为返回类型不同不能重载这时候思路是再创建一个const_iterator迭代器但是又太冗余。
这时候为了使代码更简洁使代码适应性更强在迭代器的类模板增加一个模板参数Cst而在list类中给迭代器类不同类型的模板的参数如果是普通迭代器传T如果是const迭代器就传const。使用哪种迭代器就会使用哪种模板参数进行实例化就是用这个类型的时候编译器就会把T替换对应的类型。 第三个模板参数 在箭头运算符重载函数中返回类型是T*如果来一个const对象继续使用不符合const的性质const T 类型无法构成重载所以在迭代器模板参数里面再增加一个参数P就能解决把T换成P在list把iteratorconst_iterator分别增加一个T和一个const T就能解决让编译器根据具体情况去实例化
2.3 在pos位置插入 void insert(iterator pos,const T x){node* cur pos._node;node* prev cur-_prev;node* Newnode new node(x);prev-_next Newnode;Newnode-_next cur;Newnode-_prev prev;cur-_prev Newnode;}如果不用struct用class 去加私有封装在这要么用友元要么getnode所以迭代器一般用struct在里面用这个迭代器去取这个指针这里用pos迭代器取取出当前指针在pos前插入再定义一个前驱指针然后开一个结点进行链接。后面四部是链接过程。
2.4 头插 void push_front(const T x){insert(begin(), x);}直接复用插入函数就是在第一个结点的前面进行插入begin位置进行插入。
2.5 尾插 void push_back(const T x){/*node* newnode new node(x);node* tail _head-_prev;tail-_next newnode;newnode-_prevtail;newnode-_next _head;_head-_prev newnode;*/insert(end(), x);}这里可以用传统的方法也是直接复用插入函数就是在end的前面插入也即end指向前面的下一个。
2.6 删除pos位置 iterator erase(iterator pos){assert(pos!end());node* net pos._node-_next;node* prevpos._node-_prev;prev-_next net;net-_prev prev;delete pos._node;return iterator(net);}先加一个断言头结点不能删除。定义一个net指针表示当前位置的下一个位置再定一个前驱指针表示当前位置的前面的然后直接把它俩进行链接释放当前结点因为考虑到迭代器失效要给一个返回值也就是删除位置下一个结点不然无法遍历。
2.7 尾删 void pop_back(){erase(--end());}直接复用删除函数因为尾删删的是头结点上一个里面返回的是一个迭代器对象直接调用前置- -。
2.8 头删 void pop_front(){erase(begin());}也是复用删除函数头删就是删第一个也即是删除begin位置。
2.9 析构和清理函数 ~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){erase(it);}}
在clear函数如果直接erase(it)迭代器会失效最好返回当前位置的下一个位置两种方法一种是是接收一下二种是在里面it因为这是后置返回的是临时变量是it的拷贝所以这里删除的是it的拷贝。但是clear函数不删除头结点。 析构函数先调用clear函数把head以后的结点删除再释放头结点在把头结点置空。
3.1 swap交换函数 void swap(listT tmp){std::swap(_head, tmp._head);}3.2 拷贝构造函数 list(const T it){/*init();for (auto e : it){push_back(e);}*/init();listTtmp(it.begin(), it, end());swap(tmp);}拷贝构造使用第一种方法就可以拷贝嵌套list和string等自定义类型如果里面是一个list用init函数解决了外部的拷贝里面开了一个新的头结点的空间而在push_back的时候调用insert里面开除新结点最重要的点是新结点中的_data它存的是拷贝的自定义类型这个新_data变量的地址和旧结点的地址是不一样的因为开新结点就意味着T _data,进行实例化变量是新空间开的是新地址而在释放结点摧毁里面的变量时或改变里面其中一个内容不会互相影响或者说就不存在指向同一块的空间的问题即深拷贝问题。如土_data地址不一样已得到验证 使用第二种方法先在内部进行创建一个头结点之后调用迭代器初始化构造tmp对象里面形成了一个新的初始化的链表最后用swap函数交换tmp的头指针和刚刚创建的头指针也即是this指向的头指针。
3.3 使用迭代器进行初始化构造 templateclass Iteratorlist(Iterator first, Iterator last){init();while (first ! last){push_back(*first);first;}}也就是先初始化把某种迭代器的区间的内容进行尾插到实例化对象的空间中去。
3.4 构造的list中包含n个值为val的元素 list (size_t n, const T val T()){init();for (size_t i 0; in; i){push_back(val);}}先初始化再用一个for循环进行尾插n个val。
3.5 赋值重载函数 listT operator(listT it){swap(it);return *this;}这里是用swap的时候在里面要传值如果传引用交换的时候等号右边的内容会发生变化我们需要传值就会调用拷贝构造it就是等号右边的拷贝拷贝是等号左边想要的不是右边想要的的不能让右变的发生变化。所以交换后直接返回*this。
三、list迭代器失效
迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 在insert时这里的迭代器pos不会失效因为这里pos始终指向这个结点并且这个位置关系不会变不像vector插入删除数据就算不扩容也要挪动数据因为数据相对位置已经发生改变他已经不是指向之前的位置了。它俩形成鲜明对比。如图 而在使用**erase()**函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值如图
四、list模拟实现代码
(1)simulate_list
#pragma once
#includeassert.h
namespace nza
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _data;list_node(const T x T()):_next(nullptr), _prev(nullptr), _data(x){}};templateclass T,class Cst,class Pstruct list_iterator{typedef list_nodeT node;typedef list_iteratorT,Cst,P self;node* _node;list_iterator(node* n):_node(n){}P operator-(){return (_node-_data);}Cst 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;}};templateclass Tclass list{typedef list_nodeT node;public:typedef list_iteratorT,T,T* iterator;typedef list_iteratorT, const T,const T* const_iterator;void init(){_head new node;_head-_next _head;_head-_prev _head;}list(){init();}~list(){clear();delete _head;_head nullptr;}void clear(){iterator it begin();while (it ! end()){erase(it);}}templateclass Iteratorlist(Iterator first, Iterator last){init();while (first ! last){push_back(*first);first;}}void swap(listT tmp){std::swap(_head, tmp._head);}list(const listT it){init();for (auto e : it){push_back(e);}/*init();listT tmp(it.begin(), it. end());swap(tmp);*/}list (size_t n, const T val T()){init();for (size_t i 0; in; i){push_back(val);}}listT operator(listT it){swap(it);return *this;}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 x){/*node* newnode new node(x);node* tail _head-_prev;tail-_next newnode;newnode-_prevtail;newnode-_next _head;_head-_prev newnode;*/insert(end(), x);}void push_front(const T x){insert(begin(), x);}void insert(iterator pos,const T x){node* cur pos._node;node* prev cur-_prev;node* Newnode new node(x);prev-_next Newnode;Newnode-_next cur;Newnode-_prev prev;cur-_prev Newnode;}iterator erase(iterator pos){assert(pos ! end());node* net pos._node-_next;node* prevpos._node-_prev;prev-_next net;net-_prev prev;delete pos._node;return iterator(net);}void pop_back(){erase(--end());}void pop_front(){erase(begin());}private:node* _head;};
}(2)test.cpp
#includeiostream
#includesimulate_list.h
#includelistusing namespace std;
void test1()
{nza::listint v;v.push_back(9);v.push_back(5);v.push_back(3);nza::listint ::iterator p v.begin();for (auto n : v){cout n ;}cout endl;
}
void input_list(const nza::listint v)
{nza::listint ::const_iterator p v.begin();while (p ! v.end()){/* (*p)* 2;*/cout *p ;p;}cout endl;
}
void test2()
{nza::listintl;l.push_back(4);l.push_back(6);l.push_back(8);input_list(l);}
struct M{int _a1;int _a2;M(int a1 0, int a2 0):_a1(a1), _a2(a2){}};
void test3()
{nza::listM q;q.push_back(M(3, 7));q.push_back(M(22, 22));q.push_back(M(44, 66));nza::listM ::iterator p q.begin();while (p ! q.end()){cout p-_a1 ;p;}cout endl;
}
void test4()
{nza::listint l;l.push_back(99);l.push_back(88);l.push_back(77);for (auto e : l){cout e ;}cout endl;l.push_back(66);l.push_front(55);for (auto e : l){cout e ;}cout endl;l.pop_back();l.pop_front();for (auto e : l){cout e ;}cout endl;l.clear();for (auto e : l){cout e ;}cout endl;
}
void test5()
{nza::liststd::listint v3(3,{1,2,3});for (auto e : v3){/* cout e */}//cout endl;nza::liststd::listint v4(v3);for (auto e : v4){/*coute ;*/}//cout endl;
}
int main()
{test1();test2();test3();test4();test5();
}(3)测试结果 五、vector和list容器对比
底层结构 vector是动态顺序表一段连续空间list是带头结点的双向循环链表。 随机访问 vector支持随机访问访问某个元素效率O(1)而list不支持随机访问访问某个元素效率O(N)。 插入与删除 任意位置插入和删除效率低需要挪动元素时间复杂度为O(N)插入时有可能需要扩容扩容就需要开辟新空间拷贝元素释放旧空间导致效率更低而list任意位置插入和删除效率高不需要诺丁元素时间复杂度为O(1)。 迭代器 vector是原生态指针这不能绝对例如VS是封装的list对原生态指针即节点指针进行封装。 空间利用率 vector底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高而list底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低。 使用场景 vector需要高效存储支持随机访问不关心插入删除效率而list大量插入和删除操作不关心随机访问。 迭代器失效 在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效而list插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响
六、总结与补充
总结 原生指针只是一个偶然用来类去封装才是常态底层的本质都可以认为是指针只是说嵌入了一个自定义类型去封装它语法这个行为就把他识别为自定义类型自定义用这个运算符就是重载运算符比如解引用等到底是怎么样的行为是另回事因为函数是我们实现的。const在定义对象的那一下是没有const属性的这是编译器的特殊处理。 补充 listint::iterator p v.begin(),这里要调用一个拷贝构造这里没有写拷贝构造编译器默认生成了一个拷贝构造它是一个浅拷贝begin返回一个临时对象包含了开始结点的指针把这个结点的位置赋值给p也是期望这里有个p对象对象里面有个结点指针也就是指向首位置不是有结点指针就得深拷贝。 同时指向了一个位置但并没有报错因为迭代器没有写析构函数不需要释放结点虽然有结点指针这不属于迭代器只是给迭代器进行封装帮助它实现遍历链表修改链表不支持释放释放是链表的事,另外结点也不是它创建的总来的的说浅拷贝没问题。
