怎么用手机做网站平台,从做网站可以用现在的名称吗,途牛旅游网站建设背景,江阳建设集团网站List的使用
构造 与vector的区别
与vector的区别在于不支持 [ ]
由于链表的物理结构不连续,所以只能用迭代器访问
vector可以排序,list不能排序(因为快排的底层需要随机迭代器,而链表是双向迭代器)
(算法库里的排序不支持)(需要单独的排序)
list存在vector不支持的功能 链…List的使用
构造 与vector的区别
与vector的区别在于不支持 [ ]
由于链表的物理结构不连续,所以只能用迭代器访问
vector可以排序,list不能排序(因为快排的底层需要随机迭代器,而链表是双向迭代器)
(算法库里的排序不支持)(需要单独的排序)
list存在vector不支持的功能 链表的排序
vector可以用算法库里的sort排序,list不能用算法库里的sort排序排序(因为快排的底层需要随机迭代器,而链表是双向迭代器)
(算法库里的排序不支持)(需要单独的排序)
链表的排序效率要远低于算法库里的快排,因此链表的sort很少使用 即使将list拷贝会vector排序再拷贝回来,效率依旧大于直接在list中排序 升序 降序 去重(unique)
去除多个重复的数据,每个值只留一个
但是去重有一个前提,需要先排序,否则去不全 迭代器访问链表 list的剪切
将一个链表的内容转移(剪切)到另一个链表 也可以自己剪切自己,来把某个节点向前或后移动 list变为3 1 2 4
List的实现(双向带头循环)
链表基础结构 _head是双向带头循环链表的哨兵位(不存储有效数据)
list的迭代器
与vector不同,list在物理上是不连续的
因此不能像vector一样 因为这样iterator不能得到下一个节点
因此可以选择建立一个类来进行封装 可以在该类中重载 和 * 等运算符
是迭代器可以实现作用 但是注意不需要重载 和 - ,因为他们的效率很低
同时,迭代器类不需要写析构函数
因为节点不属于迭代器,只是需要用迭代器访问
节点是属于链表的
也不需要写拷贝构造(深拷贝),默认生成的浅拷贝就够了
因为没有写析构,所以也不存在析构两次的问题
-的重载
迭代器内还重载了 - 运算符
eg.
对于自定义类型 想要进行输出,又没有重载符号
方法一
比较原始的方法: 方法二 这里就是重载了 - 符号 从逻辑上讲
方法2应该有两个-,但是为了代码的可读性,省略了一个- const迭代器 采用引用传参一般会给参数加const,就产生了const迭代器
但是注意 所以需要单独写一个类,让迭代器可以修改,但它指向的内容不能修改(控制返回值)
该类与之前写的迭代器的类非常相似,唯一的区别就是operator* 和operator-的返回值不同
迭代器不能修改的核心行为是operator* 和operator- 控制operator* 和operator-的返回值,从而达成不能修改的目的 但是,以上两个类重复度很高,重写一个类过于浪费
因此可以采取新添加两个模板参数 写一个类模板,传不同的模板参数,来控制返回值
这样相当于利用模板生成了两个类,交给编译器来完成
提高了开发效率
插入insert 链表里的insert不存在迭代器失效的问题,因为它不存在扩容
pos指向的位置也不会变
删除erase erase存在迭代器失效的问题
是野指针失效
拷贝
默认的浅拷贝存在一定的问题
eg. 因为浅拷贝,指向同一块空间,会相互影响,析构两次
析构函数 这里用clear()清除数据
深拷贝 在范围for时,如果不确定遍历的类型,最好加引用
赋值 直接交换两个链表的头节点就行
因为传入的参数不是引用,lt是lt3的临时拷贝,使用完后就会释放
交换头节点后,不仅实现了赋值,还顺便将原链表析构了
initializer_list
为了支持{ }赋值,需要写一个initializer_list 参数不用加引用
因为initializer_list直接用{ }初始化,里面是常量数组
里面是直接用指针指向常量数组的开始和结束 模拟实现
#pragma once
#include iostream
using namespace std;
namespace bit
{templateclass Tstruct ListNode//定义一个链表节点的结构体//因为结构体内的东西全部公有,所以选择结构体,而不是类//一个类有公有私,用class,全部公有,用struct{ListNodeT* _next;ListNodeT* _prev;//结构体指针后加T模板,否则结构体指针就无法指向该类型的数据T _data;ListNode(const T data T())//初始化: _next(nullptr), _prev(nullptr), _data(data)//初始化列表{}};templateclass T, class Ref, class Ptrclass ListIterator{typedef ListNodeT Node;typedef ListIteratorT, Ref, Ptr Self;Node* _node;public://itListIterator(Node* node):_node(node){}Self operator()//前置{_node _node-_next;return *this;}Self operator--(){_node _node-_prev;return *this;}Self operator(int)//后置{Self tmp *this;_node _node-_next;return tmp;}Self operator--(int){Self tmp *this;_node _node-_prev;return tmp;}Ref operator*(){return _node-_data;}Ptr operator-(){return _node-_data;}bool operator!(const Self it){return _node ! it._node;}};//templateclass T//class ListConstIterator//{// typedef ListNodeT Node;// typedef ListConstIteratorT Self;// Node* _node;//public:// //it// ListIterator(Node* node)// :_node(node)// {}// Self operator()//前置// {// _node _node-_next;// return *this;// }// Self operator--()// {// _node _node-_prev;// return *this;// }// Self operator(int)//后置// {// Self tmp *this;// _node _node-_next;// return tmp;// }// Self operator--(int)// {// Self tmp *this;// _node _node-_prev;// return tmp;// }// const T operator*()// {// return _node-_data;// }// const T* operator-()// {// return _node-_data;// }// bool operator!(const Self it)// {// return _node ! it._node;// }//};templateclass Tclass list//链表{typedef ListNodeT Node;public:typedef ListIteratorT, T, T* iterator;typedef ListIteratorT, const T,const T* const_iterator;/* typedef ListConstIteratorT const_iterator;*/iterator begin(){return iterator(_head-_next);//传入匿名对象构造一个iterator类型的变量来返回}iterator end(){return iterator(_head);}void empty_init(){_head new Node();_head-_next _head;_head-_prev _head;}list(){/*_head new Node(T());_head-_next _head;_head-_prev _head;*/empty_init();} list(initializer_listT il){for (const auto e : il){push_back(e);}}//lt2(lt1)list(const listT It)//深拷贝构造{empty_init();for (const auto e : lt){push_back(e);}}//lt1 lt3listT operator(listT lt){swap(_head, lt._head);return *this;}~list(){clear();delete _head;_head nullptr;}void clear(){auto it begin();while (it ! end()){it erase(it);}}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;}void insert(iterator pos, const T x){Node* cur pos._node;Node* newnode new Node(x);Node* prev cur-_prev;prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;return iterator(newnode);}void erase(iterator pos){Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;prev-_next next;next-_prev prev;delete cur;return iterator(next);}private:Node* _head;};void test_list1(){listint It1;It1.push_back(1);It1.push_back(2);It1.push_back(3);It1.push_back(4);listint::iterator it It1.begin();while (it ! It1.end()){*it 10;cout *it ;it;}cout endl;}
}
