list容器
目录
begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()
使用这一块我会写的比较简洁，实在是前面vector和string已经写了很多相同的了
1.介绍（cv的，网上太多了）
1. list 是可以在常数范围内在任意位置进行插入和删除的序列式容器，并且该容器可以前后双向迭代。2. list 的底层是双向链表结构，双向链表中每个元素存储在互不相关的独立节点中，在节点中通过指针指向其前一个元素和后一个元素。3. list 与 forward_list 非常相似：最主要的不同在于 forward_list 是单链表，只能朝前迭代，已让其更简单高效。4. 与其他的序列式容器相比 (array ， vector ， deque) ， list 通常在任意位置进行插入、移除元素的执行效率更好。5. 与其他序列式容器相比， list 和 forward_list 最大的缺陷是不支持任意位置的随机访问，比如：要访问 list的第 6 个元素，必须从已知的位置 ( 比如头部或者尾部 ) 迭代到该位置，在这段位置上迭代需要线性的时间开销； list 还需要一些额外的空间，以保存每个节点的相关联信息 ( 对于存储类型较小元素的大 list 来说这可能是一个重要的因素 )
2.使用
2.1构造函数
//第一种常用 //第一个参数给数量，第二个参数给初始化的值，比如2个3 list<int>i(2,3); //3 3 //第二种常用 //给一个迭代器区间（可以是指针） list<int>i1(i.begin(), i.end()); //3 3 //第三种常用 //拷贝构造 list<int>l3(i1); //3 3 当然还有就是无参构造 list()另外，还有一个就是=的运算符重载
也就是说，可以这样写
list<int>i1(3,6); list<int>l3 = i1;//注意，这其实还是拷贝构造，赋值是两个都已存在的实体类之间 list<int>j; j = l3;//这才是赋值
2.2迭代器
begin(),end(),rbegin(),rend(),cbegin(),cend(),crbegin(),crend()
我们要知道，list是个双向循环的链表，也就是说，每个节点，都存在着前驱和后驱。
begin()和rend()，指向的就是第一个节点（有效节点）,rbegin()和end()指向的就是头结点（不存有效数据）
begin(),end()如果++，是向后移动，rbegin(),rend()是向前移动
至于加个c，纯粹就是const修饰的迭代器罢了
遍历方式
list没有[]的重载，因为list的每个元素，物理空间不一定连续，那么就不能用指针+-的方式来随机访问，因此这里只能用迭代器遍历的方式
list<int>i = { 2,3,4,5,6,6,7,8 }; list<int>::iterator it = i.begin(); while (it != i.end()) { cout << (*it) << " "; it++; } 或者范围for（但范围for本质还是迭代器）
2.3 容量
empty()
很经典的判断容器里面是否还未空，是返回true，否返回false
size()
返回有效数据个数
max_size()
返回最大能存的数据个数（取决于编译环境）
2.4元素遍历
front()
返回容器第一个元素，分两种重载，即非const和const（避免权限放大）
back()
返回容器最后一个元素，同样两种重载，非const和const（原因同理）
2.5修改
assign()
list<int>i = { 2,3,4,5,6,6,7,8 }; //void assign (size_type n, const value_type& val); list<int>c; c.assign(4, 5); //c : 5555 //注意是替换，不是追加 //template <class InputIterator> //void assign(InputIterator first, InputIterator last); c.assign(i.begin(), i.end()); //c:2,3,4,5,6,6,7,8 //注意，是替换，不是追加push_front()
就是在第一个元素前插入一个数据
pop_front()
删除第一个元素
push_back()
在最后插入一个数据
pop_back()
删除最后一个数据
insert()
list<int>i = { 2,3,4,5,6,6,7,8 }; //第一种 //iterator insert (iterator position, const value_type& val); //在迭代器指定位置插入一个数据 list<int>::iterator it = i.begin(); while (it != i.end()) { if ((*it) == 4)break; it++; } it=i.insert(it, 4); cout << (*it); cout << endl; //这个重载还会返回迭代器，比如插入了一个4，那返回的就是指向这个4的迭代器 //i: 2,3,4,4,5,6,6,7,8 //第二种 //void insert (iterator position, size_type n, const value_type& val); //注意，这个重载是插入多个相同值的元素 i.insert(it, 4,6); //i:2 3 4 6 6 6 6 4 5 6 6 7 8 it = i.begin(); list<int>c; //第三种,迭代器区间 //template <class InputIterator> //void insert(iterator position, InputIterator first, InputIterator last); c.insert(c.begin(),i.begin(), i.end()); //c::2 3 6 6 6 6 4 4 5 6 6 7 8erase()
list<int>i = { 2,3,4,5,6,6,7,8 }; list<int>::iterator it = i.begin(); while ((*it) != 4)it++; //第一种 //iterator erase (iterator position); //删除迭代器指向数据，返回删除之后，新的原相对位置的数据的迭代器 it=i.erase(it); //i:2 3 5 6 6 7 8 //第二种，删除迭代器区间的元素 //iterator erase (iterator first, iterator last); while ((*it) != 6)it++; i.erase(it, i.end()); //i:2 3 5swap()
简单的交换
resize()
扩容
void resize (size_type n, value_type val = value_type()); 给n个空间大小，初始化值val 这里是调用无参构造clear()
清空容器
2.6操作
reverse()
经典的逆置函数
list<int>i = { 2,3,4,5,6,6,7,8 }; i.reverse(); //i:8 7 6 6 5 4 3 2sort()
排序，默认从小到大排，你可以自己写个规则,用法跟algorithm的sort()一样
之所以单独提供，是因为链表的物理空间不连续，而算法库的sort是针对连续物理空间的
而且算法库用的是快排，而链表这里用的是归并
平时用的话，速度还不如直接拷贝到vector，用算法库的sort之后，再拷贝回链表快
merge()
合并两个有序的链表，注意一定要有序，然后根据规则（默认从小到大），跟algorithm的sort()一样.
unique()
去重，注意，相同的必须紧邻，所以你可以先sort()，如果为了适配自定义类型，可以自己写个规则，跟algorithm的sort()一样
remove()
跟erase的最大区别就是，不用给迭代器，只用给值，相当于容器自己找
remove_if()满足条件才删除
splice()
list<int>i = { 2,3,4,5,6,6,7,8 }; list<int>b = { 6,7,8,9,0,34,12,1 }; //第一种 //void splice (iterator position, list& x); //直接把x的所有节点都转移过去，x变空 i.splice(i.begin(), b); //i:6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8 //void splice (iterator position, list& x, iterator i); list<int>c= { 6,7,8,9,0,34,12,1 }; i.splice(i.begin(), c, c.begin()); //i:6 6 7 8 9 0 34 12 1 2 3 4 5 6 6 7 8 //是将第二个参数指向的链表中的最后一个参数的位置的值转移过去 //c的第一个6会没掉 //void splice (iterator position, list& x, iterator first, iterator last); //这个就不示范了，就是把一个区间的节点转移过去注意，可以自己转移自己，就是在一个链表里面转移
3.模拟
反向迭代器，我在这里先不实现，等后面另一篇文章的时候再补充上去
#pragma once #include<assert.h> namespace manba { //注意，这个是节点的类，我们实现的是双向带头链表，所以要有前驱和后驱 template<class T> struct ListNode { ListNode<T>* _next;//前驱 ListNode<T>* _prev;//后驱 //注意<>在类里面，是可以忽略的，但我们严谨一些 T _data;//存数据 ListNode(const T& x=T())//默认构造函数，方便后面调用,因为不确定参数类型，所以默认值 //直接用T类型的默认构造即可，不管是内置还是自定义都可以符合 :_next(nullptr) , _prev(nullptr) , _data(x) {} }; //这里通过Ref，第二个模板参数，简约的实现了const迭代器和正常迭代器的转换 //ptr控制的是配合重载->，区分const迭代器和普通迭代器 template<class T,class Ref,class Ptr> struct _list_iterator { typedef ListNode<T> Node; //注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点 typedef _list_iterator<T,Ref,Ptr> self; //跟上面一个同理,这里是一个链表迭代器类型 Node* _node; //迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++ //而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器 //重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走 _list_iterator(Node* node)//这里是默认构造，方便各种调用 :_node(node) {} //前置++ self& operator++() { _node = _node->_next; return *this; } //后置++ //注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型 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; } //解引用,利用ref，实现const迭代器和普通迭代器 Ref operator*() { return _node->_data; } //不等于 bool operator !=(const self& s) { return _node != s._node; } //等于 bool operator==(const self& s) { return _node == s._node; } Ptr operator->() { return &_node->_data; } /*struct AA { int b; AA(int a = 1) :b(a) { } };*/ /*manba::List<manba::AA> l1; l1.push_back(3); l1.push_back(7); l1.push_back(9); l1.push_back(12); manba::List<manba::AA>::iterator it = l1.begin(); while (it != l1.end()) { cout << it.operator->()->b << endl; cout<<it->b<<endl; it++; } cout << endl;*/ }; //const迭代器 //template<class T> //struct _list_const_iterator { //typedef ListNode<T> Node; ////注意，类名<T>才是一个链表节点类型，这里重命名一下，方便后面少写点 //typedef _list_const_iterator<T> self; ////跟上面一个同理,这里是一个链表迭代器类型 //Node* _node; ////迭代器本质还是指针，只是因为原始指针针对物理空间不连续的容器，无法实现++ ////而我们无法重载指针，所以我们采用封装的方式，将指针封装起来，将封装起来的迭代器 ////重载前后置++，前后置--，解引用*等运算符，理由前驱后驱指针，实现向前向后走 //_list_const_iterator(Node* node)//这里是默认构造，方便各种调用 //:_node(node) //{} ////前置++ //self& operator++() //{ //_node = _node->_next; //return *this; //} ////后置++ ////注意，这里我们返回的时候不用&，因为tmp是局部变量，函数结束后会销毁，所以直接返回迭代器类型 //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; //} ////解引用 //const T& operator*() //{ //return _node->_data; //} ////不等于 //bool operator !=(const self& s) //{ //return _node != s._node; //} ////等于 //bool operator==(const self& s) //{ //return _node == s._node; //} //}; template<class T> class List { typedef ListNode<T> Node; public: typedef _list_iterator<T,T&,T*> iterator; //typedef _list_const_iterator<T> const_iterator; //这里迭代器直接传const类型的模板参数 typedef _list_iterator<T, const T&,const T*> const_iterator; //跟上面一样 //空链表初始化 void empty_init() { _head = new Node; _head->_next = _head; _head->_prev = _head; } //默认构造函数 List() { empty_init(); } //拷贝构造函数 //List(const List<T> &cp) List(List<T>& cp) { empty_init(); for (const auto& e : cp) { push_back(e); } } //交换函数,交换物理地址 void swap(List<T>&t) { std::swap(_head, t._head); } //赋值 //第一种 //List<T>& operator=(const List<T>& t2) /*List<T>& operator=( List<T>& t2) { if (this != &t2) { clear(); for (const auto& e : t2) { push_back(e); } } return *this; }*/ //第二种 //这个方法的妙处在于，因为外面要赋值的链表是直接通过拷贝构造直接给了t2链表 // ，也就是传值。 //而拷贝构造我们用的是深拷贝，这样t2的空间和外面的类是不一样的，如此，直接 //让this链表和t2交换，函数结束之后，t2作为局部变量，t2会自动调用析构函数。 List<T>& operator=(List<T> t2) { swap(t2); return *this; } //返回第一个有效节点的迭代器 iterator begin() { return _head->_next; } iterator end() { return _head; } //返回第一个有效节点的const迭代器 const_iterator begin() const { return _head->_next; } const_iterator end() const { return _head; } //尾插 void push_back(const T& x) { insert(iterator(_head), x); } //头插 void push_front(const T& x) { insert(begin(), x); } //尾删 void pop_back() { erase(--end()); } //头删 void pop_front() { erase(begin()); } //在指定位置前面插入 //vector 迭代器在insert会失效，list不会 iterator insert(iterator pos, const T& x) { Node* cur = pos._node; Node* prev = cur->_prev; Node* newnode = new Node(x); prev->_next = newnode; newnode->_prev = prev; newnode->_next = cur; cur->_prev = newnode; return iterator(newnode); } //删除指定位置 iterator erase(iterator pos) { assert(pos != end()); Node* cur = pos._node; Node* prev = cur->_prev; Node* next = cur->_next; prev->_next = next; next->_prev = prev; delete cur; return next; } //注意，vector在insert和erase处都会有迭代器失效的风险，所以要注意返回值。 //而list在insert处不会，不用担心，但是erase处就要考虑这个问题了，要注意接收返回值。 //更详细的，可以参考我在vector文章里，vector的模拟中对insert和erase的模拟。 //另外补充一下，vector处的erase会出现迭代器失效，主要是针对vs的强制检查和如果删除了最后一个 //元素，会导致迭代器超出了数组有效范围。 //而对于list的erase，因为链表底层物理不一定是连续的，这样原迭代器封装的指针指向的空间是非法空间， //所以要注意返回值。 //清空链表 void clear() { iterator it = begin(); while (it != end()) { it = erase(it); } } //析构函数 ~List() { clear(); delete _head; _head = nullptr; } private: Node* _head; //头结点，注意，整个list是左闭右开，head是也是end()返回的 }; }
原文地址：https://blog.csdn.net/MXZSL/article/details/138398480
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！