东莞技术支持 骏域网站建设,如何给网站做轮播图,营销型网站效果不好,免费手机网页网站1.list的介绍
list的文档介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代。 2. list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向 其前一个… 1.list的介绍
list的文档介绍
1. list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向 其前一个元素和后一个元素。 3. list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. 与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. 与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
list的基本结构图 2.list的使用 我们这里可以简单看一下文档里面关于list各种构造函数的介绍 2.1list的构造 目前我们只掌握这四种构造函数的使用方法
代码案例
#includeiostream
#includelistusing namespace std;void test_list1()
{listint lt1; //1.这里我们构造了一个空的list对象listint lt2(10, 100); // 2.这里我们通过用构造了10个100的方式构造了lt2//由于list不支持随机访问所以下面我们需要借助迭代器遍历一下lt2cout lt2中的元素遍历 endl;listint::iterator it lt2.begin();while (it ! lt2.end()){cout *it ;it;}cout endl;cout lt3拷贝lt2构造后的元素遍历 endl;listint lt3(lt2);listint::iterator its lt3.begin();while (its ! lt3.end()){cout *its ;its;}cout endl;listint lt4(lt3.begin(), lt3.end());cout lt4用lt3的迭代器区间构造后的元素遍历 endl;listint::iterator it1 lt4.begin();while (it1 ! lt4.end()){cout *it1 ;it1;}cout endl;}int main()
{test_list1();return 0;
}
代码运行结果 2.2 list 迭代器 iterator 的使用 迭代器分为正向迭代器和反向迭代器像begin() 和end()返回的是正向迭代器rbegin()和rend()返回的是反向迭代器然后这两种迭代器又可以和const进行结合形成上面c11新加的cbegin()和cend(),crbegin()和crend()其对应的迭代器名称也要跟着变化,我们可以看一下文档中的这些函数的说明, 注意
iterator T* 可读可写
const_iterator T* 只读
const iterator 这样实现是迭代器本身不能修改
const_iterator 重新定义的一个类型做到的是本身可以修改但是指向的内容不能修改 下面我们通过代码举个例子
测试代码
void test_list2()
{//迭代器的使用,我们就简单通过常用的正反向迭代器进行说明,//前面加了const的迭代器只需要记得不能修改迭代器所指向的内容//1.正向迭代器我们用简单的遍历list元素来说明listint lt;lt.push_back(1); //在list里面插入6个结点lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(6);cout 正向迭代器的遍历 endl;listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;// 2.反向迭代器listint::reverse_iterator rit lt.rbegin();cout 反向迭代器的遍历 endl;while (rit ! lt.rend()){cout *rit ;rit;}cout endl;}注意
1. begin与end为正向迭代器对迭代器执行操作迭代器向后移动2. rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动
2.3 list的容量大小接口的使用 代码测试
void test_list3()
{//empty()接口和size()接口的使用你会发现跟vector相比没有capacitylistint lt;cout empty(): lt.empty() endl;cout size(): lt.size() endl;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout 插入三个元素之后 endl;cout empty(): lt.empty() endl;cout size(): lt.size() endl;
}
运行结果 2.4 list访问头尾元素的接口 测试代码
void test_list4()
{//front()接口和 back()接口的测试listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);cout 遍历 endl;listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;cout 第一个元素 endl;cout lt.front() endl;cout 最后一个元素 endl;cout lt.back() endl;
} 测试结果 这个list底层是一个双向循环链表所以通过头结点访问到第一个元素和最后一个元素比较简单但是中间的元素就不支持随机访问了。
2.5 list Modifiers 我们先了解下以下这几个接口的使用方法 //头插
void push_front (const value_type val);//头删
void pop_front();//尾插
void push_back (const value_type val);//尾删
void pop_back();//在pos位置插入元素val
single element (1)
iterator insert (iterator position, const value_type val);//在pos位置插入n个元素val
fill (2) void insert (iterator position, size_type n, const value_type val);//在pos位置插入一段迭代器区间的结点
range (3)
template class InputIteratorvoid insert (iterator position, InputIterator first, InputIterator last);//删除pos位置的结点
iterator erase (iterator position);//删除一段迭代器区间的结点
iterator erase (iterator first, iterator last);//交换两个链表实际上只需要将头结点的指针跟大小size进行交换即可
void swap (list x);//将链表数据清空
void clear();
下面带大家来看看我们的使用案例
测试代码
void test_list5()
{listint lt;//尾插for (int i 0; i 10; i)//尾插后的结点值是0 1 2 3 4 5 6 7 8 9{lt.push_back(i);}//我们这里使用简单的范围for来进行遍历cout 尾插后链表中的结点值为 endl;for (auto e : lt)//范围for借助迭代器自动推导e的类型自动给e赋值自动往后{cout e ;}cout endl;//头插lt.push_front(10);lt.push_front(20); //头插这两个结点后变成20 10 0 1 2 3 4 5 6 7 8 9cout 头插后的链表结点值为 endl;for (auto e : lt){cout e ;}cout endl;//头删lt.pop_front();lt.pop_front();lt.pop_front(); //头删之后变成1 2 3 4 5 6 7 8 9cout 头删之后 endl;for (auto e : lt){cout e ;}cout endl;//尾删lt.pop_back();lt.pop_back();lt.pop_back(); //尾删之后变成 1 2 3 4 5 6cout 尾删之后 endl;for (auto e : lt){cout e ;}cout endl;//在pos位置插入一个值为val的结点listint::iterator it lt.begin();it;lt.insert(it, 20); //此时变成 1 20 2 3 4 5 6cout 在第2个结点位置插入一个20: endl;for (auto e : lt){cout e ;}cout endl;//在pos位置插入n个值为val的结点it;it;lt.insert(it, 5, 30);//在第4个结点的位置插入5个30cout 在第4个结点的位置插入5个30后 endl;for (auto e : lt){cout e ;}cout endl;//在pos位置插入一段迭代器区间listint lt2(10, 100);lt.insert(it, lt2.begin(), lt2.end());//将lt2的10个值为100的结点从lt的第4个结点插入cout 插入一段迭代器区间之后: endl;for (auto e : lt){cout e ;}cout endl;//删除pos位置的结点 这里我们会涉及一个迭代器失效的问题我们后面再说it lt.erase(it);cout 删除it位置的结点后 endl;for (auto e : lt){cout e ;}cout endl;//删除一段迭代器区间的结点it lt.erase(it, lt.end());//我们将it以及之后的结点都删除cout 将it后面位置的结点都删除了 endl;for (auto e : lt){cout e ;}cout endl;//交换两个链表//我们先看看lt和lt2的两个链表结点的值然后交换cout lt endl;for (auto e : lt){cout e ;}cout endl;cout lt2: endl;for (auto e : lt2){cout e ;}cout endl;//交换后lt.swap(lt2);cout 交换后 endl;cout lt endl;for (auto e : lt){cout e ;}cout endl;cout lt2: endl;for (auto e : lt2){cout e ;}cout endl;//将链表数据清空cout 将两个链表的数据都清空之后 endl;lt.clear();lt2.clear();cout lt endl;for (auto e : lt){cout e ;}cout endl;cout lt2: endl;for (auto e : lt2){cout e ;}cout endl;}测试结果 2.6 list的迭代器失效问题
前面说过此处大家可将迭代器暂时理解成类似于指针迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
void TestListIterator1()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));auto it l.begin();while (it ! l.end()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给//其赋值l.erase(it);it;}
}运行这段代码之后因为迭代器失效导致运行失败 所以当我们删除了某个结点之后迭代器需要重新赋值而为了解决这个问题给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);}
}
这样就没有什么大问题了 3. list 的模拟实现
#pragma once
#includestring
#includevector
#includeiostreamusing namespace std;
namespace mylist
{templateclass T//链表的每个结点的结构struct list_node {T _data; //存放数据list_nodeT* _prev;//指向前一个结点的指针list_nodeT* _next;//指向后一个结点的指针list_node(const T val T()) //构造一个结点对象:_data(val), _prev(nullptr), _next(nullptr){ }};// T T T*// T cosnt T const T*templateclass T,class Ref,class Ptrstruct __list_iterator //list的迭代器结构{typedef list_nodeT Node; //结点typedef __list_iteratorT,Ref,Ptr _self; //_self就是一个实例化的迭代器Node* _node; //结点的指针__list_iterator(Node* node):_node(node){}Ref operator*() //重载运算符* 通过*能够访问结点里面的数据{return _node-_data;}Ptr operator-() //重载- 结构体指针访问成员可以用结构体对象-结构体成员{return _node-_data;}_self operator() //重载运算符前置,返回下一个结点的迭代器{_node _node-_next;return (*this);}_self operator--() //重载运算符前置--,返回前一个结点的迭代器{_node _node-_prev;return (*this);}_self operator(int) //重载运算符后置,返回当前结点的迭代器的拷贝再{Node* tmp(_node);_node _node-_next;return tmp;}_self operator--(int) //重载运算符前置--,返回当前一个结点迭代器的拷贝再--{Node* tmp(_node);_node _node-_prev;return tmp;}bool operator!(const _self n) //重载迭代器的比较运算符!{return this-_node ! n._node;}bool operator(const _self n) //重载迭代器的比较运算符{return this-_node n._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT, T, T* iterator;typedef __list_iteratorT, const T, const T* const_iterator;const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}iterator begin(){return (_head-_next);}iterator end(){return _head;}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}void clear(){iterator it begin();while (it ! end()){it erase(it);}}void swap(listT lt){std::swap(_head, lt._head);std::swap(_size, lt._size);}list(){empty_init();}//lt1(lt2)list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}~list(){clear();delete _head;_head nullptr;}listint operator(listintlt){swap(lt);return *this;}void push_back(const T x){insert(end(), x);}void push_front(const T x){insert(begin(), x);}void pop_back(const T x){erase(--end());}void pop_front(const T x){erase(begin());}iterator 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;return iterator(newnode);}iterator erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;delete cur;prev-_next next;next-_prev prev;--_size;return iterator(next);}size_t size(){return _size;}private:Node* _head; //list的头结点size_t _size;//list的大小};
}
4. list和vector的比较
vector与list都是STL中非常重要的序列式容器由于两个容器的底层结构不同导致其特性以及应用场景不同其主要不同如下
