企业网站建设报告,永州做网站的公司,深圳画册制作,请写出html文档的代码本期主题#xff1a;list的讲解和模拟实现博客主页#xff1a;小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限#xff0c;出现错误希望大家不吝赐1.list的介绍和使用1.1.list的介绍1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器…本期主题list的讲解和模拟实现博客主页小峰同学分享小编的在Linux中学习到的知识和遇到的问题小编的能力有限出现错误希望大家不吝赐1.list的介绍和使用1.1.list的介绍1.list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2.list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向 其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高 效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率 更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list 的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间 开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这 可能是一个重要的因素) 1.2.list的使用1.2.1.成员函数这个和vector的差不多1.2.2.迭代器和vector相似从此时开始就要知道迭代器的重要性了不支持下标访问了这时候迭代器就很重要了。所有的容器真正的统一的遍历方式就是迭代器。31.2.3.容量相关1.2.4.访问相关1.2.5.修改相关1.2.6.操作相关2.List的模拟实现2.1.源码源码#pragma once
#include utility
#includeiostream
#includeassert.h
using namespace std;namespace zxf2
{templateclass Tstruct list_node{//共有成员变量list_node* _next;list_node* _prev;T _data;//每个节点的构造函数。list_node(const T val T()):_next(nullptr),_prev(nullptr),_data(val){}};//这里实现的迭代器是普通版本的那如果想要一个const版本的迭代器怎么办//const list_iteratorT it lt.begin();//这样 显然不是我们想要的结果//上述的写法只能是it 不能改但是 const迭代器是 *it不能改动。//为什么vector模拟实现的时候 直接 定义了 typedef const T* const_iterator;自然就是实现了 it可以改而 *it不能改的目的利用了指针的特性////templateclass T//struct list_iterator//{// //迭代器本质上是在控制节点的指针 _pnode;// //是对节点node指针的封装。// typedef list_nodeT node;// typedef list_iteratorT self;//迭代器类型重命名。// //成员变量// node* _pnode;// //迭代器在创建的时候必须初始化// //使用节点的指针来构造// list_iterator(node* pnode){// _pnode pnode;// }// //前置 ,--; 前置可以返回引用也就返回迭代器本身。// self operator()// {// _pnode _pnode-_next;// return *this;// }// self operator--()// {// _pnode _pnode-_prev;// return *this;// }// //后置 -- ;不能返回引用。// self operator(int)// {// self tmp(*this);//出了函数tmp会被销毁的。// _pnode _pnode-_next;// return tmp;// }// self operator--(int)// {// self tmp(*this);//出了函数tmp会被销毁的。// _pnode _pnode-_prev;// return tmp;// }// //所以一般使用前置减少拷贝照成的空间和时间浪费。// //判断两个迭代器是否相同就是迭代器里面的成员变量的地址是否相同。// bool operator!(const self lt)const// {// return _pnode ! lt._pnode;// }// bool operator(const self lt)const// {// return _pnode lt._pnode;// }// T operator*()// {// return _pnode-_data;// }//};//templateclass T//struct list_const_iterator//{// //迭代器本质上是在控制节点的指针 _pnode;// //是对节点node指针的封装。// typedef list_nodeT node;// typedef list_const_iteratorT self;//迭代器类型重命名。// //成员变量// node* _pnode;// //迭代器在创建的时候必须初始化// //使用节点的指针来构造// list_const_iterator(node* pnode) {// _pnode pnode;// }// //前置 ,--; 前置可以返回引用也就返回迭代器本身。// self operator()// {// _pnode _pnode-_next;// return *this;// }// self operator--()// {// _pnode _pnode-_prev;// return *this;// }// //后置 -- ;不能返回引用。// self operator(int)// {// self tmp(*this);//出了函数tmp会被销毁的。// _pnode _pnode-_next;// return tmp;// }// self operator--(int)// {// self tmp(*this);//出了函数tmp会被销毁的。// _pnode _pnode-_prev;// return tmp;// }// //所以一般使用前置减少拷贝照成的空间和时间浪费。// //判断两个迭代器是否相同就是迭代器里面的成员变量的地址是否相同。// bool operator!(const self lt)const// {// return _pnode ! lt._pnode;// }// bool operator(const self lt)const// {// return _pnode lt._pnode;// }// const T operator*()//这里是const迭代器和 普通迭代器真的区别区别就这一点点。就是在解引用的时候返回的是const类型还是普通类型。// //返回const类型就是不能修改const迭代器返回普通类型就是可以修改普通迭代器。// {// return _pnode-_data;// }//};//上面两个迭代器多少有点代码冗余。可以把他们合并在一起。templateclass T , class ref, class ptr
struct list_iterator
{//迭代器本质上是在控制节点的指针 _pnode;//是对节点node指针的封装。typedef list_nodeT node;typedef list_iteratorT, ref ,ptr self;//迭代器类型重命名。//成员变量node* _pnode;//迭代器在创建的时候必须初始化//使用节点的指针来构造list_iterator(node* pnode) {_pnode pnode;}//前置 ,--; 前置可以返回引用也就返回迭代器本身。self operator(){_pnode _pnode-_next;return *this;}self operator--(){_pnode _pnode-_prev;return *this;}//后置 -- ;不能返回引用。self operator(int){self tmp(*this);//出了函数tmp会被销毁的。_pnode _pnode-_next;return tmp;}self operator--(int){self tmp(*this);//出了函数tmp会被销毁的。_pnode _pnode-_prev;return tmp;}bool operator!(const self lt)const//这里的const有什么用{return _pnode ! lt._pnode;}bool operator(const self lt)const{return _pnode lt._pnode;}ref operator*(){return _pnode-_data;}ptr operator-(){return _pnode-_data;}self operator(size_t n){while (n--){_pnode _pnode-_next;}return *this;}self operator-(size_t n){while (n--){_pnode _pnode-_prev;}return *this;}};template class Tclass list{//类名 list//类型 listTtypedef 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;//创建出头节点void empty_list(){_phead new node(T());_phead-_next _phead;_phead-_prev _phead;}//无参构造list(){empty_list();}void push_back(const T val){//node* tmp new node(val);//tmp-_next _phead;//tmp-_prev _phead-_prev;//_phead-_prev-_next tmp;//_phead-_prev tmp;insert(iterator(_phead), val);}void push_front(const T val){//node* tmp new node(val);//tmp-_next _phead;//tmp-_prev _phead-_prev;//_phead-_prev-_next tmp;//_phead-_prev tmp;insert(iterator(_phead-_next), val);}//单参数构造list(const T val){empty_list();push_back(val);}//迭代器构造的模板templateclass input_iteratorlist(input_iterator first, input_iterator last){//创建头节点empty_list();while (first ! last){push_back(*first);//(*first)是 T/const T 类型的数据first;}}// //拷贝构造(古法) 里 lt1 lt2
// list(const listT lt)
// //注意拷贝构造的参数也是引用防止无线循环
// {
// empty_list();
需要迭代器的支持
// for (auto e : lt){//注意这样的引用const 可加可不加。
// //引用1防止e的空间浪费2listlist T这种情况出现时死循环。
// push_back(e);
// }
// }void swap(list lt){std::swap(lt._phead, _phead);}~list(){clear();delete _phead;_phead nullptr;}void clear(){//注意这里只能是 iterator 不能是 const_iterator //const list 才会返回const_iterator,但是 const list 不能修改iterator first begin();//while (first ! end())//{// erase(first);// first;//}//上述写法是错误的while (first ! end()){first erase(first);}}size_t size(){return _size;}bool empty(){return _size 0;}//lt1 lt2;listT operator(listT lt){swap(lt);return *this;}//注意删除的时候要返回欲删除元素下一个元素的迭代器iterator erase(iterator it){assert(it ! end());node* next it._pnode-_next;node* prev it._pnode-_prev;next-_prev prev;prev-_next next;delete it._pnode;return iterator(next);// 匿名对象 这里的生命周期只有一行不能引用返回。--_size;}iterator insert(iterator pos, const T val){node* newnode new node(val);node* next pos._pnode;node* prev pos._pnode-_prev;newnode-_next next;newnode-_prev prev;prev-_next newnode;next-_prev newnode;return iterator(newnode);_size;}void pop_back(){erase(iterator(_phead-_prev));}void pop_front(){erase(iterator(_phead-_next));}//拷贝构造(现代) 里 lt1 lt2list(const listT lt)//注意拷贝构造的参数也是引用防止无线循环{//无论什么构造都要先创建头节点empty_list();list tmp(lt.begin(), lt.end());//先创建一个list类型的临时局部变量出了作用域会被销毁。swap(tmp);}//这里也不能返回引用iterator begin(){return iterator(_phead-_next);//匿名对象生命周期只有一行}const_iterator begin()const{return const_iterator(_phead-_next);//匿名对象生命周期只有一行}iterator end(){return iterator(_phead);//匿名对象生命周期只有一行}const_iterator end()const{return const_iterator(_phead);//匿名对象生命周期只有一行}private://list私有的成员node* _phead;size_t _size;};}2.2.常见问题2.2.1. list的迭代器失效 前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节 点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代 器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。 void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给
其赋值l.erase(it); it;}
}// 改正
void TestListIterator()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, arraysizeof(array)/sizeof(array[0]));auto it l.begin();while (it ! l.end()){l.erase(it); // it l.erase(it);}
}2.2.2.类模板中类名和类型的问题类一般只有两种普通类 和 类模板对于普通类 类名就是类型是相同的。对于类模板类名是类名给T赋上对应的类型后才是类的类型class BBB
{int _data;
};
//在这里类名就是类型
//类名BBB
//类型BBBtemplateclass T
class AAA
{T _data;
};
//在这里
//类名是AAA
//类型是AAAT但是在类模板里面可以使用类名去代表类型但是在类外面类名就是类名类型就是类型。但是我个人习惯不喜欢这个特例。2.2.3.迭代器it的 - 的访问问题看一下示例代码struct Pos
{int _row;int _col;Pos(int row 0, int col 0):_row(row), _col(col){}
};void print_list(const zxf2::listPos lt)
{zxf2::listPos::const_iterator it lt.begin();while (it ! lt.end()){//it-_row;//这里还能 明明是 const类型的listPos为啥里面的数据可以//因为这里又会出现一个问题 T* 和 const T* 的 问题//const_iterator 对应的应该是 const T解引用的返回值不可修改 和 const T* it- 返回值不可修改 的问题。//iterator 对应的应该是 T 解引用的返回值可修改 和 T* it- 返回值不可修改 的问题。//迭代器是什么//功能类似于指针可以 * 和 - 访问指针元素的类模板//他是通过 对 T* 进行封装的得到的一个类。//typedef list_iteratorT, T, T* iterator;//普通迭代器// 重载operator* 的时候 用T返回。 // 重载operator- 的时候用 T* 返回//typedef list_iteratorT, const T, const T* const_iterator;//const迭代器// operator* 的时候 用const T返回。// operator- 的时候用const T* 返回cout it-_row : it-_col endl;it;}cout endl;
}void test_list5()
{zxf2::listPos lt;Pos p1(1, 1);lt.push_back(p1);lt.push_back(p1);lt.push_back(p1);lt.push_back(Pos(2, 2));lt.push_back(Pos(3, 3));// int* p - *p// Pos* p - p-zxf2::listPos::iterator it lt.begin();//listPos::iterator it2 it;while (it ! lt.end()){it-_row;//cout it-;//错误写法。//cout it.operator-()//it.operator-()-_col;//cout ((*it))-_row : (*it)._col endl;cout it-_row : it-_col endl;//cout it.operator-()-_row : it-_col endl;it;}cout endl;print_list(lt);
}首先第一个问题operator-()如何重载的问题 ptr operator-()//ptr是 T* 类型或者 const T* 类型的节点里面存放数据的地址。{return (_pnode-_data);}我们说迭代器是一个类似于指针一样的东西所以如果list节点数据是一个自定义类型不用-,但是如果list节点数据是一个结构体那么 - 成员变量应该就可以访问到成员所以应该 it - 成员变量 就可以访问到。但是根据我们迭代器-的重载来看的话它返回的是结构的指针所以按理来说访问成员应该是 it - - 成员变量但是我们看到在实例中我们访问的时候 直接是使用 it - 成员变量 即可所以这里编译器做了优化。我们可以看到下面代码都可以实现对结构体里面对象的访问。 cout ((*it))-_row : (*it)._col endl;cout it-_row : it-_col endl;cout it.operator-()-_row : it-_col endl;其实本质就是编译器把 it - - _row 优化为 it -_row可以从it.operator-()-_row 证明得出。这里是编译器的一个特殊处理。在以后的智能指针中很常用。
