外贸网站优化价格,广西南宁做网站的公司,哈尔滨网站建设价格低,合肥网站建设市场分析#x1f47b;内容专栏#xff1a; C/C编程 #x1f428;本文概括#xff1a;list的介绍与使用、深度剖析及模拟实现。 #x1f43c;本文作者#xff1a; 阿四啊 #x1f438;发布时间#xff1a;2023.10.12 一、list的介绍与使用
1.1 list的介绍
cpluplus网站中有关… 内容专栏 C/C编程 本文概括list的介绍与使用、深度剖析及模拟实现。 本文作者 阿四啊 发布时间2023.10.12 一、list的介绍与使用
1.1 list的介绍
cpluplus网站中有关list的介绍 list的文档介绍 list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。list与forward_list非常相似最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
1.2 list的使用
list中的接口也比较多此处的学习也是类似只需要掌握如何正确的使用然后再去深入研究底层的原理已达到可扩展的能力。以下为list要学习的常用接口。
1.2.1 list的构造
构造函数constructor接口说明list (size_type n, const value_type val value_type()构造的list中包含n个值为val的元素list()无参构造listlist (const list x)拷贝构造函数template class InputIterator list (InputIterator first, InputIterator last用[firstlast)区间的元素构造list
以下为list的四种构造方式。我们通常使用迭代器遍历访问list由于list是一种双向链表不支持随机访问所以不能像数组一样使用[]操作符来访问元素。 代码演示
#includeiostream
#includelist
#includestring
#includevector
using namespace std;
//list的使用及测试
void test_list1()
{//无参初始化listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);listint::iterator it1 lt1.begin();while (it1 ! lt1.end()){cout *it1 ;it1;}cout endl;//n个val初始化liststring lt2(10,xxx);liststring::iterator it2 lt2.begin();while (it2 ! lt2.end()){cout *it2 ;it2;}cout endl;//迭代器区间初始化int arr[] { 10, 20, 30, 40 };listint lt3(arr, arr sizeof(arr) / sizeof(*arr));listint::iterator it3 lt3.begin();while (it3 ! lt3.end()){cout *it3 ;it3;}cout endl;//拷贝构造listint lt4(lt3);listint::iterator it4 lt4.begin();while (it4 ! lt4.end()){cout *it4 ;it4;}cout endl;}1.2.2 list iterator的使用
此处大家可暂时将迭代器理解为一个指针有关于迭代器我们还会在后面章节讲解到该指针指向list中的某个节点。
函数声明接口说明begin end返回第一个元素的迭代器返回最后一个元素下一个位置的迭代器rbegin rend返回第一个元素的reverse_iterator,即end位置返回最后一个元素下一个位置的reverse_iterator,即begin位置
注意⚠️
begin与end为正向迭代器对迭代器执行操作迭代器向后移动rbegin(end)与rend(begin)为反向迭代器对迭代器执行操作迭代器向前移动。
代码演示
// list迭代器的使用
// 注意遍历链表只能用迭代器和范围for
void PrintList(const listint l)
{// 注意这里调用的是list的 begin() const返回list的const_iterator对象for (listint::const_iterator it l.begin(); it ! l.end(); it){cout *it ;// *it 10; 编译不通过}cout endl;
}void test_list2()
{int array[] { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0 };listint l(array, array sizeof(array) / sizeof(array[0]));// 使用正向迭代器正向list中的元素// listint::iterator it l.begin(); // C98中语法auto it l.begin(); // C11之后推荐写法while (it ! l.end()){cout *it ;it;}cout endl;// 使用反向迭代器逆向打印list中的元素// listint::reverse_iterator rit l.rbegin();auto rit l.rbegin();while (rit ! l.rend()){cout *rit ;rit;}cout endl;
}1.2.3 list capacity
函数声明接口说明empty检测list是否为空是返回true否则返回falsesize返回list中有效节点的个数
1.2.4 list element access
函数声明接口说明front返回list的第一个节点中值的引用back返回list的最后一个节点中值的引用
1.2.5 list modifiers
函数声明接口说明push_front在list首元素前插入值为val的元素pop_front删除list中第一个元素push_back在list尾部插入值为val的元素pop_back删除list中最后一个元素insert在list position 位置中插入值为val的元素erase删除list position位置的元素swap交换两个list中的元素clear清空list中的有效元素resize改变size
代码演示
// list插入和删除
// push_back/pop_back/push_front/pop_front
void test_list3()
{int array[] { 1, 2, 3 };listint L(array, array sizeof(array) / sizeof(array[0]));// 在list的尾部插入4头部插入0L.push_back(4);L.push_front(0);PrintList(L);// 删除list尾部节点和头部节点L.pop_back();L.pop_front();PrintList(L);
}// insert /erase
void test_list4()
{int array1[] { 1, 2, 3 };listint L(array1, array1 sizeof(array1) / sizeof(array1[0]));// 获取链表中第二个节点auto pos L.begin();cout *pos endl;// 在pos前插入值为4的元素L.insert(pos, 4);PrintList(L);// 在pos前插入5个值为5的元素L.insert(pos, 5, 5);PrintList(L);// 在pos前插入[v.begin(), v.end)区间中的元素vectorint v{ 7, 8, 9 };L.insert(pos, v.begin(), v.end());PrintList(L);// 删除pos位置上的元素L.erase(pos);PrintList(L);// 删除list中[begin, end)区间中的元素即删除list中的所有元素L.erase(L.begin(), L.end());PrintList(L);
}// resize/swap/clear
void test_list5()
{// 用数组来构造listint array1[] { 1, 2, 3 };listint l1(array1, array1 sizeof(array1) / sizeof(array1[0]));PrintList(l1);// 交换l1和l2中的元素listint l2;l1.swap(l2);PrintList(l1);PrintList(l2);// 将l2中的元素清空l2.clear();cout l2.size() endl;
}1.2.6 operations
函数声明接口说明splice将元素从一个list转移到另一个listremove删除具体值元素unique删除重复值元素merge合并排序列表sort对list容器中的元素进行排序reverse逆置元素
对于sort的成员函数大家可能有疑问了算法库里面不是有sort吗为什么自己还需要另外实现一个sort呢 这里我们就需要讲解一下迭代器的分类问题了iterator 按功能上分为const修饰的正反向迭代器与非const修饰的正反向迭代器按性质上分为单向迭代器、双向迭代器、随机迭代器。 简单来说单向迭代器支持常见的容器有单链表、哈希表。双向迭代器支持/--常见的容器有双向链表、红黑树(map/set)随机迭代器支持/--//-常见的容器有vector、string、deque 观察算法库里的sort按形参说明就需要传入随机迭代器但是list容器的底层迭代器属于双向迭代器所以这里对于list的sort得自己写一个成员函数。
以下简单写一些操作接口稍微感受一下即可。
代码演示
void test_list6()
{listint l1;l1.push_back(1);l1.push_back(2);l1.push_back(3);l1.push_back(4);l1.push_back(5);listint::iterator it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;l1.reverse();it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;//sort(l1.begin(), l1.end()); errorl1.sort();it l1.begin();while (it ! l1.end()){cout *it ;it;}cout endl;listint l2;l2.push_back(1);l2.push_back(2);l2.push_back(3);l2.push_back(5);l2.push_back(2);l2.push_back(6);l2.push_back(7);l2.push_back(6);for (auto e: l2){cout e ;}cout endl;l2.sort();l2.unique();//对于不连续重复元素并不能达到去重效果需要先进行排序for (auto e : l2){cout e ;}cout endl;l2.remove(3); //删除容器中指定的元素for (auto e : l2){cout e ;}cout endl;}
void test_list7()
{listint mylist1, mylist2;listint::iterator it;// set some initial values:for (int i 1; i 4; i)mylist1.push_back(i); // mylist1: 1 2 3 4for (int i 1; i 3; i)mylist2.push_back(i * 10); // mylist2: 10 20 30it mylist1.begin();it; // points to 2cout mylist1:;for (auto e : mylist1){cout e ;}cout endl;cout mylist2:;for (auto e : mylist2){cout e ;}cout endl;cout ---------------------------------------- endl;mylist1.splice(it, mylist2); // mylist1: 1 10 20 30 2 3 4// mylist2 (empty)// it still points to 2 (the 5th element)cout mylist1:;for (auto e : mylist1){cout e ;}cout endl;cout mylist2:;for (auto e : mylist2){cout e ;}cout endl;cout ---------------------------------------- endl;mylist2.splice(mylist2.begin(), mylist1, it);// mylist1: 1 10 20 30 3 4// mylist2: 2// it is now invalid.cout mylist1:;for (auto e : mylist1){cout e ;}cout endl;cout mylist2:;for (auto e : mylist2){cout e ;}cout endl;cout ---------------------------------------- endl;mylist2.splice(mylist2.end(), mylist1, mylist1.begin(), mylist1.end());//mylist1: //mylist2:2 1 10 20 30 3 4cout mylist1:;for (auto e : mylist1){cout e ;}cout endl;cout mylist2:;for (auto e : mylist2){cout e ;}cout endl;}1.3 list的迭代器失效
前面说过此处大家可将迭代器暂时理解成类似于指针(实际迭代器并不一定是原生态指针在后面模拟实现list我们会了解其实是进行封装了的iterator)迭代器失效即迭代器所指向的节点的无效即该节点被删除了。因为list的底层结构为带头结点的双向循环链表因此在list中进行插入时是不会导致list的迭代器失效的只有在删除时才会失效并且失效的只是指向被删除节点的迭代器其他迭代器不会受到影响。
void TestListIterator1()
{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()){// erase()函数执行后it所指向的节点已被删除因此it无效在下一次使用it时必须先给其赋值//l.erase(it); errorit l.erase(it);it;}
}二、list的模拟实现
要模拟实现list必须要熟悉list的底层结构以及其接口的含义通过上面的学习这些内容已基本掌握现在我们来模拟实现list。
2.1 list_node 节点类
首先我们还是命令一个MyList的空间以表示与库里面的list进行区分。 首先使用struct封装每一个list的节点因为里面的前驱_prev与后继_next到时候在外面使用时需要进行外部访问所以我们将list_node封装为struct默认的限定符为public.
namespace MyList
{//list节点类templateclass Tstruct list_node{T _data;list_nodeT* _next;list_nodeT* _prev;list_node(const T val T()):_data(val), _next(nullptr), _prev(nullptr){}};
}2.2 list的框架
因为有过数据结构链表的基础这里多的细节不给大家详细介绍list给一个头节点指针_head即可有的版本也会给定一个_size用来记录链表的节点个数。 写一个empty_init函数表示空list的初始化工作构造函数直接调用它为什么不直接写到构造函数中这在后面其他地方也会用到。 对于push_back尾插一个节点元素我们不再像C语言那样写一个创建节点的函数而这里我们可以直接new一个Node节点类会去调用它的构造函数然后链接到list的最后一个节点双链表中头节点的前驱指针_head-_prev指向的就是最后一个节点。另外每每插入一个节点_size一下。
templateclass T
class list
{typedef list_nodeT Node;
public:void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}void push_back(const T val){Node* tail _head-_prev;Node* newnode new Node(val);newnode-_prev tail;tail-_next newnode;newnode-_next _head;_head-_prev newnode;_size;}size_t size(){return _size;}private:Node* _head;size_t _size;
};2.3 list迭代器
我们思考一下链表是怎么访问的呢可以像string、vector一样使用访问操作符[]吗答案是当然不能因为string、vector在内存空间中数据是连续存储的而list是利用内存中大量的空间内存碎片使用指针连接而成那么此时我们就需要用迭代器来访问了迭代器该怎么写呢难道可以像string、vector一样用原生指针表示吗答案依旧不行也正是因为list是非连续的内存存储结构使用原生指针作为迭代器会导致一些错误的内存访问这会导致程序崩溃或一些未定义行为因为C语言学过指针是涉及到算术运算的因此对于涉及到指针行为我们需要进行封装迭代器
这里大家可以简单查看一些stl库里面的list的头文件它的封装是如何命名与书写的文件已经上传到我的资源点击访问- 资源下载
库中将迭代器类命名为__list_iterator 我们将__list_iterator作为list迭代器实现的类以下简称迭代器类为了在类里面方便使用我们将节点类list_nodeT typedef 为 Node迭代器类里面我们只有一个_node指针成员构造函数参数当然也为Node*类型。
我们目的是将iterator封装通过迭代器访问list的每一个元素那么也就是达到和string、vector一样统一的访问效果如以下图中表示 图中的、*、!等等就是指针的一些行为。前面我们说过list属于双向迭代器有也有--操作接下来我们就需要用到operator操作符重载在日期类我们就实现过前置与后置有无一个int参数构成他们之间的函数重载前置返回自增之后的值后置返回自增之前的值提前将*this存储即可前置--与后置--操作类似我就不多赘述了。 _node _node-_next指针指向下一个节点。 _node _node-_prev指针指向前一个节点。 _node-_data:拿到迭代器指向的元素。
templateclass T
struct __list_iterator
{typedef list_nodeT Node;typedef __list_iterator Self;Node* _node;__list_iterator(Node* node){_node node;}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;}T operator*(){return _node-_data;}//当前迭代器对象的_node与s迭代器对象的_node进行比较bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}
};到这我们可以继续编写list类。 前面说过我们在使用的时候注意到了list还是涉及到迭代器失效的问题特别是erase删除数据之后迭代器指向的节点无效。在网站标准文档中还是给出了返回一个iterator值规避方法就是在下一次使用前必须先给其赋值。
库中insert返回值说明
库中erase返回值说明 list中beign与end的指向
templateclass T
class list
{typedef list_nodeT Node;
public:typedef __list_iteratorT iterator;void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;_size 0;}list(){empty_init();}~list(){clear();delete _head;_head nullptr;}iterator begin(){//return iterator(_head-_next);return _head-_next;}iterator end(){return _head;}void push_back(const T val){/*Node* tail _head-_prev;Node* newnode new Node(val);newnode-_prev tail;tail-_next newnode;newnode-_next _head;_head-_prev newnode;*/insert(end(), val);}void push_front(const T val){insert(begin(), val);}void pop_front(){erase(begin());}void pop_back(){erase(end()--);}void clear(){iterator it begin();while (it ! end()){it erase(it);it;}}iterator insert(iterator pos, const T val){Node* cur pos._node;Node* newnode new Node(val);// cur-prev newnode cur cur-_prev-_next newnode;newnode-_prev cur-_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;_size--;return iterator(next);}size_t size(){return _size;}private:Node* _head;size_t _size;
};测试
void test_list1()
{listintlt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;lt.insert(lt.begin(), 20);it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}打印结果
1 2 3 4 5
20 1 2 3 4 5在这里我们并不好实现const类型的迭代器并不是简单的const iterator原因为何待会需要结合其他知识说明。
2.4 拷贝构造与赋值重载
list的拷贝构造函数写法有许多种这里给出简单通俗的方式先调用empty_init()函数使用范围for循环给对象的每一个元素进行push_back即可注意我们没有写const类型的迭代器因此这里暂时去掉const至于const类型的迭代器我们待会讲解。
list的赋值重载函数我们可以复用写好的拷贝构造使用现代写法让编译器代替我们打工 //参数使用const修饰编译不通过因为范围for底层是利用了const的类型器而我们没有实现const类型的
//iteratorconst对象访问非const对象就会出现权利的放大编译出错
//list(const listT lt)
list(listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}lt1 lt2
//listT operator(const listT lt)
//{
// //传统写法
// if (*this ! lt)
// {
// clear();
// for (auto e : lt)
// {
// push_back(e);
// }
// }
// return *this;
//}void swap(const listT lt)
{std::swap(_head, lt._head);std::swap(_size, lt._size);
}
//lt1 lt2
listT operator(listT lt)
{//现代写法swap(lt);return *this;
}测试
void test_list2()
{listintlt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);lt.push_back(5);listint::iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;listintlt1(lt);listint::iterator it1 lt1.begin();while (it1 ! lt1.end()){cout *it1 ;it1;}cout endl;
}打印结果
1 2 3 4 5
1 2 3 4 52.5 list中存储自定义类型
若在list节点中存储自定义类型通过直接用*it的方式去访问自定义类型中的数据会报错究竟为什么呢 其实和vector一样编译器并不知道你要以哪种方式去打印是元素之间添加空格呢还是冒号分隔还是换行呢并不清楚你只能自己对于每个自定义类型中的数据进行处理操作。
错误示范
//像vector一样对自定义类型本身不支持流插入
//所以在test_list3中使用访问会出错
struct A
{A(int a 0,int b 0):_a(a),_b(b){}int _a;int _b;
};
void test_list3()
{listA lt;lt.push_back(A(1, 2));lt.push_back(A(2, 3));lt.push_back(A(3, 4));listA::iterator it lt.begin();while (it ! lt.end()){// error C2679: 二元“”: 没有找到接受“T”类型的右操作数的运算符(或没有可接受的转换)//cout *it ; //访问报错cout (*it)._a (*it)._b ;//访问运算符 自定义类型.自定义类型成员it;}cout endl;
}T* operator-()
{return _node-_data;
}让我们回顾一下指针访问内置类型和自定义类型的方式 所以对于自定义类型我们就可以在迭代器类中重载一个operator-函数:
T* operator-()
{//-优先级高于return _node-_data;
}
通过-访问自定义类型成员 通过迭代器it - 自定义类型成员就可以访问但是仔细想想咦为什么这里不是it--_a 其实显式调用的时候应该这么写it.operator-()-_a实际是因为这么写可读性不好编译器做了特殊处理省略掉了中间的-
void test_list3()
{listA lt;lt.push_back(A(1, 2));lt.push_back(A(2, 3));lt.push_back(A(3, 4));listA::iterator it lt.begin();while (it ! lt.end()){cout it-_a it-_b ;//显式地调用cout it.operator-()-_a it.operator-()-_b ;//本来应该是it--_a,但是这样写可读性不好于是编译器做了特殊处理省略了一个-it;}
}所以到这里我们更加深刻理解了为什么要封装iterator对于指针的行为、数据的访问使得更加灵活的访问使得vector、list、set等容器的遍历访问具有统一性。
2.6 const类型的迭代器
到这里迭代器类的封装我们已经写的差不多了不过对于刚才的疑惑const类型的迭代器我们该如何写是直接在迭代器iterator前加个const吗
例如这样这样子就是const修饰iterator本身了表示一旦初始化之后就不能修改了。我们想要的结果是类似于iterator的const_iterator他们两个本质是不同的对象const_iterator表示迭代器指向的内容是常量不可修改。也就是说我们实现的const_iterator只能读取容器中的元素不能修改。
const listint::iterator it lt.begin();而我们只有再封装一个const_iterator版本的对象: 本质是对通过迭代器拿到的元素不能做修改所以我们对于operator*和operator-的返回值加上const即可
templateclass T
struct __list_const_iterator
{typedef list_nodeT Node;typedef __list_const_iterator Self;Node* _node;__list_const_iterator(Node* node){_node node;}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;}//*it 1;const T operator*(){return _node-_data;}const T* operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}bool operator(const Self s){return _node s._node;}};但是大家不觉得这里的代码冗余度很高吗我们只是对细微处作了修改我们有没有什么办法简化一下呢没错就是改变模板参数列表。 那么怎么改呢我们看一下库中是如何写的 库中的模板参数列表给出了reference引用和pointer指针两个参数对于const_iteratorconst类型的迭代器我们只需在模板参数Ref和Ptr添加const修饰即可。
2.7 实现全容器的打印函数(深刻体会泛型编程的意义)
我们实现了const类型的迭代器之后可以将写一个打印list的函数
void print_list(const listint lt)
{listint::const_iterator it lt.begin();while (it ! lt.end()){*it;cout *it ;it;}cout endl;
}
void test_list4()
{listint lt;lt.push_back(1);lt.push_back(2);lt.push_back(3);lt.push_back(4);print_list(lt);
}以上结果能够正确打印但是对于liststring这种类型的对象以上函数也用不了故我们需要实现一个模板函数 listT是一个未实例化的模板直接通过访问listT类模板名 会报错因为编译器就无法判断listT::iterator是内嵌类型还是静态成员变量所以我们需要在其前面加一个typename意思是告诉编译器这是一个类型等到listT实例化后再去类里面读取。
//实例化
templatetypename T
//templateclass T
void print_list(const listT lt)
{//listT未示例化的类模板编译器不能去它里面去找//编译器就无法判断listT::iterator是内嵌类型还是静态成员变量//前面加一个typename就是告诉编译器这里是一个类型等到listT实例化后//再去类里面读取typename listT::const_iterator it lt.begin();while (it ! lt.end()){*it;cout *it ;it;}cout endl;
}对此我们还可以实现一个专门针对任意容器的打印函数。
templatetypename Container
void print_container(const Container con)
{typename Container::const_iterator it con.begin();while (it ! con.end()){cout *it ;it;}cout endl;
}测试
void test_list5()
{liststring lt;lt2.push_back(11111);lt2.push_back(11111);lt2.push_back(11111);lt2.push_back(11111);print_list(lt2); vectorstring v;v.push_back(22222);v.push_back(22222);v.push_back(22222);v.push_back(22222);print_container(v);
}打印结果
11111 11111 11111 11111
22222 22222 22222 22222三、list模拟实现源码
list深度剖析及模拟实现
