建设网站需要多少费用,韩国女排出线,网站流量超限,网站建设流费用list模拟实现 1.链表结点2.类模板基本框架3.构造4.插入普通迭代器实现4.1尾插4.2普通迭代器实现4.3对比list和vector的iterator4.4迭代器的价值4.5insert4.6尾插头插复用写法 5.删除erase5.1erase5.2尾删头删复用写法 6.析构emptysizeclear6.1clear6.2size6.3 empty6.4 析构 7.… list模拟实现 1.链表结点2.类模板基本框架3.构造4.插入普通迭代器实现4.1尾插4.2普通迭代器实现4.3对比list和vector的iterator4.4迭代器的价值4.5insert4.6尾插头插复用写法 5.删除erase5.1erase5.2尾删头删复用写法 6.析构emptysizeclear6.1clear6.2size6.3 empty6.4 析构 7.拷贝构造赋值运算符重载7.1拷贝构造写法7.2赋值运算符重载 8.const迭代器9.类名与类型的区别10.对于自定义类型迭代器遍历的功能实现11.迭代器完整代码12.vector与list对比12.1vector优缺点总结12.2list优缺点总结 13.迭代器失效问题 自我名言只有努力才能追逐梦想只有努力才不会欺骗自己。 喜欢的点赞收藏关注一下把 库里面的list类模板实现的是带头双向循环链表。这里我们和库实现的是一样的。
1.链表结点 这里链表结点实现的是一个模板因为我们并不知道别人想在结点里放什么数据。
其次库里面结点指针是void*而我们和库里面有一些细微差别
//链表结点
templateclass T
struct __list_node
{__list_node* _prev;__list_node* _next;T _date;
};
//struct和class一样也可以是类关键字并且里面的成员变量和成员函数默认都是public的。2.类模板基本框架
templateclass T
class List
{//每次都要写太长了所以typedef一下typedef __list_nodeT node;
public:private:node* —_head;
};3.构造
templateclass T
struct __list_node
{__list_node* _prev;__list_node* _next;T _date;__list_node(const T val):_prev(nullptr),_next(nullptr),_date(val){}
};//构造list(){//new对自定义类型会调用它的构造函数因此结点类必须要有一个构造_head new node(T());_head-_prev _head;_head-_next _head;}
4.插入普通迭代器实现
4.1尾插 void push_back(const T x){node* newnode new node(x);node* tail _head-_prev;tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}4.2普通迭代器实现 这使用库里面的iterator,遍历链表。 注意list遍历只能用迭代器或者范围for(底层是迭代器)不能用下标[]因为vector物理结构是数组而list底层是一个个按需申请的结点。 接下来我们自己实现一个迭代器。遍历链表。 首先来认识认识迭代器。
std::listint::iterator it It.begin();链表结点是一个个申请的而vector和stirng是一次就申请连续的空间。
由于在前面学过封装这里我们可以把指针封装起来并且加上运算符重载* !来支持迭代器的行为。 templateclass T
struct __lsit_iterator
{typedef __list_nodeT node;node* _pnode;T operator*(){return _pnode-_date;}__lsit_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __lsit_iteratorT It){return _pnode ! It._pnode;}
};//迭代器
iterator begin()
{//这里是匿名构造但是__list_iterator缺少了构造所以增加一下return iterator(_head-_next);
}iterator end()
{return iterator(_head);
}普通迭代器部分模板
templateclass T
struct __lsit_iterator
{typedef __list_nodeT node;node* _pnode;__lsit_iterator(node* _node):_pnode(_node){}T operator*(){return _pnode-_date;}__lsit_iteratorT operator(){_pnode _pnode-_next;return *this;}bool operator!(const __lsit_iteratorT It){return _pnode ! It._pnode;}
};我们使用自己的iterator结果也是正确的。这里不太懂得可以调试一下帮助理解。
4.3对比list和vector的iterator
iteratorr-------1.内置类型 2.行为像指针一样。 范围【begin(),end()) listvector迭代器上层使用都是一样的。但是它们底层实现不一样。list的迭代器是自定义类型封装运算符重载但vector的迭代器并不一定就是内置类型原生指针。
就如在linux环境和vs环境下erase后pos位置失效不失效的问题在linux环境下pos不失效而vs环境下pos失效这是因为在两个不同环境下iterator底层实现是不一样的。linux下iterator是原生指针vs对vector的iterator和list的iterator一样都是指针的封装。所以iterator不一定就是指针 为什么vector和list这里都用 ! “而不是” 呢 这是因为vector的物理结构数组可以满足 但是list的物理结构并不能确定前一个结点与后一个结点位置谁大谁小所以统一用 ! 可以满足不同容器的迭代器。
4.4迭代器的价值
1.封装底层实现不暴露底层的实现细节。 2.提供统一的访问方式降低使用成本。
迭代器是一种框架可能代码我们都会写但是这种框架思维是最重要的。
从物理层面上看vector和list的iterator物理结构都是指针请问大小是几个字节呢
vector迭代器是一个原生指针list迭代器是一个指针类模板类的大小是成员变量的大小内存对齐list迭代器我们就放一个node*指针我们知道32位指针大小为464位指针大小为8所以大小都是4/8字节。
虽然iterator变化都是指针的变化但是它们的类型是不一样的vector的iterator是内置类型原生指针list的iterator是自定义类型编译器根据类型的不同所走的方式不同list的iterator走的是调用函数如it调用it.operator()再把结构返回来而vector直接使用指针直接像后走4个字节。。这就是类型的力量。
4.5insert iterator insert(iterator pos, const T val){node* newnode new node(val);node* cur pos._pnode;node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}4.6尾插头插复用写法 void push_back(const T x){//node* newnode new node(x);//node* tail _head-_prev;//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;insert(end(), x);}void push_front(const T x){insert(begin(), x);}
5.删除erase
5.1erase iterator erase(iterator pos){assert(pos ! end());node* prev pos._pnode-_prev;node* next pos._pnode-_next;prev-_next next;next-_prev prev;delete pos._pnode;//返回pos下一个位置return iterator(next);}5.2尾删头删复用写法 __List_iteratorT operaotr--(){_pnode _pnode-prev;return *this;}void pop_back(){//iterator没有实现--运算符重载所以补充一下erase(--end());}void pop_front(){erase(begin());}6.析构emptysizeclear
6.1clear void clear(){iterator it begin();while (it ! end()){it erase(it);}}6.2size
//一般想法就是遍历统计一下个数但是我们这里可以增加一个_size成员遍历来统计个数
//然后再返回这个变量即可
//成员变量增加一个_size,构造都要改但是我们实现了empty_initialize(),只要修改这里就可以void empty_initialize(){_head new node(T());_head-_prev _head;_head-_next _head;_size 0;}size_t size() const{return _size;}
//插入和删除也需要相应的把_size加上。
6.3 empty bool empty() const{return _size 0;}6.4 析构 ~List(){clear();delete _head;_head nullptr;}7.拷贝构造赋值运算符重载
7.1拷贝构造写法 //拷贝构造传统写法List(const ListT it){//由于构造拷贝构造赋值都要有这样写法,为了减少代码冗余//专门写一个empty_initialize()//_head new node(T());//_head-_prev _head;//_head-_next _head;empty_initialize();for (auto e : it){push_back(e);}}但是这样写有一个问题。 list T是泛型 如果T放的是内置类型还好说但如果T放的是自定义类型这里还涉及拷贝构造和析构。因此正确写法如下。 //拷贝构造传统写法List(const ListT it){empty_initialize();//加个引用for (auto e : it){push_back(e);}}但是这样写还是有问题it是const修饰的对象范围for变量底层是迭代器走的是const的迭代器。但是在__List_iterator 还没有实现。这里先把拷贝构造和赋值写完就说这个问题。
在string和vector模拟实现拷贝构造和赋值运算符重载最终都用现代写法来实现。现代写法的主要思想就是自己的事情让别人干然后再交换一下。
拷贝构造现代写法复用构造函数 前面实现的是一个无参构造想要复用构造函数必须要实现这个一段区间的构造函数。 template class InputIteratorList(InputIterator first, InputIterator last){empty_initialize();while (first ! last){push_back(*first);first;}}void swap(Listint x){std::swap(_head, x._head);std::swap(_size,x._size);}//拷贝构造现代写法List(const ListT it){//这里必须要申请带头结点不然交换就会野指针tmp析构的是就会报错//也不能直接给_head(nullptr)这样tmp析构也会报错empty_initialize();ListT tmp(it.begin(), it.end());swap(tmp);}7.2赋值运算符重载 //传统写法ListT operator(const ListT it){if (this ! it){//this-clear()clear();for (auto e : it){//this-push_back(e);push_back(e);}}return *this;}赋值运算符重载现代写法的思想复用拷贝构造函数 //赋值现代写法//it这里调用拷贝构造函数ListT operator(ListT it){swap(it);return *this;}虽然现在已经实现了拷贝构造和赋值运算符重载但是迭代器没有实现const iterator 上面代码都会报错。 接下来实现const迭代器
8.const迭代器
回想一下vector实现的const迭代器 typedef T* iterator;typedef const T* const_iterator;Listint::iterator it It.begin();//可能会以为在前面加上const 就是const迭代器了但这样是不对的const Listint::iterator it It.begin();我们知道const修饰指针有不同位置
//const修饰*p1*p1内容不能改变p1指针可以改变const T* p1
//const修饰p2p2指针不能改变*p2内容可以改变T* const p2而const迭代器类似p1的行为保护指向对象不能改变迭代器本身可以修改
//不符合迭代器的行为因为它保护迭代器 本身不能修改那么就不能/--迭代器const Listint::iterator it It.begin();所以考虑一下放在__List_iterator中 //iterator it//*it//itT operator*(){return _pnode-_date;}//可能还会想这样写const修饰指针*this//const iterator* const this 这样*this就不会改变了//但是*this 是const iterator it//*it//it 这样的话可以解引用但是不能itconst T operator*() const{//引用赋值必须权限缩小或者平移所以返回类型是constreturn _pnode-_date;}因此我们大多数人会再写一个const迭代器类
templateclass T
struct __List_iterator
{typedef __List_nodeT node;node* _pnode;__List_iterator(node* _node):_pnode(_node){}cosnt T operator*(){return _pnode-_date;}__List_iteratorT operator(){_pnode _pnode-_next;return *this;}__List_iteratorT operator--(){_pnode _pnode-_prev;return *this;}bool operator!(const __List_iteratorT It){return _pnode ! It._pnode;}
};但是对比普通迭代器和const迭代器发现就只有operator*不一样其他运算符重载都一样。 我们看库里是怎么实现iterator的。 暂时先不用管Ptr参数。
看到大佬是把普通迭代器和const迭代器实现放在一块然后用Ref参数来做区分。
我们知道一个模板类由于类型不同可实现不同的类。 如list int , list char 虽然用的是统一模板但是由于类型不同因此是不同的类。所以大佬方法是非常厉害的。
//typedef __List_iteratorT,T iterator;
//typedef __List_iteratorT,const T const_iterator;
templateclass T,class Ref
struct __List_iterator
{typedef __List_nodeT node;typedef __List_iteratorT, Ref self;node* _pnode;__List_iterator(node* _node):_pnode(_node){}Ref operator*(){return _pnode-_date;}//__List_iteratorT operator()//{// _pnode _pnode-_next;// return *this;//}//普通迭代器和const迭代器返回类型不一样因此typedef一下比较方便。self operator(){_pnode _pnode-_next;return *this;}//__List_iteratorT operator--()//{// _pnode _pnode-_prev;// return *this;//}self operator--(){_pnode _pnode-_prev;return *this;}//bool operator!(const __List_iteratorT It)//{// return _pnode ! It._pnode;//}bool operator!(const self It){return _pnode ! It._pnode;}
};有了const迭代器拷贝构造和赋值运算符重载就没问题了。
9.类名与类型的区别
普通类 类名 等价于 类型 类模板 类名 不等价于 类型 注意在类外面 类名 ! 类型 ,类里面 类名 类型
这样写是没有报错的但是不建议这样写。如果别人这样写能看懂即可。 就如库里面提供的拷贝构造赋值就是这样写的
10.对于自定义类型迭代器遍历的功能实现
list T T可能是内置类型也有可能是自定义类型如果是自定义类型迭代器该如何遍历呢
struct Pos
{int _row;int _col;Pos(int row 0, int col 0):_row(row),_col(col){}
};void test_list5()
{ListPos It;Pos p(1,1);It.push_back(p);It.push_back(p);It.push_back(Pos(2,2));It.push_back(Pos(3,3));ListPos::iterator it It.begin();while (it ! It.end()){//这里还这样解引用可以拿到想要的数据吗cout *it ;it;}cout endl;
}解引用有三种访问方式 1.数组------ [ ] 2.普通指针如int *p)------ *p 3.结构的指针pos *p------- p----- ListPos::iterator it It.begin();while (it ! It.end()){//cout *it ;//1.cout (*it)._row : (*it)._col endl;//2.cout it-_row : it-_col endl;it;}cout endl;第一种方法调用it.operator*返回的是一个Pos对象
第二种方法需要调用it.operator-因此给迭代器增加一个operator-()函数 T* opearotr-(){//返回的是结点数据的地址return _pnode-_date;} 对于T是自定义类型迭代器遍历推荐it-_row这样的。
再看一个问题
void print_List(const ListPos lt)
{ListPos::const_iterator it lt.begin();while (it ! lt.end()){//const迭代器数据不能修改it-_row;cout it-_row : it-_col endl;it;}cout endl;
}void test_list7()
{ListPos It;Pos p(1, 1);It.push_back(p);It.push_back(p);It.push_back(Pos(2, 2));It.push_back(Pos(3, 3));ListPos::iterator it It.begin();while (it ! It.end()){//普通迭代器对于数据可以修改it-_row;cout it-_row : it-_col endl;it;}cout endl;print_List(It);
}注意运行结果const迭代器竟然也能支持it-_row了。这不符合const迭代器。
因此再次修改一下迭代器但是我们的普通迭代器和const迭代器实现在一块所以这里我们给__List_iterator第三个参数Ptr Ptr operator-(){return _pnode-_date;}11.迭代器完整代码
//typedef __List_iteratorT,T,T* iterator;
//typedef __List_iteratorT,const T,const T* const_iterator;
templateclass T,class Ref,class Ptr
struct __List_iterator
{typedef __List_nodeT node;typedef __List_iteratorT,Ref,Ptr self;node* _pnode;__List_iterator(node* _node):_pnode(_node){}Ref operator*(){return _pnode-_date;}Ptr operator-(){return _pnode-_date;}//itself operator(){_pnode _pnode-_next;return *this;}//it//int是一个占位符为了把前置和后置 分开self operator(int){self tmp(*this);_pnode _pnode-next;return tmp;}//--itself operator--(){_pnode _pnode-_prev;return *this;}//it--self operator--(int){self tmp(*this);_pnode _pnode-_prev;return tmp;}bool operator!(const self It){return _pnode ! It._pnode;}bool operator(const self It){return _pnode It._pnode;}
};注意观察我们的迭代器和List模拟实现成员变量都有node*指针。
List我们实现了析构函数释放所有结点而迭代器我们并没有实现析构函数。那迭代器这里默认生成的析构会不会释放结点呢
析构函数和构造函数一样如果不写默认生成的析构函数对内置类型不处理对自定义类型调用它的析构。 如果我们List我们不写析构编译器默认生成的析构敢不敢轻易释放指针所指向的结点呢 我们的编译器非常尽责默认生成的析构对自定义类型调用它的析构对内置类型不敢轻易处理。所以对于指针不敢轻易释放所指向的结点。
因此对于List我们需要析构的时候释放所有结点所以自己写了个析构。而迭代器我们没写析构那编译器默认生成的析构对这个指针指向的结点也不会释放。因为这个结点是链表的迭代器只是借助结点的指针帮助去访问或修改数据。所以也不能自己写一个析构去把这个结点释放。
不是说有指针就需要去析构一定要具体问题具体分析。
并且iterator我们也没有实现拷贝构造和赋值。使用的是默认生成的属于浅拷贝就够用了这是因为默认生成的析构并不会释放指针所指向的结点所以够用。
在类与对象中也总结过需要写析构就需要自己写拷贝构造和赋值。
12.vector与list对比
vectorlist底层结构动态顺序表一段连续空间带头结点的双向循环链表随机访问支持随机访问访问某个元素效率O(1)不支持随机访问访问某个元素效率O(N)插入和删除任意位置插入和删除效率低需要搬移元素时间复杂度为O(N)插入时有可能需要增容增容开辟新空间拷贝元素释放旧空间导致效率更低任意位置插入和删除效率高不需要搬移元素时间复杂度为O(1)空间利用率底层为连续空间不容易造成内存碎片空间利用率高缓存利用率高底层节点动态开辟小节点容易造成内存碎片空间利用率低缓存利用率低迭代器原生态指针对原生态指针(节点指针)进行封装迭代器失效在插入元素时要给所有的迭代器重新赋值因为插入元素有可能会导致重新扩容致使原来迭代器失效删除时当前迭代器需要重新赋值否则会失效在插入元素不会导致迭代器失效删除元素时只会导致当前迭代器失效其他迭代器不受影响使用场景需要高效存储支持随机访问不关心插入删除效率大量插入和删除操作不关心随机访问
12.1vector优缺点总结
优点 1.下标随机访问 2.尾插尾删效率高 3.cpu高速缓存命中高因为vector物理结构是一段连续的数组
缺点 1.前面部分插入删除效率低O(N) 2.扩容有销毁还存在一定空间浪费
12.2list优缺点总结
优点 1.按需申请释放无需扩容 2.任意位置插入删除O(1)
缺点 1.不支持下标随机访问 2.cpu高速缓存命中低list物理结点是一个个按需申请的结点
vector与list就像左右手一样属于互补配合的关系。
13.迭代器失效问题
我们现在已经模拟实现了stringvectorlist。 vector-----insert/erase (失效) list--------erase失效
string似乎从来没提过失效还是不失效的问题。那么string到底失效不失效呢
stirng底层和vector一样都是连续的空间。空间不够需要扩容因此string也失效。
string------insert/erase失效但是一般不关注string的失效。 vector的insert/erase给的是迭代器string的insert/erase常用接口更多都是下标支持迭代器支持用的很少。所以即使扩容或者删除对下标没什么影响。 自此关于list模拟实现内容结束了有些接口没有实现有兴趣可以实现一下。
