做影视网站需要的软件,南通制作公司网站,襄阳网站建设八零后,京津冀协同发展现状文章目录 目录 文章目录 前言 一、使用list时的注意事项 1.list不支持std库中的sort排序 2.去重操作 3.splice拼接 二、list的接口实现 1.源码中的节点 2.源码中的构造函数 3.哨兵位头节点 4.尾插和头插 5.迭代器* 5.1 迭代器中的operator和-- 5.2其他迭代器中的接口 5.3迭代器… 文章目录 目录 文章目录 前言 一、使用list时的注意事项 1.list不支持std库中的sort排序 2.去重操作 3.splice拼接 二、list的接口实现 1.源码中的节点 2.源码中的构造函数 3.哨兵位头节点 4.尾插和头插 5.迭代器* 5.1 迭代器中的operator和-- 5.2其他迭代器中的接口 5.3迭代器类的使用 5.4 前置后置-- 5.5 list不支持重载和- 5.6 operator- 6.const迭代器 6.1写俩个类实现const迭代器 6.2更简洁的const 迭代器 7.insert插入 8.erase删除节点 9.insert和erase的复用 9.1尾插 9.2尾删 9.3头插 9.4头删 10.析构函数 11.拷贝构造 12.operator赋值操作 13.initializer_list构造 14.反向迭代器 前言 list是带头双向循环链表。是序列容器允许在序列中的任何位置进行常数时间的插入和删除操作并且可以在两个方向上进行迭代。list被实现为双向链表双向链表可以将其包含的每个元素存储在不同且不相关的存储位置中。通过将每个元素与其前面的元素和后面的元素的链接关联起来可以在内部保持排序。 一、使用list时的注意事项 1.list不支持std库中的sort排序 由于std库中sort内部是快排操作涉及三数取中操作需要迭代器可以相减。而由于list不支持迭代器相减操作 所以不能使用std库中的sort排序。因为效率和空间问题链表的空间不是连续的实现迭代器相减操作非常影响效率。 list想要进行排序就要使用它专门提供的操作 默认升序 #include iostream
using namespace std;
#include list
int main()
{listint lt1 { 9,8,4,2,1,3 };for (auto e : lt1){cout e ;}cout endl;lt1.sort();for (auto e : lt1){cout e ;}return 0;
} 降序 使用greaterint进行排序。也可以直接使用匿名对象lt1.sort(greaterint());。 #include iostream
using namespace std;
#include list
int main()
{listint lt1 { 9,8,4,2,1,3 };//lt1.sort(greaterint());greaterint gt;lt1.sort(gt);for (auto e : lt1){cout e ;}return 0;
} list中的排序是归并排序。在使用如果使用list排序它的效率较vector的排序效率较低。所以大量数据时不建议使用list 的排序。
2.去重操作
操作中的去重是去掉重复的元素但是前提是要进行排序 void test_list02()
{listint lt1 { 9,8,4,2,1,3 ,2,1,3};for (auto e : lt1){cout e ;}cout endl;//直接调用去重lt1.unique();for (auto e : lt1){cout e ;}
}没有进行去重操作无法使得相同元素在一起。调用排序sort
3.splice拼接 实际上就是转移另一个链表中的元素到目标链表的某个位置之前可以转移一个或者整个链表。
注意是将另一个链表中的节点直接拿过来所以另一个链表中的元素在转移之后要去掉。
也可以将自己的元素转移到自己的某个位置 。 void test_list01()
{listint mylist1;for (int i 1; i 4; i){mylist1.push_back(i); // 1 2 3 4}for (auto e : mylist1)cout e ;cout endl;auto it std::find(mylist1.begin(), mylist1.end(), 3);//将3转移到头mylist1.splice(mylist1.begin(), mylist1, it);for (auto e : mylist1)cout e ;
} 二、list的接口实现 1.源码中的节点 list一般是带头双向循环链表所以节点的结构是俩个指针
源码中用void*指针在后面使用时都要进行强转成节点类型的指针。 我们在实现过程中不必这样直接使用模板定下指针的类型 // List的节点类templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T _val;}; 再看整个list框架迭代器刚开始看不懂往下翻发现有个节点的指针
link_type是什么可以通过vs中ctrlF功能进行查找往上翻 link_type实际上就是节点的指针。 #pragma once
#include iostream
using namespace std;namespace mylist
{templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T val;};templateclass Tclass list{typedef ListNodeT Node;private:Node* _head;};
} 为什么节点不使用class原因是因为节点的成员变量和成员函数需要频繁访问使用public和友元也可以但是这样实际上和struct一样并且使用public和友元实际上破坏了封装。 2.源码中的构造函数 empty_initialize()从字面意思上理解就是空节点初始化。
观察 这个函数就是给出哨兵位。 get_node()函数就是获取节点观察 C获取节点时都是从内存池上获取的内存池就是我们使用空间配置中自己管理的空间。
使用内存池的好处就是可以更灵活的利用空间使得代码空间获取效率提高。由于我们初步接触list所以我们使用new开辟的就好。 由于内存池的空间是我们自己管理所以对于自定义类型不能自动的调用构造函数所以在源码中还有一个creat_node()函数 consruct函数调用的是构造函数。对开辟好的内存池进行初始化也就是定位new的功能。
这里不是本章重点仅仅了解一下。 代码实现很简单 void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();} 3.哨兵位头节点 创建节点时哨兵为的prev和next都应该指向自己 templateclass Tclass list{public:typedef ListNodeT Node;public:void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){empty_init();}private:Node* _head;}; 写到这时我们实例化一个对象观察是否有错误 void test_mylist01()
{mylist::listint lt1;
} 结果 由于节点是一个自定义类型new在对自定义类型开空间时需要调用相应的默认构造函数.
而Node中没有构造函数所以我们加上默认构造 templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T val;ListNode(const T data T()):_prev(nullptr), _next(nullptr), val(data) {}}; 4.尾插和头插 尾插和头插操作源码中调用的是insert() 观察insert 在迭代器position位置插入x。 先写一个简单的尾插
找尾
修改指向 代码 void push_back(const T x)
{//创建新节点然后初始化Node* newnode new Node(x);//找尾Node* ptail head-prev;//改变新节点指向newnode-_next head;newnode-_prev ptail;//改变head和ptail指向ptail-_next newnode;head-prev newnode;
} 测试代码 void test_mylist01()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);
} 结果 已经插入了3个节点然后遍历节点
遍历节点有很多种方式最常用的是使用迭代器遍历。接下来我们进入重点。
5.迭代器* 链表的迭代器实现与vector和string不同考虑到没有operator[]并且不像vector那样空间连续使用比较麻烦空间不连续。有没有更好的方法 迭代器模拟的是指针的行为。 实际上链表要遍历很简单因为链表中已经有后继节点和前驱节点了。 这里不能像vector那样直接typedef一个指针成为迭代器。空间不连续。如何实现一个迭代器可以实现到下一个节点、--到前一个节点、解引用*访问节点 typedef Node* iterator无法满足我们的行为。 我们一般会想到函数重载和重载运算符那么如何将这些函数封装成一个迭代器答案是--类。而和--等运算符对内置类型可以直接使用但是对于自定义类型我们需要重载而重载的条件之一就是必须有一个参数是自定义类型所以迭代器用类封装再好不过了。
有了类就可以定义迭代器的行为。 templateclass T
class ListIterator
{typedef ListNodeT Node;Node* _node;
}; 由于迭代器实际上是对节点的指针进行操作所以我们需要指针的成员变量 迭代器用节点的指针构造。所以在迭代器中还需要构造函数 templateclass Tclass ListIterator{typedef ListNodeT Node;typedef ListIteratorT Self;//指向迭代器本身的类型重命名public:Node* _node;public:ListIterator(Node* node):_node(node){}};//用迭代器时要获取指针iterator(节点的指针); 5.1 迭代器中的operator和-- 由于和--的返回值是迭代器所以在迭代器中还需要一个指向自己的typedef。 typedef ListNodeT Node;typedef ListIteratorT Self;public:Node* _node;public:ListIterator(Node* node):_node(node){}Self operator(){_node _node-_next;return *this;}Self operator(int){Self tmp(*this);_node _node-_next;return tmp;} 5.2其他迭代器中的接口 接下来我们先写出接口然后进行分析注意迭代器中构造函数和其他函数应该是公有的。 templateclass T
class ListIterator
{typedef ListNodeT Node;typedef ListIteratorT Self;
public:Node* _node;
public:ListIterator(Node* node):_node(node){}Self operator()//前置{_node _node-_next;return *this;}Self operator(int)//后置{Self tmp(*this);_node _node-_next;return tmp;}T operator*()//访问数据{return _node-val;}bool operator!(const Self it)//比较节点地址{return _node ! it._node;}
}; 5.3迭代器类的使用 我们可以通过迭代器进行修改数据(operator*),也可以进行比较。 实现迭代器begin()和end()迭代器的实例化 templateclass Tclass list{public:typedef ListNodeT Node;typedef ListIteratorT iterator;public:iterator begin(){return iterator(_head-_next);//匿名对象}iterator end(){return iterator(_head);//末尾就是哨兵位}
//代码.... 使用迭代器遍历链表测试接口 void test_mylist02()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);mylist::listint::iterator it lt1.begin();while (it ! lt1.end()){cout *it ;it;}
} 代码结果
测试前置后置 void test_mylist02()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);//测试前置mylist::listint::iterator it1 lt1.begin();cout *(it1) endl;cout *it1 endl;cout endl;//测试后置mylist::listint::iterator it2 lt1.begin();cout *(it2) endl;cout *it2 endl;
}结果 5.4 前置后置-- 和类似找到前一个节点 Self operator--()
{_node _node-_prev;return *this;
}
Self operator--(int)
{Self tmp(*this);_node _node-_prev;return tmp;
} 5.5 list不支持重载和- 由于链表的空间地址不连续重载和-就需要遍历到n次节点所以效率不高标准库中未支持、-。 迭代器不需要写析构函数不需要对节点进行释放。节点的释放应该由list来做。 5.6 operator- 标准库中的list不仅仅重载了operator*并且重载了operator- 图中operator*的返回值是引用(被typedef了),而operator-的返回值是T*的指针即数据的指针。 T operator*()
{return _node-val;
}
T* operator-()
{return _node-val;
} 为什么要重载-?观察下面代码 假设我们需要存储坐标 void test_mylist03()
{struct Pos{int _row;int _col;Pos(int row 0, int col 0)//需要默认构造节点需要对象的默认构造:_row(row),_col(col){}};mylist::listPos lt1;lt1.push_back(Pos(1, 2));lt1.push_back(Pos(3, 4));lt1.push_back(Pos(5, 6));//迭代器遍历数据mylist::listPos::iterator it lt1.begin();while (it ! lt1.end()){cout *it ;//这样是编译不过的it;}
} 我们需要访问成员 //迭代器遍历数据mylist::listPos::iterator it lt1.begin();while (it ! lt1.end()){cout (*it)._row : (*it)._col endl;it;} 结果
那有不有更便捷的方式如果是Pos*的数据该怎么访问
所以我们重载了operator- T* operator-()
{return _node-val;
}//迭代器遍历数据mylist::listPos::iterator it lt1.begin();while (it ! lt1.end()){//cout (*it)._row : (*it)._col endl;cout it-_row : it-_col endl;it;} 结果 这里就会有疑惑这个-为什么可以调用成功在平常使用时不应该需要一个结构体指针才用到 -吗
实际上这就是一个结构体指针调用由于重载的特性使用-会直接执行迭代器中我们所写的重载函数operator-().
在代码中调用了operator-函数实际上是俩个对头为了可读性将第二个-省略了 6.const迭代器 6.1写俩个类实现const迭代器 在访问const链表的时需要const迭代器如果使用非const迭代器则会报错 const迭代器的作用时可以访问不可修改。
不能在我们实现的迭代器前加const修饰 所以我们需要自己写一个const迭代器类如何做到可以遍历但是不能修改
只需要将访问的函数和可以修改的值的函数用const修饰将迭代器指向的内容修饰即可。
即将operator*和operator-进行修饰 list类中 typedef ListIteratorT iterator;typedef ConstListIteratorT const_iterator; 定义新的const迭代器类模板 templateclass Tclass ConstListIterator{typedef ListNodeT Node;typedef ConstListIteratorT Self;public:Node* _node;ConstListIterator(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;}const T operator*(){return _node-val;}const T* operator-(){return _node-val;}bool operator!(const Self it){return _node ! it._node;}}; list类模板中定义新的迭代器 typedef ListNodeT Node;
typedef ListIteratorT iterator;
typedef ConstListIteratorT const_iterator;
iterator begin()
{return iterator(_head-_next);//匿名对象
}
const_iterator begin()const
{return const_iterator(_head-_next);//匿名对象
}
iterator end()
{return iterator(_head);//末尾就是哨兵位
}
const_iterator end() const
{return const_iterator(_head);//末尾就是哨兵位
} const迭代器 观察测试
*it不能修改it可以修改。 写到这里肯定会觉得写俩个类是不是很重复。能不能像下面这样 这样是不行的因为迭代器中的所有T类型变为了const T类型除了operator*和operator-符合我们的预期其他的函数参数全部改变那么const对象的迭代器就不能匹配上const迭代器中的其他函数进而报错。
如listint时const迭代器中的节点都是const int。
迭代器中
链表中
节点的类型都不匹配了。 6.2更简洁的const 迭代器 增加俩个模板参数改变opeartor*和operator- 同一个类模板给不同参数就是不同类型 class Ref表示引用Ptr表示指针。 templateclass T,class Ref, class Ptr
class ListIterator
{typedef ListNodeT Node;typedef ListIteratorTRef,Ptr Self;
public:Node* _node;ListIterator(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;}Ref operator*(){return _node-val;}Ptr operator-(){return _node-val;}bool operator!(const Self it){return _node ! it._node;}
}; list中定义 templateclass Tclass list{public:typedef ListNodeT Node;typedef ListIteratorT,T,T* iterator;//typedef ConstListIteratorT const_iterator;typedef ListIteratorT,const T, const T* const_iterator; 其实就是写了俩个类交给编译器完成让编译器打工。
俩种写法实际上没有区别但是减少了我们的代码量。
测试 void Func(const mylist::listint lt)
{mylist::listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}
}
void test_mylist04()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Func(lt1);
} 结果 也可以传递俩个模板参数 7.insert插入 源码插入 我们实现一个简单的插入 void insert(iterator pos, const T x){//创建新的节点Node* newnode new Node(x);//新节点Node* cur pos._node; //pos节点Node* prev cur-_prev;//前驱节点newnode-_next cur;newnode-_prev cur-_prev;//改变前驱节点的指向//prev newnode curprev-_next newnode;cur-_prev newnode;} 思考list中的迭代器有无迭代器失效 链表中的迭代器不会失效因为它的空间不连续。没有扩容这一说法。但是为了和库保持一致我们和vector一样给insert一个返回值 iterator insert(iterator pos, const T x){//代码....return iterator(newnode);} 测试代码 void test_mylist05()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);for (auto e : lt1){cout e ;}lt1.insert(lt1.begin(), 5);lt1.insert(lt1.end(),6);cout endl;for (auto e : lt1){cout e ;}
} 结果
8.erase删除节点 改变前继节点和后继节点的指向。 #include assert.hiterator erase(iterator pos){//不能删除哨兵位assert( pos ! end());Node* cur pos._node;Node* prev cur-_prev;Node* next cur-_next;//prev cur nextprev-_next next;next-_prev prev;delete cur;//删除后迭代器失效因为pos指向的节点已经被释放//需要返回值来获取下一个节点的元素。return iterator(next);} 由于delete释放了pos位置的节点所以删除有迭代器失效。我们需要迭代器返回。
测试 void test_mylist06()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);for (auto e : lt1){cout e ;}lt1.erase(lt1.begin());cout endl;for (auto e : lt1){cout e ;}
} 结果 9.insert和erase的复用 9.1尾插 void push_back(const T x){创建新节点然后初始化//Node* newnode new Node(x);找尾//Node* ptail _head-_prev;改变新节点指向//newnode-_next _head;//newnode-_prev ptail;改变head和ptail指向//ptail-_next newnode;//_head-_prev newnode;insert(end(), x);} 9.2尾删 void pop_back()
{insert(--end());
} 9.3头插 void push_front(const T x){insert(begin(), x);} 9.4头删 void pop_front(){erase(begin());} 测试 实际上迭代器我们经常要访问它的成员变量和成员函数所以迭代器也可以写出strcut 的类。
虽然它公有但是我们接触的是list而不是迭代器的类模板。 10.析构函数 链表的析构需要一个一个节点释放在观察list等容器的代码会发现一般的容器都会有一个clear的函数。 clear函数专门用于清除有效数据的空间而不清理哨兵位。
void clear()
{auto it begin();while (it ! end()){it erase(it);}
} 析构函数在这个函数基础上进行空间释放
~list()
{clear();delete _head;_head nullptr;
} 11.拷贝构造 不写拷贝构造编译器会生成一个该默认生成的拷贝构造是值拷贝即浅拷贝。使用浅拷贝构造的链表和原链表指向的是一块空间。
void test_mylist08()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Func(lt1);mylist::listint lt2(lt1);lt1.push_back(5);Func(lt2);
} 俩个链表指向同一块空间。浅拷贝会有俩个问题 1.修改lt1lt2也会跟着改变。 2.析构时会对同一块空间进行释放俩次。 所以我们需要自己写一份深拷贝
使用empty_init创建一个新的哨兵位不指向旧空间。
//lt1(lt2)
list(const listT lt)
{empty_init();for (const auto e : lt){push_back(e);}
} 测试代码
void Func(const mylist::listint lt)
{mylist::listint::const_iterator it lt.begin();while (it ! lt.end()){cout *it ;it;}cout endl;
}
void test_mylist08()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Func(lt1);mylist::listint lt2(lt1);lt1.push_back(5);Func(lt1);Func(lt2);
} 结果 12.operator赋值操作 赋值操作也需要深拷贝有了拷贝构造赋值操作就可以使用现代写法 函数的参数lt是lt1的一份拷贝然后将拷贝的空间和lt2进行交换lt2指向的空间就是lt的空间最后出函数作用域对lt空间进行释放。 listT operator(listT lt){std::swap(_head, lt._head);return *this;}
测试代码
void test_mylist09()
{mylist::listint lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);Func(lt1);mylist::listint lt2;lt2.push_back(1);lt2.push_back(2);Func(lt2);lt2 lt1;Func(lt2);
}
测试结果
13.initializer_list构造 该构造就是支持{}括号构造
list(initializer_listT il)
{empty_init();for (const auto e : il){push_back(e);}
} 测试代码
void test_mylist10()
{mylist::listint lt1 { 1,2,3,4,5 };Func(lt1);
}
14.反向迭代器 反向迭代器我们需要学会复用iterator
template T
class list
{
public://反向迭代器typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}}; 反向迭代器就是从后开始往前遍历那么使用普通迭代器。从最后一个元素到哨兵位。 // 适配器 -- 复用templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{typedef Reverse_iterator Iterator, Ref, Ptr Self;Iterator _it;Reverse_iterator(const Iterator it):_it(it){}//Self operator(){--_it;return *this;}Self operator(int){Self tmp(*this);_it--;return tmp;}Self operator--(){_it;return *this;}Self operator--(int){Self tmp(*this);_it;return tmp;}Ref operator*(){Iterator tmp(_it);//反向迭代器的rbegin()是正向迭代器end()的--//有效元素//反向迭代器的rend()是正向迭代器begin()的--;//表示哨兵位位置return *(--tmp);}Ptr operator-(){return (operator*());//是访问的地址}bool operator!(const Self it){return _it ! it._it;//自定义类型比较所以参数需要成员函数}};
测试代码
void func(const mylist::listint lt)
{mylist::listint::const_reverse_iterator it lt.rbegin();while (it ! lt.rend()){cout *it ;it;}cout endl;
}
void test_mylist11()
{mylist::listint lt1 { 1,2,3,4,5 };func(lt1);
}
结果 三、所有代码
#pragma once
#include iostream
using namespace std;
#include list
#include algorithm
#include assert.h
namespace mylist
{templateclass Tstruct ListNode{ListNodeT* _prev;ListNodeT* _next;T val;ListNode(const T data T()):_prev(nullptr), _next(nullptr), val(data) {}};templateclass T,class Ref, class Ptrstruct ListIterator{typedef ListNodeT Node;typedef ListIteratorT,Ref,Ptr Self;Node* _node;ListIterator(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;}Ref operator*(){return _node-val;}Ptr operator-(){return _node-val;}bool operator!(const Self it){return _node ! it._node;//内置类型比较}};//templateclass T//class ConstListIterator//{// typedef ListNodeT Node;// typedef ConstListIteratorT Self;// Node* _node;//public:// ConstListIterator(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;// }// const T operator*()// {// return _node-val;// }// const T* operator-()// {// return _node-val;// }// bool operator!(const Self it)// {// return _node ! it._node;// }//};// 适配器 -- 复用templateclass Iterator, class Ref, class Ptrstruct Reverse_iterator{typedef Reverse_iterator Iterator, Ref, Ptr Self;Iterator _it;Reverse_iterator(const Iterator it):_it(it){}//Self operator(){--_it;return *this;}Self operator(int){Self tmp(*this);_it--;return tmp;}Self operator--(){_it;return *this;}Self operator--(int){Self tmp(*this);_it;return tmp;}Ref operator*(){Iterator tmp(_it);//反向迭代器的rbegin()是正向迭代器end()的--//有效元素//反向迭代器的rend()是正向迭代器begin()的--;//表示哨兵位位置return *(--tmp);}Ptr operator-(){return (operator*());//是访问的地址}bool operator!(const Self it){return _it ! it._it;//自定义类型比较所以参数需要成员函数}};// vector和list反向迭代器实现templateclass Tclass list{public:typedef ListNodeT Node;//普通迭代器typedef ListIteratorT,T,T* iterator;//typedef ConstListIteratorT const_iterator;typedef ListIteratorT,const T, const T* const_iterator;iterator begin(){return iterator(_head-_next);//匿名对象}const_iterator begin()const{return const_iterator(_head-_next);//匿名对象}iterator end(){return iterator(_head);//末尾就是哨兵位}const_iterator end() const{return const_iterator(_head);//末尾就是哨兵位}//反向迭代器typedef Reverse_iteratoriterator, T, T* reverse_iterator;typedef Reverse_iteratorconst_iterator, const T, const T* const_reverse_iterator;reverse_iterator rbegin(){return reverse_iterator(end());}const_reverse_iterator rbegin() const{return const_reverse_iterator(end());}reverse_iterator rend(){return reverse_iterator(begin());}const_reverse_iterator rend() const{return const_reverse_iterator(begin());}public:void empty_init(){_head new Node;_head-_next _head;_head-_prev _head;}list(){ empty_init();}list(const listT lt){empty_init();for (const auto e : lt){push_back(e);}}listT operator(listT lt){std::swap(_head, lt._head);return *this;}list(initializer_listT il){empty_init();for (const auto e : il){push_back(e);}}~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* ptail _head-_prev;改变新节点指向//newnode-_next _head;//newnode-_prev ptail;改变head和ptail指向//ptail-_next newnode;//_head-_prev newnode;insert(end(), x);}void pop_back(){insert(--end());}void push_front(const T x){insert(begin(), x);}void pop_front(){erase(begin());}iterator insert(iterator pos, const T x){//创建新的节点Node* newnode new Node(x);Node* cur pos._node;Node* prev cur-_prev;newnode-_next cur;newnode-_prev cur-_prev;//改变前驱节点的指向//prev newnode curprev-_next newnode;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 cur nextprev-_next next;next-_prev prev;delete cur;//删除后迭代器失效因为pos指向的节点已经被释放//需要返回值来获取下一个节点的元素。return iterator(next);}private:Node* _head;};
} 如果你有所收获可以留下你的点赞和关注。谢谢你的观看
