苏州网站设计kgwl,天津建设银行官网站,丽江市住房与城乡建设局网站,pageadmin wordpress本节博客先对list进行用法介绍#xff0c;再在库的基础上简化其内容和形式#xff0c;简单进行模拟实现#xff0c;有需要借鉴即可。 目录 1.list介绍1.1 list概述1.2相关接口的介绍 2.简化模拟实现3.各部分的细节详述3.1结点3.2迭代器细节1#xff1a;迭代器用原生指针还是… 本节博客先对list进行用法介绍再在库的基础上简化其内容和形式简单进行模拟实现有需要借鉴即可。 目录 1.list介绍1.1 list概述1.2相关接口的介绍 2.简化模拟实现3.各部分的细节详述3.1结点3.2迭代器细节1迭代器用原生指针还是专门设计为类的问题细节2迭代器、--行为重载的返回类型问题细节3迭代器解引用返回类型细节4迭代器operator-重载 3.3链表细节1list中提供begin和end函数的理由和返回类型细节2插入元素代码细节3删除元素代码细节4clear()函数和析构函数细节5拷贝构造函数与赋值运算符重载细节6insert返回为void 4.总结 1.list介绍
1.1 list概述
1.概述list是可以在常数范围内在任意位置进行插入和删除的序列式容器并且该容器可以前后双向迭代。 2. 底层实现list的底层是双向链表结构双向链表中每个元素存储在互不相关的独立节点中在节点中通过指针指向其前一个元素和后一个元素。 3. list与forward_list区别最主要的不同在于forward_list是单链表只能朝前迭代已让其更简单高效。 4. list的优势与其他的序列式容器相比(arrayvectordeque)list通常在任意位置进行插入、移除元素的执行效率更好。 5. list的缺陷与其他序列式容器相比list和forward_list最大的缺陷是不支持任意位置的随机访问比如要访问list的第6个元素必须从已知的位置(比如头部或者尾部)迭代到该位置在这段位置上迭代需要线性的时间开销list还需要一些额外的空间以保存每个节点的相关联信息(对于存储类型较小元素的大list来说这可能是一个重要的因素)
我们用代码来体会一下list的缺点
void test_op1()
{srand(time(0));const int N 1000000;//一百万数据//两个链表listint lt1;listint lt2;//一个顺序表vectorint v;//生成随机数据尾插到链表1和顺序表v中去for (int i 0; i N; i){auto e rand()i;//加上这个i主要是为了减少重复数字概率lt1.push_back(e);v.push_back(e);}//vector排序int begin1 clock();sort(v.begin(), v.end());int end1 clock();//list排序int begin2 clock();lt1.sort();int end2 clock();//打印比较两者用时printf(vector sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}void test_op2()
{srand(time(0));const int N 1000000;listint lt1;listint lt2;for (int i 0; i N; i){auto e rand();lt1.push_back(e);lt2.push_back(e);}// 拷贝vectorint begin1 clock();vectorint v(lt2.begin(), lt2.end());// 排序sort(v.begin(), v.end());// 拷贝回lt2lt2.assign(v.begin(), v.end());int end1 clock();//lt1排序int begin2 clock();lt1.sort();int end2 clock();//打印printf(list copy vector sort copy list sort:%d\n, end1 - begin1);printf(list sort:%d\n, end2 - begin2);
}1.2相关接口的介绍 2.简化模拟实现
通过去查看stl中list.h的源码我们可以知道list是通过一个_head的Node*指针进行维护的而其中广泛使用迭代器进行传值和访问数据。下面对其先直接摆代码然后对其中细节进行详细介绍。
#pragma once#includeassert.h
#includeiostreamnamespace zzg
{templatetypename Tstruct ListNode{ListNodeT* _next;//这个地方为什么类型不是T*答因为我们指针是需要指向一个ListNodeT*类型的而非T类型。ListNodeT* _prev;T _data;//ListNode有参构造ListNode(const T x T()):_next(nullptr),_prev(nullptr), _data(x){} };templateclass T, class Ref, class Ptrclass list_iterator{typedef struct ListNodeT Node;typedef list_iteratorT, Ref, Ptr Self;public:Node* _node;public://带参构造list_iterator(Node* node)//这个地方用值拷贝用引用会有bug:_node(node){}//Self operator(){_node _node-_next;return *this;}Self operator(int)//后置{Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。_node _node-_next;return temp;//这个地方得返回值了因为现在的Self已经变了}//--Self operator--(){_node _node-_prev;return *this;}Self operator--(int)//后置--{Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。_node _node-_prev;return temp;//这个地方得返回值了因为现在的Self已经变了}//*itRef operator*(){return _node-_data;}//!bool operator!(const Self it) {return _node ! it._node;}//bool operator(const Self it){return _node it._node;}//-重载Ptr operator-(){return _node-_data;}};//templatetypename T//class list_const_iterator//{// typedef struct ListNodeT Node;// typedef list_const_iteratorT Self;//public:// Node* _node;//public:// //带参构造// list_const_iterator(Node* node)//这个地方用值拷贝用引用会有bug// :_node(node)// {}// //// Self operator()// {// _node _node-_next;// return *this;// }// Self operator(int)//后置// {// Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。// _node _node-_next;// return temp;//这个地方得返回值了因为现在的Self已经变了// }// //--// Self operator--()// {// _node _node-_prev;// return *this;// }// Self operator--(int)//后置--// {// Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。// _node _node-_prev;// return temp;//这个地方得返回值了因为现在的Self已经变了// }// //*it// const T operator*()// {// return _node-_data;// }// //!// bool operator!(const Self it)// {// return _node ! it._node;// }// //// bool operator(const Self it)// {// return _node it._node;// }// //-重载// const T* operator-()// {// return _node-_data;// }//};templatetypename Tclass list{public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;typedef struct ListNodeT Node;private:Node* _head;//头节点public://无参构造函数list(){empty_init();}//拷贝构造list(const listT lt){empty_init();for (auto e : lt){push_back(e);}}// lt1 lt3listT operator(listT lt)//先调用拷贝构造构造出一个lt来{swap(lt);//然后交换这个局部变量与this原this中是其他的东西return *this;//返回this本身}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}//清理函数void clear(){iterator it begin();while (it ! end()){it erase(it);}}//析构函数~list(){clear();delete _head;_head nullptr;}iterator begin(){return _head-_next;//隐式类型转换//return iterator(_head-_next);}iterator end(){return _head;//隐式类型转换//return iterator(_head);}//const 迭代器 -- 迭代器本身不可修改//我们需要的迭代器指向的内容不可修改 const T*类型 而不是 T* const类型//如果我们直接在一般迭代器前面const,即const iterator -- 该迭代器不可修改因为这是一个自定义类//解决直接再单独一个自定义const迭代器类出来const_iterator begin() const{return _head-_next;//return iterator(_head-_next);}const_iterator end() const{return _head;//return iterator(_head);}//尾插void push_back(const T x){insert(end(), x);}//头插void push_front(const T x){insert(begin(), x);}//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 val){Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;}//任意删除iterator 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);}//尾删void pop_back(){erase(--end());}//头删void pop_front(){erase(begin());}};struct A{public:int _a;int _b;A(int a 0, int b 0){_a a;_b b;}};//测试函数void test_list1(){/*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(6);lt.pop_back();lt.pop_back();lt.pop_back();listint::iterator it lt.begin();while (it ! lt.end()){std::cout *it ;it;}std::cout std::endl;*/listA Al;Al.push_back({ 1,1 });Al.push_back({ 2,2 });Al.push_back({ 3,3 });Al.push_back({ 4,4 });Al.push_back({ 5,5 });Al.push_back({ 6,6 });listA::iterator it Al.begin();while (it ! Al.end()){//std::cout (*it)._a / (*it)._b std::endl;std::cout it-_a / it-_b std::endl;//it-_a --- it--_a it.operator-()-_a;it;}std::cout std::endl;}
}
3.各部分的细节详述
主要包含三个部分一是整体的链表类二是链表中的每个元素结点类还有就是用来访问修改结点的迭代器类。
下面分开进行细节介绍。
3.1结点
每个结点我们很熟悉无非是两个指针和一个数据一个指针指向它前面的结点另一个指向其后面的结点数据中放具体元素的值。
下面是基本结构框架
templatetypename T
struct ListNode
{ListNodeT* _next;//这个地方为什么类型不是T*答因为我们指针是需要指向一个ListNodeT*类型的而非T类型。ListNodeT* _prev;T _data;//ListNode有参构造ListNode(const T x T()):_next(nullptr),_prev(nullptr), _data(x){}
};细节
使用struct标注为公有属性方便外部调用list是带头双向循环链表因而每个结点要有两个指针提供全缺省的默认构造函数
思考每个结点的两个指针为什么是ListNode*类型而不是T*类型呢 答因为我们每个结点的指针指向的是一个结点T仅仅是一个结点中的数据而已。
3.2迭代器
templateclass T, class Ref, class Ptr
class list_iterator
{typedef struct ListNodeT Node;typedef list_iteratorT, Ref, Ptr Self;
public:Node* _node;
public://带参构造list_iterator(Node* node)//这个地方用值拷贝用引用会有bug:_node(node){}
}细节1迭代器用原生指针还是专门设计为类的问题
思考list迭代器为什么要专门设置一个类 答 这是由于list的每个节点物理空间不连续导致迭代器不能像之前string\vector那样简单的设计为原生指针而是设计为一个类以此来扩大我们对迭代器行为控制权限重新设计*-,等操作。
vectorstring原生指针充当迭代器 像之前stringvector这种容器其原生指针T*就是天然的迭代器因为就会自动指向到下一个数据*引用也是拿到的我们想要的数据。 但是在list中我们T*很明显由于地址不连续的缘故压根不知道会指向的是什么(大概率会是随机值)。
但是需要重点注意的是我们所设计的迭代器类是模拟的string/vector中T*的动作。
细节2迭代器、–行为重载的返回类型问题
//
Self operator()
{_node _node-_next;return *this;
}Self operator(int)//后置
{Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。_node _node-_next;return temp;//这个地方得返回值了因为现在的Self已经变了
}
//--
Self operator--()
{_node _node-_prev;return *this;
}Self operator--(int)//后置--
{Self temp *this;//拷贝构造一份这时候会调用编译器自动生成的拷贝构造为浅拷贝但是需求满足了。_node _node-_prev;return temp;//这个地方得返回值了因为现在的Self已经变了
}思考为什么前置返回的是类对象引用而后置返回类型是一般类型 答这要结合函数设计来看在前置中我们返回的是类本身而后置我们返回的是一个局部的类对象局部类对象在出函数后会自动销毁。
细节3迭代器解引用返回类型
//*it
Ref operator*()
{return _node-_data;
}注
//iterator:
typedef list_iteratorT, Ref, Ptr Self;
//list:
typedef list_iteratorT, T, T* iterator;
typedef list_iteratorT, const T, const T* const_iterator;返回Ref用来区分const_iterator 和 iterator。
思考为什么不重载const iterator? 答const 类 -- 表示该指针不可修改并非我们所期望的指针指向内容不可修改。
思考iterator 与 const_iterator 是同一个类吗 答不是。是利用同一份类模板生成的完全不同两份类。
细节4迭代器operator-重载
//-重载
Ptr operator-()
{return _node-_data;
}注
//iterator:
typedef list_iteratorT, Ref, Ptr Self;
//list:
typedef list_iteratorT, T, T* iterator;
typedef list_iteratorT, const T, const T* const_iterator;struct A
{
public:int _a;int _b;A(int a 0, int b 0){_a a;_b b;}
};main:
listA Al;
Al.push_back({ 1,1 });
Al.push_back({ 2,2 });
Al.push_back({ 3,3 });
Al.push_back({ 4,4 });
Al.push_back({ 5,5 });
Al.push_back({ 6,6 });listA::iterator it Al.begin();
while (it ! Al.end())
{//std::cout (*it)._a / (*it)._b std::endl;std::cout it-_a / it-_b std::endl;//it-_a --- it--_a it.operator-()-_a;it;
}
std::cout std::endl;为了可读性编译器把it--_a优化为了it-_a
思考上述代码的it--_a代表了什么 答it-_a — it--_a it.operator-()-_a;这里在编译器写法上理论上应该写两个箭头的一个用于运算符重载函数的调用另一个是为了进入到指针里面访问数据这里编译器为了可读性将其优化为了一个箭头。
3.3链表
链表类主要结构如下
templatetypename T
class list
{
public:typedef list_iteratorT, T, T* iterator;typedef list_iteratorT, const T, const T* const_iterator;typedef struct ListNodeT Node;//无参构造函数list(){empty_init();}void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}private:Node* _head;//头节点
}细节1list中提供begin和end函数的理由和返回类型
iterator begin()
{return _head-_next;//隐式类型转换//return iterator(_head-_next);
}iterator end()
{return _head;//隐式类型转换//return iterator(_head);
}//const 迭代器 -- 迭代器本身不可修改
//我们需要的迭代器指向的内容不可修改 const T*类型 而不是 T* const类型
//如果我们直接在一般迭代器前面const,即const iterator -- 该迭代器不可修改因为这是一个自定义类
//解决直接再单独一个自定义const迭代器类出来
const_iterator begin() const
{return _head-_next;//return iterator(_head-_next);
}const_iterator end() const
{return _head;//return iterator(_head);
}思考list提供begin和end的原因 答 1._head是私有的。 2.更加方便的使用迭代器在上面代码我们可以发现返回的都是迭代器类型。
返回迭代器类型的原因 与后面使用迭代器相兼容。
细节2插入元素代码
//尾插
void push_back(const T x)
{insert(end(), x);
}
//头插
void push_front(const T x)
{insert(begin(), x);
}//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 val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;
}细节3删除元素代码
//任意删除
iterator 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);
}
//尾删
void pop_back()
{erase(--end());
}
//头删
void pop_front()
{erase(begin());
}思考为什么erase()要返回迭代器类型 答因为要及时对外更新迭代器指针防止迭代器失效。
思考为什么pop_back()没有返回迭代器类型 答因为pop_back()不会对外接收迭代器不存在对外更新迭代器问题。但是erase是接收迭代器的因而要及时更新。 思考–end()是否会影响到_head为什么 答会影响到但是影响到的是_head的值拷贝没有影响到“母体”。
细节4clear()函数和析构函数
void empty_init()
{_head new Node;_head-_next _head;_head-_prev _head;
}//清理函数
void clear()
{iterator it begin();while (it ! end()){it erase(it);}
}//析构函数
~list()
{clear();delete _head;_head nullptr;
}细节5拷贝构造函数与赋值运算符重载
//拷贝构造
list(const listT lt)
{empty_init();for (auto e : lt){push_back(e);}
}// lt1 lt3
listT operator(listT lt)//先调用拷贝构造构造出一个lt来
{swap(lt);//然后交换这个局部变量与this原this中是其他的东西return *this;//返回this本身
}思考为什么赋值运算符重载函数参数用list lt而不是引用呢 答复用拷贝构造函数是为现代写法。
细节6insert返回为void
//任意插入
void insert(iterator pos, const T val)
{Node* cur pos._node;Node* prev cur-_prev;Node* newnode new Node(val);prev-_next newnode;newnode-_prev prev;newnode-_next cur;cur-_prev newnode;
}在string中insert我们返回的是迭代器但是这里为什么返回值是void呢 答因为string是连续空间插入数据会挪动数据造成迭代器失效。但是链表是由结点链接而成插入数据不会挪动数据不会造成迭代器失效问题。
在vector中 insert/erase因为增删都会牵扯到数据挪动问题两个函数肯定都要去返回迭代器来更新外部迭代器。 但是对于listinsert不会挪动数据因而不会失效但是erase时候原结点被删除会造成迭代器失效。
4.总结
list模拟实现核心就是一个类迭代器的实现相比之前string、vectorlist迭代器更值得细细思考与总结。 list模拟实现还一个难点在于使用类模板应注意类模板问题。 EOF
