海拉尔做自己的网站,群晖nas可以做网站吗,门户网站开源,theme my login wordpress❤️欢迎来到我的博客❤️
前言 list是可以在常数范围内在任意位置进行插入和删除的序列式容器#xff0c;并且该容器可以前后双向迭代list的底层是双向链表结构#xff0c;双向链表中每个元素存储在互不相关的独立节点中#xff0c;在节点中通过指针指向其前一个元素和后…❤️欢迎来到我的博客❤️
前言 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素) list相比于vector在insert和erase上有很大的区别 vector想在第五个位置插入数据可以直接5
int main()
{vectorint v1;v1.push_back(1);v1.push_back(2);v1.push_back(3);v1.push_back(4);v1.push_back(5);v1.push_back(7);v1.insert(v1.begin() 5, 6);for (auto e : v1){cout e ;}cout endl;//输出结果为1 2 3 4 5 6 7return 0;
}而list想在第五个位置插入数据只能使用迭代器不可以直接5
int main()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);lt.push_back(7);//lt.insert(lt.begin() 5, 10);auto it lt.begin();for (size_t i 0; i 5; i){it;}lt.insert(it, 6);for (auto e : lt){cout e ;}cout endl;//输出结果为1 2 3 4 5 6 7return 0;
}list使用insert之后迭代器不会失效因为结点的位置没有发生改变 但list使用erase之后迭代器就会失效因为结点位置发生了改变结点已经被删除 排序相关 可以看到list单独提供了sort库里明明有一个sort为什么list还要单独提供呢 我们来试试 可以看到当我们使用库里的sort的时候编译报错了
我们转到库定义可以看到库里的sort用了一个last-first原理是快排需要三数取中但在链表中就不适合三数取中的场景
迭代器从功能的角度是会分类的他分为单向、双向和随机 单向可以进行 双向可以进行 /– 随机可以进行 /–//- 单向迭代器有forward_list / unordered_map / unordered_set 双向迭代器有list / map / set 随机迭代器有vector / string / deque 在形参的名字中就暗示了我们适合用哪一种算法比如reverse就适合用双向find适合用单向sort适合用随机 InputIteratorfind只写迭代器他在单向迭代器的上面也就是说单向 / 双向 / 随机都可以使用 双向迭代器reverse双向 / 随机可以使用 随机迭代器sort只有随机能用 容器的迭代器类型在文档中是有说明的 list vector set forward_list 在数据量大的情况下我们可以把list拷贝到vector中使用库里的排序再把数据拷贝回去效率更高我们来对比一下 数据个数为一千万
int main()
{srand(time(0));const int N 10000000;vectorint v;v.reserve(N);listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt2.push_back(e);lt1.push_back(e);}//拷贝到vectorint 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排序int begin2 clock();lt2.sort();int end2 clock();cout 使用vector排序 end1 - begin1 endl;cout 直接使用list排序 end2 - begin2 endl;return 0;
}可以看到效率差了近十倍所以在数据量特别大的时候就不要直接使用list排序了排少量数据则可以直接使用 merge 可以将两个链表归并前提是链表有序 unique 去重前提是链表有序 remove remove就是finderase如果要删除的值不存在则不进行任何操作 splice 可以把一个链表的内容转移到另一个链表直接把结点拿走
转移全部
int main()
{listint list1, list2;listint::iterator it;for (int i 1; i 4; i){list1.push_back(i); //list1:1 2 3 4}for (int i 1; i 3; i){list2.push_back(i * 10); //list2:10 20 30}cout list1转移前:;for (auto e : list1){cout e ;}cout endl;cout list2转移前:;for (auto e : list2){cout e ;}cout endl;it list1.begin();it;//2位置//把list2全部转移到list1中2之前的位置list1.splice(it, list2);cout list1转移后;for (auto e : list1){cout e ;}cout endl;cout list2转移后;for (auto e : list2){cout e ;}cout endl;return 0;
}转移某一个结点
//转移某一个结点
list1.splice(it, list2,list2.begin());部分转移
//部分转移
list1.splice(it, list2,list2.begin(),list2.end());自己转移自己
//把第二位置转移到第一个位置的前面
list1.splice(list1.begin(),list1,list1.begin());注意转移重叠位置会造成死循环 模拟实现list
基本框架
namespace List
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;//构造函数list_node(const T val T()) //缺省值不能给0因为T不一定是内置类型:_next(nullptr),_prev(nullptr),_val(val){}};templateclass Tclass list{typedef list_nodeT Node;public:list(){_head new Node;//哨兵位指向自己_head-_prev _head;_head-_next _head;}//尾插void push_back(const T x){Node* tail _head-_prev;//找尾Node* newnode new Node(x);//调用构造函数tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;}private:Node* _head;};void test1(){listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);}
}尾插
//尾插
void push_back(const T x)
{Node* tail _head-_prev;//找尾Node* newnode new Node(x);//调用构造函数tail-_next newnode;newnode-_prev tail;newnode-_next _head;_head-_prev newnode;
}迭代器
由于结点的地址不是连续的那我们的迭代器该如何设置呢这时候就要用到运算符重载 我们先来看迭代器的使用
listint::iterator it lt.begin();
while (it ! lt.end())
{cout *it ;it;
}
cout endl;那么我们的begin应该返回的是第一个数据的位置end在最后一个数据的下一个位置 迭代器是一个自定义类型这个自定义类型是一个结点的指针所以在list中他的迭代器需要自己设计而不是像vector或string那样使用原生指针不同平台下实现方式不同个别平台也可能对其进行二次封装也可能不是用原生指针实现作为迭代器原因如下 list 的元素在内存中不是连续存储的而是通过指针链接起来的。这意味着你不能简单地使用原生指针作为迭代器因为原生指针只能访问连续内存块中的元素list 的迭代器需要提供额外的功能如在链表中前进或后退这些操作涉及到修改指针以跳转到下一个或上一个元素。原生指针不支持这些操作因此需要自定义迭代器来实现自定义迭代器可以针对链表的特性进行优化。例如链表迭代器在插入或删除操作时只需要调整相邻元素的指针而不需要移动大量元素这使得链表在某些操作上比数组更高效list中插入或删除元素通常不会使迭代器失效除非删除的是迭代器指向的元素这与vector不同。自定义迭代器可以确保这些操作的正确性而原生指针无法提供这种保证自定义迭代器可以提供更好的封装性隐藏链表的内部实现细节这样即使链表的实现发生变化只要迭代器的接口保持不变使用迭代器的代码就不需要修改 begin和end
templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT iterator;iterator begin(){//单参数的构造函数支持隐式类型转换//return _head-_next;return iterator(_head-_next);}iterator end(){//return _head;return iterator(_head);}list(){_head new Node;//哨兵位指向自己_head-_prev _head;_head-_next _head;}private:Node* _head;
};* / / – / ! /
templateclass T
struct __list_iterator
{typedef list_nodeT Node;Node* _node;//用一个结点的指针构造一个迭代器__list_iterator(Node* node):_node(node){}T operator*(){//*it默认解引用是结点我们不想要结点我们要的是数据return _node-_val;}//迭代器返回的还是迭代器__list_iteratorT operator(){//我们想做的是让他走向下一个结点//原生指针是加一个结点的大小这样并不能到下一个结点的位置_node _node-_next;return *this;}//后置__list_iteratorT operator(int){__list_iteratorT 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;}bool operator!(const __list_iteratorT it){//使用结点的指针来进行比较return _node ! it._node;}bool operator(const __list_iteratorT it){//使用结点的指针来进行比较return _node it._node;}
};这样我们的迭代器就可以正常使用了
void test1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}int main()
{List::test1();return 0;
}运行效果
const迭代器 迭代器模拟的是指针的行为指针有2种const指针 1const T* ptr1; 指针指向的内容不能修改 2T* const ptr2;指针本身不能修改 const迭代器模拟的是第一种指针的行为 我们可以通过一个类型来控制返回值给不同的模板参数不同的实例化他们就是不同的类
templateclass T,class Ref//添加一个class Ref参数
struct __list_iterator
{Ref operator*()//返回值改为Ref{return _node-_val;}
}templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT,T iterator;//普通迭代器typedef __list_iteratorT, const T const_iterator;//const迭代器//提供const接口const_iterator begin() const{return const_iterator(_head-_next);}const_iterator end() const{return const_iterator(_head);}
};-
T* operator-()
{return _node-_val;
}struct A
{A(int a1 0,int a2 0):_a1(a1),_a2(a2){}int _a1;int _a2;
};void test1()
{listA lt;lt.push_back(A(1, 1));lt.push_back(A(2, 2));lt.push_back(A(3, 3));lt.push_back(A(4, 4));listA::iterator it lt.begin();while (it ! lt.end()){cout it-_a1 it-_a2 endl;it;}cout endl;
}运行效果 const迭代器也需要添加一个模板参数
//typedef __list_iteratorT,T,T* iterator;//普通迭代器
//typedef __list_iteratorT, const T,const T* const_iterator;//const迭代器
templateclass T,class Ref,class Ptrinsert insert默认都是在pos位置之前插入任意位置都可以所以insert不需要做检查 erase则需要检查因为哨兵位的结点不可删 //pos位置之前插入
iterator insert(iterator pos, const T x)
{//首先得换成结点的指针因为迭代器不好访问数据Node* cur pos._node;Node* prev cur-_prev; //前一个位置Node* newnode new Node(x); //新结点prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;return newnode;
}库里面的insert返回的是新插入位置的迭代器所以我们实现时和库里保持一致 erase
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; //返回下一个位置
}注意这里会存在迭代器失效的问题因为pos位置的结点已经被我们释放掉了所以我们需要返回下一个位置的迭代器而不是void 代码复用 当我们实现完insert和erase之后尾插、头插、尾删、头删都可以复用
尾插
//尾插
void push_back(const T x)
{//Node* tail _head-_prev;//找尾//Node* newnode new Node(x);//调用构造函数//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;//复用//尾插 - 在哨兵位的前面插入insert(end(), x);
}头插
void push_front(const T x)
{//头插//在第一个位置插入也就是begin的前面insert(begin(), x);
}尾删
void pop_back()
{//尾删erase(--end());
}头删
void pop_front()
{//头删erase(begin());
}size
size有两种实现方法
方法一
size_t size()
{size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;
}方法二 增加一个_size成员初始化为0每次插入_size每次删除–_size
size_t size()
{return _size;
}private:Node* _head;size_t _size;//增加成员clear和析构
void clear()
{//clear - 清除所有数据不清哨兵位iterator it begin();while (it ! end()){//这里erase之后就不能进行了因为他失效了//所以得接收返回值(返回值是下一个结点it erase(it);}
}析构可以直接复用clear
~list()
{//析构clear();delete _head;_head nullptr;
}测试一下
void test1()
{listint lt;lt.push_back(1);lt.push_back(2);lt.insert(lt.end(), 3);lt.push_back(4);lt.push_back(5);lt.erase(lt.begin());for (auto e : lt){cout e ;}cout endl;lt.push_front(1);for (auto e : lt){cout e ;}cout endl;lt.pop_front();lt.pop_back();for (auto e : lt){cout e ;}cout endl;lt.clear();lt.push_back(10);lt.push_back(20);for (auto e : lt){cout e ;}cout endl;cout size lt.size() endl;
}运行效果 拷贝构造和empty_init
拷贝构造
// lt2(lt1)
list(const listT lt)
{//初始化_head new Node;//哨兵位指向自己_head-_prev _head;_head-_next _head;//T对象不确定所以最好加上引用//遍历lt1把lt1的数据插入到lt2for (auto e : lt){push_back(e);}
}empty_init
void empty_init()
{_head new Node;//哨兵位指向自己_head-_prev _head;_head-_next _head;
}复用
list()
{empty_init();
}// lt2(lt1)
list(const listT lt)
{empty_init();//T对象不确定所以最好加上引用//遍历lt1把lt1的数据插入到lt2for (auto e : lt){push_back(e);}
}赋值和swap
void swap(listT lt)
{std::swap(_head, lt.head);
}赋值
listT operator(listT lt)
{//现代写法swap(lt);return *this;
}测试一下
void test2()
{listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2(lt1);for (auto e : lt2){cout e ;}cout endl;listint lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 lt3;for (auto e : lt1){cout e ;}cout endl;
}运行效果 完整代码
#pragma once
#includeiostream
#includeassert.husing namespace std;namespace List
{templateclass Tstruct list_node{list_nodeT* _next;list_nodeT* _prev;T _val;//构造函数list_node(const T val T()) //缺省值不能给0因为T不一定是内置类型:_next(nullptr),_prev(nullptr),_val(val){}};templateclass T,class Ref,class Ptrstruct __list_iterator{typedef list_nodeT Node;typedef __list_iteratorT, Ref,Ptr self;Node* _node;//用一个结点的指针构造一个迭代器__list_iterator(Node* node):_node(node){}Ref operator*(){//*it默认解引用是结点我们不想要结点我们要的是数据return _node-_val;}Ptr operator-(){return _node-_val;}//迭代器返回的还是迭代器self operator(){//我们想做的是让他走向下一个结点//原生指针是加一个结点的大小这样并不能到下一个结点的位置_node _node-_next;return *this;}//后置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;}bool operator!(const self it) const{//使用结点的指针来进行比较return _node ! it._node;}bool operator(const self it) const{//使用结点的指针来进行比较return _node it._node;}};templateclass Tclass list{typedef list_nodeT Node;public:typedef __list_iteratorT,T,T* iterator;typedef __list_iteratorT, const T,const T* const_iterator;iterator begin(){//单参数的构造函数支持隐式类型转换//return _head-_next;return iterator(_head-_next);}iterator end(){//return _head;return iterator(_head);}const_iterator begin() const{//单参数的构造函数支持隐式类型转换//return _head-_next;return const_iterator(_head-_next);}const_iterator end() const{//return _head;return const_iterator(_head);}void empty_init(){_head new Node;//哨兵位指向自己_head-_prev _head;_head-_next _head;}list(){empty_init();}// lt2(lt1)list(const listT lt){empty_init();//T对象不确定所以最好加上引用//遍历lt1把lt1的数据插入到lt2for (auto e : lt){push_back(e);}}void swap(listT lt){std::swap(_head, lt._head);}listT operator(listT lt){//现代写法swap(lt);return *this;}~list(){//析构clear();delete _head;_head nullptr;}void clear(){//clear - 清除所有数据不清哨兵位iterator it begin();while (it ! end()){//这里erase之后就不能进行了因为他失效了//所以得接收返回值(返回值是下一个结点it erase(it);}}//尾插void push_back(const T x){//Node* tail _head-_prev;//找尾//Node* newnode new Node(x);//调用构造函数//tail-_next newnode;//newnode-_prev tail;//newnode-_next _head;//_head-_prev newnode;//复用//尾插 - 在哨兵位的前面插入insert(end(), x);}void push_front(const T x){//头插//在第一个位置插入也就是begin的前面insert(begin(), x);}void pop_back(){//尾删erase(--end());}void pop_front(){//头删erase(begin());}//pos位置之前插入iterator insert(iterator pos, const T x){//首先得换成结点的指针因为迭代器不好访问数据Node* cur pos._node;Node* prev cur-_prev; //前一个位置Node* newnode new Node(x); //新结点prev-_next newnode;newnode-_next cur;cur-_prev newnode;newnode-_prev prev;return 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;}size_t size(){size_t sz 0;iterator it begin();while (it ! end()){sz;it;}return sz;}private:Node* _head;};void Print(const listint lt){listint::const_iterator it lt.begin();while (it ! lt.end()){//(*it) 1;cout *it ;it;}cout endl;}struct A{A(int a1 0,int a2 0):_a1(a1),_a2(a2){}int _a1;int _a2;};void test1(){listint lt;lt.push_back(1);lt.push_back(2);lt.insert(lt.end(), 3);lt.push_back(4);lt.push_back(5);lt.erase(lt.begin());for (auto e : lt){cout e ;}cout endl;lt.push_front(1);for (auto e : lt){cout e ;}cout endl;lt.pop_front();lt.pop_back();for (auto e : lt){cout e ;}cout endl;lt.clear();lt.push_back(10);lt.push_back(20);for (auto e : lt){cout e ;}cout endl;cout size lt.size() endl;}void test2(){listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint lt2(lt1);for (auto e : lt2){cout e ;}cout endl;listint lt3;lt3.push_back(10);lt3.push_back(20);lt3.push_back(30);lt3.push_back(40);lt1 lt3;for (auto e : lt1){cout e ;}cout endl;}
}以上就是本篇文章的全部内容了希望大家看完能有所收获
❤️创作不易点个赞吧❤️
