成都教育网站建设公司价格,河北省住房城乡建设厅网站首页,集团网站建设价格,赤峰市哪里做网站创作不易#xff0c;感谢三连#xff01;#xff01;
一、List的介绍
list的文档介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。
2. list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不… 创作不易感谢三连
一、List的介绍
list的文档介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。
2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。
3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。
4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。
5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)要注意的是list开始就不支持下标访问了所以要访问都要以迭代器为准
void Print(const listint l)
{//迭代去区间遍历listint::const_iterator it l.begin();while (it ! l.end()){cout *it ;it;}cout endl;//范围for遍历for (auto e : l)cout e ;cout endl;
}
二、List的使用注意事项 博主觉得跟之前vector的基本上差不了多少如果不会看文档用库里面的list的可以去看博主只管关于string和vector的使用。
CString类的使用-CSDN博客
CVector的使用-CSDN博客
下面直接介绍List使用中的易错点
2.1 List的迭代器失效问题 我们之前学习vector的时候知道了insert和erase都有可能存在迭代器失效的问题那list会出现这种情况吗下面来进行分析 insert插入新节点的迭代器因此insert不可能会出现失效的问题。 而earse必然会失效因为该迭代器对应的节点被删除了。如果我们想继续用的话就得利用返回值去更新迭代器返回值是被删除元素的下一个位置的迭代器。
2.2 List中sort的效率测试
我们用一段代码来测试一下list中sort的性能
void test_op()
{srand((unsigned int)time(NULL));const int N 1000000;vectorint v;v.reserve(N);listint lt1;listint lt2;for (int i 0; i N; i){int e rand();lt1.push_back(e);lt2.push_back(e);}// 拷贝到vector排序排完以后再拷贝回来int begin1 clock();for (auto e : lt1){v.push_back(e);}sort(v.begin(), v.end());size_t i 0;for (auto e : lt1){e v[i];}int end1 clock();//list调用自己的sortint begin2 clock();lt2.sort();int end2 clock();printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
} 会发现哪怕我先拷贝到vector排完再拷贝回去效率都比list的sort效率高所以list的sort实际中意义不是很大 三、模拟实现的注意事项 还是跟之前模拟实现一样先看看SGI版本的源码 list本质上是带头双向链表
第一部分 链表节点
第二部分 迭代器
第三部分、链表
这里我们可以先实现链表节点结构体 这里用sturct把权限放开。 //节点的封装
templateclass T
struct list_node
{list_nodeT* _prev;list_nodeT* _next;T _data;//节点的构造函数list_node(const T val T()):_prev(nullptr), _next(nullptr), _data(val){}
}; 然后封装一个链表将头结点作为自己的成员变量封装起来 templateclass T
class list
{typedef list_nodeT node;//typedef可以帮助我们简洁代码private:node* _head;}; 下面开始进行我们的重中之重——迭代器
四、正向迭代器的实现
2.1 正向迭代器的封装 在学习Vector的时候我们发现其实vector的迭代器就是一个原生指针所以我们将他改了名字
这得益于vector空间连续的特点所以对指针进行加和减再进行解引用可以访问到我们想要的元素但是链表可以吗 虽然看似我们好像用箭头连接起来了但其实他们空间上是不连续的那我们对一个节点指针进行加减就很难说能不能找到下一个节点更多的是找不到的情况 那我们思考一样如果我们要搞一个迭代器我们希望怎么去得到我们的数据呢我们希望我们解引用的时候可以拿到他的data希望的时候可以拿到他的next--的时候可以拿到他的prev。 那我们怎么去改变原生操作符的行为呢答案就是运算符重载所以我们可以将迭代器单独封装成一个类去管理节点改变运算符的行为 我们先进行实现然后再慢慢分析 //封装迭代器templateclass T, class Ref, class Ptr//Ref用于引用是否constPtr用于指针是否conststruct list_iterator{typedef list_nodeT node;typedef list_iteratorT, Ref, Ptr self;node* _node;//迭代器的构造函数list_iterator(node* n)//迭代器的构造:_node(n){}//实现*Ref operator*() const{return _node-_data;}//实现-Ptr operator-() const{return operator*(); //本来是两个-,为了增强可读性我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员那么我们可以通过箭头的直线去找到对应我们想要的成员 }//前置self operator(){_node _node-_next;return *this;}//后置self operator(int){self temp(*this);*this;return temp;}//前置--self operator--(){_node _node-_prev;return *this;}//后置--self operator--(int){self temp(*this);--*this;return temp;}//bool operator!(const self s) const{return _node ! s._node;}//bool operator(const self s) const{return _node s._node;}}; 第一个模版参数是类型第二个模版参数是引用第三个模版参数是指针 Ref和Ptr是用来区分正常的迭代器和const修饰的迭代器Ref是T或者是const T,这样可以在某些时候我们去限制data不能被修改。而Ptr是T*或者是const T*重载箭头的作用是如果我们data存储的是一个自定义类型这个时候如果直接解引用肯定是不行的所以我们的箭头可以在解引用的时候先返回data的地址然后我们就可以通过箭头去访问他不同的成员变量。
下面举个data存的是自定义类型的例子
2.2 迭代器的使用 templateclass T
class list
{typedef list_nodeT node;//typedef可以帮助我们简洁代码
public://正向迭代器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_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}private:node* _head;}; 这边我们用到了匿名对象。
思考这里的const迭代器为什么不能直接用const修饰普通迭代器
因为typedef碰到const的话就不是简单的字符串替换 实际上你以为的const T* 在这里变成了T*const 因为迭代器我们是希望他可以进行和--的而我们只是不希望他指向的内容给改变所以我们的const要修饰的是指针的内容而不是修饰指针。
五、list相关的成员函数
3.1 构造函数
1、默认构造函数
因为无论如何都要有哨兵节点所以我们直接封装一个 void empty_init(){_head new node;_head-_next _head;_head-_prev _head;} 所以可以这么写 //默认构造函数list(){empty_init();} 2、有参构造函数 //有参构造函数
list(size_t n, const T val T())
{empty_init();for (size_t i n; i 0; --i)push_back(val);
} 3、迭代器区间构造函数 //迭代器区间构造函数
template class InputIterator
list(InputIterator first, InputIterator last)
{empty_init();while (first ! last){push_back(*first);first;}
} 4、拷贝构造的传统写法
传统方法就是一个个拷贝过去 //拷贝构造函数传统写法
list(const listT lt)
{empty_init();for (auto e : lt)push_back(e);
} 5、拷贝构造的现代写法swap 现代写法就是我先创建一个临时对象让他利用被拷贝对象的迭代器构造出来然后再交换窃取革命成功被利用完后的临时对象会在栈帧结束后被清除典型的资本家思维 //交换函数void swap(listT temp){std::swap(_head, temp._head);}//拷贝构造函数的现代写法list(const listT lt){empty_init();listT temp(lt.begin(), lt.end());//复用迭代器区间构造让别人构造好了我再窃取革命成果swap(temp);} 3.2 clear和析构函数 list不像vector一样不能直接用头指针delete因为空间不连续所以要一个个节点去delete所以在这之前我们可以先实现clearclear的作用是把链表清空只剩一个头节点然我们的析构函数再复用clear然后再单独delete头节点就行了 //clear 只留一个头节点void clear(){iterator it begin();while (it ! end())it erase(it);}//析构函数~list(){clear();delete _head;_head nullptr;} 3.3 赋值重载和assign
assign和的本质上都是先将原来的空间的内容给清空换成的内容。 只不过区别就是assign可以利用迭代器去控制被替换的范围也可以自己去换成n个一样的元素。所以我们先实现assign再实现
1、assign直接替换 //assign(直接替换)
void assign(size_t n, const T val)
{clear();for (size_t i n; i 0; --i)push_back(val);
} 2、assign迭代器区间替换 //assign(迭代器区间替换)template class InputIteratorvoid assign(InputIterator first, InputIterator last){clear();while (first ! last){push_back(*first);first;}} 3、assign直接替换重载防止间接寻址
思考我们的本意是将lt2替换成5个2我们发现我们调的竟然是迭代器区间构造的assign为什么会这样呢 因为重载类型会优先找最匹配的assign的第一个版本的n是size_t类型我们传的整数默认是int所以会发生强制类型转化而第二个版本恰好可以变成两个int所以他会走迭代器区间版本。所以此时有两个方案第一个方案是我们要在第一个参数后面加u但是这不符合我们的使用习惯所以我们可以采用第二个方案写个重载版本。 //assign重载版本 防止间接寻址
void assign(int n, const T val)
{clear();for (size_t i n; i 0; --i)push_back(val);
} 4、赋值重载传统写法
直接复用assign // 赋值重载的传统写法listT operator(const listT lt){assign(lt.begin(), lt.end());return *this;} 5、赋值重载的现代写法 listT operator(listT lt)
{swap(lt);//利用值传递拷贝的临时对象进行交换return *this;
} 3.4 修改相关函数Modifiers
1、empty、size //size
size_t size() const
{size_t n 0;for (auto e : *this)n;return n;
}
//empty
bool empty() const
{return node-next node;
} 2、insert
我们先实现insert和erase其他的就可以直接复用了 //insert
iterator insert(iterator pos, const T val)
{node* cur pos._node;//记录当前节点node* prev cur-_prev;//记录前驱节点node* newnode new node(val);//建立新节点//开始改变指向newnode-_next cur;cur-_prev newnode;prev-_next newnode;newnode-_prev prev;return iterator(newnode);
} 3、erase //erase
iterator erase(iterator pos)
{assert(pos ! end());//确保不是删除哨兵位置node* prev pos._node-_prev;node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);//利用匿名对象返回
} 4、尾插尾删头插头删 //pushback 尾插
void push_back(const T val)
{insert(end(), val);
}
//pushfront 头插
void push_front(const T val)
{insert(begin(), val);
}
//popback 尾删
void pop_back()
{erase(--end());
}
//popfront 头删
void pop_front()
{erase(begin());
} 5、resize //resize 如果n小于当前容量的大小则内容将减少到前n个元素 当n大于容器大小时则在末尾插入任意容量的内容。
void resize(size_t n, const T val T())
{size_t sz size();//记录当前的有效元素的个数while (n sz){pop_back();--sz;}while (n sz){push_back(val);sz;}
} 六、反向迭代器的实现
sgi版本下的反向迭代器其实就是将构建一个反向迭代器的类将正向迭代器封装起来这个时候正向迭代器的就是反向迭代器的-- templateclass iterator, class Ref, class Ptr
struct list_reverse_iterator
{typedef list_reverse_iteratoriterator, Ref, Ptr self;//用正向迭代器去构造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp _cur;--temp;return *temp;}//实现-Ptr operator-() const{return operator*();}//前置self operator(){--_cur;return *this;}//后置self operator(int){iterator temp(_cur);--*this;return temp;}//前置--self operator--(){_cur;return *this;}//后置--self operator--(int){iterator temp(_cur);*this;return temp;}//不等于bool operator!(const self s){return _cur ! s._cur;}//等于bool operator(const self s){return _cur s._cur;}iterator _cur;
}; 思考为什么解引用的是前一个位置的元素
通过这个我们来看看vector下的反向迭代器代码
复用性很高和list的区别就是因为是随机迭代器所以多了和-的接口第二个就是不需要-,所以其实模版也可少传一个 七、list模拟实现的全部代码 //c喜欢ListNode驼峰法命名 为了和STL风格一致我们也用小写
//但是STL版本和java喜欢小写带_
namespace cyx
{//节点的封装templateclass Tstruct list_node{list_nodeT* _prev;list_nodeT* _next;T _data;//节点的构造函数list_node(const T val T()):_prev(nullptr), _next(nullptr), _data(val){}};//封装迭代器templateclass T, class Ref, class Ptr//Ref用于struct list_iterator{typedef list_nodeT node;typedef list_iteratorT, Ref, Ptr self;node* _node;//迭代器的构造函数list_iterator(node* n)//迭代器的构造:_node(n){}//实现*Ref operator*() const{return _node-_data;}//实现-Ptr operator-() const{return operator*(); //本来是两个-,为了增强可读性我们封装了这个函数 比如当我们存储的结构体解引用后有多个成员那么我们可以通过箭头的直线去找到对应我们想要的成员 }//前置self operator(){_node _node-_next;return *this;}//后置self operator(int){self temp(*this);*this;return temp;}//前置--self operator--(){_node _node-_prev;return *this;}//后置--self operator--(int){self temp(*this);--*this;return temp;}//bool operator!(const self s) const{return _node ! s._node;}//bool operator(const self s) const{return _node s._node;}};templateclass iterator, class Ref, class Ptrstruct list_reverse_iterator{typedef list_reverse_iteratoriterator, Ref, Ptr self;//用正向迭代器去构造反向迭代器list_reverse_iterator(iterator it):_cur(it){}//解引用Ref operator*() const{iterator temp _cur;--temp;return *temp;}//实现-Ptr operator-() const{return operator*();}//前置self operator(){--_cur;return *this;}//后置self operator(int){iterator temp(_cur);--*this;return temp;}//前置--self operator--(){_cur;return *this;}//后置--self operator--(int){iterator temp(_cur);*this;return temp;}//不等于bool operator!(const self s){return _cur ! s._cur;}//等于bool operator(const self s){return _cur s._cur;}iterator _cur;};templateclass Tclass list{typedef list_nodeT node;//typedef可以帮助我们简洁代码public://正向迭代器typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;//typedef __list_const_iteratorT const_iterator;不行//反向迭代器typedef list_reverse_iteratoriterator, T, T* reverse_iterator;typedef list_reverse_iteratoriterator, const T, const T* const_reverse_iterator;//可读可写正向迭代器iterator begin(){return iterator(_head-_next);}iterator end(){return iterator(_head);}//可读不可写正向迭代器const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}//可读可写的反向迭代器reverse_iterator rbegin(){return reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}//可读不可写的反向迭代器const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}//默认构造函数list(){empty_init();}//有参构造函数list(size_t n, const T val T()){empty_init();for (size_t i n; i 0; --i)push_back(val);}//迭代器区间构造函数template class InputIteratorlist(InputIterator first, InputIterator last){empty_init();while (first ! last){push_back(*first);first;}}//拷贝构造函数传统写法/*list(const listT lt){empty_init();for (auto e : lt)push_back(e);}*///交换函数void swap(listT temp){std::swap(_head, temp._head);}//拷贝构造函数的现代写法list(const listT lt){empty_init();listT temp(lt.begin(), lt.end());//复用迭代器区间构造让别人构造好了我再窃取革命成果swap(temp);}//assign(迭代器区间替换)template class InputIteratorvoid assign(InputIterator first, InputIterator last){clear();while (first ! last){push_back(*first);first;}}//assign(直接替换)void assign(size_t n, const T val){clear();for (size_t i n; i 0; --i)push_back(val);}//assign重载版本 防止间接寻址void assign(int n, const T val){clear();for (size_t i n; i 0; --i)push_back(val);}// 赋值重载的传统写法listT operator(const listT lt){assign(lt.begin(), lt.end());return *this;}// 赋值重载的现代写法//listT operator(listT lt)//{// swap(lt);//利用值传递拷贝的临时对象进行交换// return *this;//}//析构函数~list(){clear();delete _head;_head nullptr;}//sizesize_t size() const{size_t n 0;for (auto e : *this)n;return n;}//insertiterator insert(iterator pos, const T val){node* cur pos._node;//记录当前节点node* prev cur-_prev;//记录前驱节点node* newnode new node(val);//建立新节点//开始改变指向newnode-_next cur;cur-_prev newnode;prev-_next newnode;newnode-_prev prev;return iterator(newnode);}//eraseiterator erase(iterator pos){assert(pos ! end());//确保不是删除哨兵位置node* prev pos._node-_prev;node* next pos._node-_next;prev-_next next;next-_prev prev;delete pos._node;return iterator(next);//利用匿名对象返回}//pushback 尾插void push_back(const T val){insert(end(), val);}//pushfront 头插void push_front(const T val){insert(begin(), val);}//popback 尾删void pop_back(){erase(--end());}//popfront 头删void pop_front(){erase(begin());}//clear 只留一个头节点void clear(){iterator it begin();while (it ! end())it erase(it);}//resize 如果n小于当前容量的大小则内容将减少到前n个元素 当n大于容器大小时则在末尾插入任意容量的内容。void resize(size_t n, const T val T()){size_t sz size();//记录当前的有效元素的个数while (n sz){pop_back();--sz;}while (n sz){push_back(val);sz;}}//emptybool empty() const{return node-next node;}private:node* _head;//用来初始化 类内部自己用设私有void empty_init(){_head new node;_head-_next _head;_head-_prev _head;}}; 接口暂时就搞这些如果后面有时间再写些比较复杂的接口这一篇不太好理解讲解不到位还请见谅
