list的简单模拟实现

文章目录

目录

文章目录

前言

一、使用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()
{list<int> 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;
}

降序:
使用greater<int>进行排序。也可以直接使用匿名对象(lt1.sort(greater<int>());)

#include <iostream>
using namespace std;
#include <list>
int main()
{list<int> lt1 = { 9,8,4,2,1,3 };//lt1.sort(greater<int>());greater<int> gt;lt1.sort(gt);for (auto e : lt1){cout << e << ' ';}return 0;
}

list中的排序是归并排序。在使用如果使用list排序,它的效率较vector的排序效率较低。所以大量数据时不建议使用list 的排序

2.去重操作

操作中的去重是去掉重复的元素,但是前提是要进行排序

void test_list02()
{list<int> 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()
{list<int> 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的节点类template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T _val;};

再看整个list框架,迭代器刚开始看不懂,往下翻发现有个节点的指针:

link_type是什么?可以通过vs中ctrl+F功能进行查找,往上翻:

link_type实际上就是节点的指针

#pragma once
#include <iostream>
using namespace std;namespace mylist
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T val;};template<class T>class list{typedef ListNode<T> 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都应该指向自己:

	template<class T>class list{public:typedef ListNode<T> Node;public:void empty_init(){_head = new Node;_head->_next = _head;_head->_prev = _head;}list(){empty_init();}private:Node* _head;};

        写到这时我们实例化一个对象观察是否有错误

void test_mylist01()
{mylist::list<int> lt1;
}

结果:

        由于节点是一个自定义类型,new在对自定义类型开空间时,需要调用相应的默认构造函数.

而Node中没有构造函数,所以我们加上默认构造:

	template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _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::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);
}

        结果:

        已经插入了3个节点然后遍历节点?

遍历节点有很多种方式,最常用的是使用迭代器遍历。接下来我们进入重点。

5.迭代器*

        链表的迭代器实现与vector和string不同,考虑到没有operator[],并且不像vector那样空间连续,使用+=比较麻烦空间不连续。有没有更好的方法?

        迭代器模拟的是指针的行为。

        实际上链表要遍历很简单,因为链表中已经有后继节点和前驱节点了。

        这里不能像vector那样直接typedef一个指针成为迭代器。空间不连续。如何实现一个迭代器,可以实现++到下一个节点、--到前一个节点、解引用*访问节点?

typedef Node* iterator;无法满足我们的行为。

        我们一般会想到函数重载和重载运算符,那么如何将这些函数封装成一个迭代器?答案是--。而++和--等运算符对内置类型可以直接使用,但是对于自定义类型我们需要重载,而重载的条件之一就是必须有一个参数是自定义类型,所以迭代器用类封装再好不过了。

有了类就可以定义迭代器的行为。

template<class T>
class ListIterator
{typedef ListNode<T> Node;Node* _node;
};

由于迭代器实际上是对节点的指针进行操作,所以我们需要指针的成员变量:

迭代器用节点的指针构造。所以在迭代器中还需要构造函数:

	template<class T>class ListIterator{typedef ListNode<T> Node;typedef ListIterator<T> Self;//指向迭代器本身的类型重命名public:Node* _node;public:ListIterator(Node* node):_node(node){}};//用迭代器时,要获取指针:iterator(节点的指针);

       5.1 迭代器中的operator++和--

        由于++和--的返回值是迭代器,所以在迭代器中还需要一个指向自己的typedef。

		typedef ListNode<T> Node;typedef ListIterator<T> 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其他迭代器中的接口

        接下来我们先写出接口,然后进行分析;注意迭代器中构造函数和其他函数应该是公有的

template<class T>
class ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T> 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()(迭代器的实例化):

	template<class T>class list{public:typedef ListNode<T> Node;typedef ListIterator<T> iterator;public:iterator begin(){return iterator(_head->_next);//匿名对象}iterator end(){return iterator(_head);//末尾就是哨兵位}
//代码....

        使用迭代器遍历链表测试接口:

void test_mylist02()
{mylist::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);mylist::list<int>::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << ' ';++it;}
}

        代码结果:

测试前置后置++:

void test_mylist02()
{mylist::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);//测试前置++mylist::list<int>::iterator it1 = lt1.begin();cout << *(++it1) << endl;cout << *it1 << endl;cout << endl;//测试后置++mylist::list<int>::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::list<Pos> lt1;lt1.push_back(Pos(1, 2));lt1.push_back(Pos(3, 4));lt1.push_back(Pos(5, 6));//迭代器遍历数据mylist::list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){cout << *it << ' ';//这样是编译不过的++it;}
}

我们需要访问成员:

	//迭代器遍历数据mylist::list<Pos>::iterator it = lt1.begin();while (it != lt1.end()){cout << (*it)._row << ':' << (*it)._col << endl;++it;}

结果:

那有不有更便捷的方式?如果是Pos*的数据该怎么访问?

所以我们重载了operator->:

T* operator->()
{return &_node->val;
}//迭代器遍历数据mylist::list<Pos>::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 ListIterator<T> iterator;typedef ConstListIterator<T> const_iterator;

        定义新的const迭代器类模板:

	template<class T>class ConstListIterator{typedef ListNode<T> Node;typedef ConstListIterator<T> 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 ListNode<T> Node;
typedef ListIterator<T> iterator;
typedef ConstListIterator<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);//末尾就是哨兵位
}

const迭代器:

观察测试:

*it不能修改,it可以修改。


写到这里肯定会觉得写俩个类是不是很重复。能不能像下面这样:

这样是不行的,因为,迭代器中的所有T类型变为了const T类型,除了operator*和operator->符合我们的预期其他的函数,参数全部改变,那么const对象的迭代器不能匹配const迭代器中的其他函数,进而报错。

如list<int>时,const迭代器中的节点都是const int。

迭代器中:

链表中:

节点的类型都不匹配了。

        6.2更简洁的const 迭代器

        增加俩个模板参数,改变opeartor*和operator->:
同一个类模板给不同参数,就是不同类型:
        class Ref表示引用,Ptr表示指针。

template<class T,class Ref, class Ptr>
class ListIterator
{typedef ListNode<T> Node;typedef ListIterator<T,Ref,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中定义:

	template<class T>class list{public:typedef ListNode<T> Node;typedef ListIterator<T,T&,T*> iterator;//typedef ConstListIterator<T> const_iterator;typedef ListIterator<T,const T&, const T*> const_iterator;

        其实就是写了俩个类,交给编译器完成,让编译器打工。

俩种写法实际上没有区别,但是,减少了我们的代码量

测试:

void Func(const mylist::list<int>& lt)
{mylist::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}
}
void test_mylist04()
{mylist::list<int> 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::list<int> 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.h>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);}

由于delete释放了pos位置的节点,所以删除有迭代器失效。我们需要迭代器返回。

测试:

void test_mylist06()
{mylist::list<int> 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::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Func(lt1);mylist::list<int> lt2(lt1);lt1.push_back(5);Func(lt2);
}

俩个链表指向同一块空间。浅拷贝会有俩个问题
1.修改lt1,lt2也会跟着改变。

2.析构时会对同一块空间进行释放俩次。

        所以我们需要自己写一份深拷贝:

使用empty_init创建一个新的哨兵位,不指向旧空间。

//lt1(lt2)
list(const list<T>& lt)
{empty_init();for (const auto& e : lt){push_back(e);}
}

        测试代码:

void Func(const mylist::list<int>& lt)
{mylist::list<int>::const_iterator it = lt.begin();while (it != lt.end()){cout << *it << ' ';++it;}cout << endl;
}
void test_mylist08()
{mylist::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);lt1.push_back(4);Func(lt1);mylist::list<int> lt2(lt1);lt1.push_back(5);Func(lt1);Func(lt2);
}

        结果:

        12.operator=赋值操作

        赋值操作也需要深拷贝,有了拷贝构造,赋值操作就可以使用现代写法:

        函数的参数ltlt1一份拷贝,然后将拷贝的空间lt2进行交换,lt2指向的空间就是lt的空间,最后出函数作用域对lt空间进行释放。

	list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}

测试代码:

void test_mylist09()
{mylist::list<int> lt1;lt1.push_back(1);lt1.push_back(2);lt1.push_back(3);Func(lt1);mylist::list<int> lt2;lt2.push_back(1);lt2.push_back(2);Func(lt2);lt2 = lt1;Func(lt2);
}

测试结果:

13.initializer_list构造

        该构造就是支持{}括号构造:

list(initializer_list<T> il)
{empty_init();for (const auto& e : il){push_back(e);}
}

        测试代码:

void test_mylist10()
{mylist::list<int> lt1 = { 1,2,3,4,5 };Func(lt1);
}

14.反向迭代器

        反向迭代器我们需要学会复用iterator:

template <T>
class list
{
public://反向迭代器typedef Reverse_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_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());}};

        反向迭代器就是从后开始往前遍历,那么使用普通迭代器。从最后一个元素到哨兵位

	// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct 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::list<int>& lt)
{mylist::list<int>::const_reverse_iterator it = lt.rbegin();while (it != lt.rend()){cout << *it << ' ';++it;}cout << endl;
}
void test_mylist11()
{mylist::list<int> lt1 = { 1,2,3,4,5 };func(lt1);
}

结果:

三、所有代码:

#pragma once
#include <iostream>
using namespace std;
#include <list>
#include <algorithm>
#include <assert.h>
namespace mylist
{template<class T>struct ListNode{ListNode<T>* _prev;ListNode<T>* _next;T val;ListNode(const T& data = T()):_prev(nullptr), _next(nullptr), val(data) {}};template<class T,class Ref, class Ptr>struct ListIterator{typedef ListNode<T> Node;typedef ListIterator<T,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;//内置类型比较}};//template<class T>//class ConstListIterator//{//	typedef ListNode<T> Node;//	typedef ConstListIterator<T> 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;//	}//};// 适配器 -- 复用template<class Iterator, class Ref, class Ptr>struct 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反向迭代器实现template<class T>class list{public:typedef ListNode<T> Node;//普通迭代器typedef ListIterator<T,T&,T*> iterator;//typedef ConstListIterator<T> const_iterator;typedef ListIterator<T,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_iterator<iterator, T&, T*> reverse_iterator;typedef Reverse_iterator<const_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 list<T>& lt){empty_init();for (const auto& e : lt){push_back(e);}}list<T>& operator=(list<T> lt){std::swap(_head, lt._head);return *this;}list(initializer_list<T> 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;};
}

如果你有所收获,可以留下你的点赞和关注。谢谢你的观看!!!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/338683.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【TCP协议中104解析】wireshark抓取流量包工具,群殴协议解析基础

Tcp ,104 ,wireshark工具进行解析 IEC104 是用于监控和诊断工业控制网络的一种标准&#xff0c;而 Wireshark则是一款常用的网络协议分析工具&#xff0c;可以用干解析TEC104 报文。本文将介绍如何使用 Wireshark解析 IEC104报文&#xff0c;以及解析过 程中的注意事项。 一、安…

C语言-01_HelloWord

文章目录 1.C程序运行机制2.HelloWorld的剖析① main()② 函数体③ printf()④ 标准库、头文件 3.输出3.1 printf()标准格式3.2 占位符3.3 输出格式 1.C程序运行机制 过程1&#xff1a;编辑 编写C语言源程序代码&#xff0c;并已文件的形式存储到磁盘中。源程序文件以“.c”作…

dubbo复习:(19)dubbo 和spring整合(老古董)

一、服务端依赖 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org/POM…

【Linux】Linux工具——gcc/g++

1.使用vim更改信用名单——sudo 我们这里来补充sudo的相关知识——添加信任白名单用户 使用sudo就必须将使用sudo的那个账号添加到信用名单里&#xff0c;而且啊&#xff0c;只有超级管理员才可以添加 信用名单在/etc/sudoers里 我们发现它的权限只是可读啊&#xff0c;所以…

cocos入门5:编辑器界面介绍

Cocos Creator是一款功能强大的跨平台游戏开发工具&#xff0c;其编辑器界面设计直观易用&#xff0c;提供了从资源管理、场景编辑到脚本编写等一站式解决方案。下面是对Cocos Creator编辑器界面的详细介绍&#xff1a; 一、界面布局 Cocos Creator编辑器界面通常包含以下几个…

渲染100为什么是高性价比网渲平台?渲染100邀请码1a12

市面上主流的网渲平台有很多&#xff0c;如渲染100、瑞云、炫云、渲云等&#xff0c;这些平台各有特色和优势&#xff0c;也都声称自己性价比高&#xff0c;以渲染100为例&#xff0c;我们来介绍下它的优势有哪些。 1、渲染100对新用户很友好&#xff0c;注册填邀请码1a12有3…

IDeal下的SpringBoot项目部署

一、首先找到自己的sql文件&#xff0c;没有就从数据库挪进来 二、在Maven下打包一下&#xff08;点击package&#xff09;&#xff0c;看到BUILD SUCCESS就是打包好了 三、将上面两个文件分别挪到 linux 中对应的文件&#xff0c;没有就创建一个&#xff08;我的是spring_blog…

常见算法(基本查找、二分查找、分块查找冒泡、选择、插入、快速排序和递归算法)

一、常见算法-01-基本、二分、插值和斐波那契查找 1、基本查找/顺序查找 需求1&#xff1a;定义一个方法利用基本查找&#xff0c;查询某个元素是否存在 数据如下&#xff1a;{131&#xff0c;127&#xff0c;147&#xff0c;81&#xff0c;103&#xff0c;23&#xff0c;7&am…

WordPress子比主题美化-首页动态的图片展示

WordPress子比主题首页动态的图片展示 WordPress子比主题首页添加动态的图片展示&#xff0c;其他程序也可以用&#xff0c;复制代码到相应位置即可&#xff0c;也可作为指定分类&#xff0c;重点内容等&#xff0c;可以适合各个场景&#xff0c;需要的自取。 图片展示: 教程…

Spring源码之BeanDefinition的加载

Spring源码之BeanFactory和BeanDefinition BeanFactory和BeanDefinitionBeanFactoryBeanDefinition源码分析创建AnnotationConfigApplicationContext对象注册配置类refresh方法 BeanFactory和BeanDefinition BeanFactory BeanFactory是Spring提供给外部访问容器的根接口&…

MVC和MVVM

MVC Model层&#xff1a;用于处理应用程序数据逻辑的部分&#xff0c;通常负责在数据库中存取数据 View&#xff08;视图&#xff09;处理数据显示的部分。通常视图是依据模型数据创建的 Controller&#xff08;控制器&#xff09;是处理用户交互的部分。通常控制器负责从视…

Yolov10笔记

一、前言 清华大学团队设计的Yolov10. 在这项工作中&#xff0c;我们主要从后处理和模型结构两方面进一步优化YOLO系列模型的性能和延迟平衡。我们首先为YOLO引入了端到端训练的一致双重分配&#xff0c;这在大大降低推理延迟的情况下保证了性能。此外&#xff0c;我们针对YOLO…

养生与健康|一起跟随林曦老师养个元气满满

暄桐是一间传统美学教育教室&#xff0c;创办于2011年&#xff0c;林曦是创办人和授课老师&#xff0c;教授以书法为主的传统文化和技艺&#xff0c;皆在以书法为起点&#xff0c;亲近中国传统之美&#xff0c;以实践和所得&#xff0c;滋养当下生活。    在暄桐教室的六阶…

XCP协议系列介绍02-基于ASAP2 Tool-Set生成A2l介绍

本文框架 1. 前言2. ASAP2 Tool-Set系统介绍2.1 ASAP2 Creator介绍2.2 ASAP2 Updater介绍2.3 ASAP2 Merger介绍2.4 ASAP2 Comparer及Checker介绍2.5 ASAP2 Modifier介绍2.6 ASAP2 Studio介绍 3. 项目实操说明3.1 项目实操建议3.2 工具下载地址及使用 1. 前言 在XCP观测及标定整…

计算机网络期末复习(1)计算机网络在信息时代对的作用 计算机网络的定义和分类 三种交换方法

计算机网络在信息时代扮演着至关重要的角色&#xff0c;它极大地改变了我们生活、工作和学习的方式。 计算机网络在信息时代的作用 信息共享与传播&#xff1a;计算机网络使全球范围内的信息快速共享成为可能&#xff0c;无论是新闻、学术研究还是娱乐内容&#xff0c;都可以…

【C++】类和对象——构造和析构函数

目录 前言类的六个默认构造函数构造函数1.构造函数的概念2.构造函数的特性 初始化列表1.构造函数整体赋值2.初始化列表 析构函数1.析构函数的概念2.析构函数的特性 前言 类和对象相关博客&#xff1a;【C】类和对象   我们前面一个内容已经讲了关于类好对象的初步的一些知识&…

【MyBatis】零基础从入门到进阶(源码级深入详解)

1 MyBatis概述 1.1 框架 ● 在⽂献中看到的framework被翻译为框架 ● Java常⽤框架&#xff1a; ○ SSM三⼤框架&#xff1a;Spring SpringMVC MyBatis ○ SpringBoot ○ SpringCloud ○ 等。。 ● 框架其实就是对通用代码的封装&#xff0c;提前写好了⼀堆通用…

数据库系统概论(个人笔记)(第三部分)

数据库系统概论&#xff08;个人笔记&#xff09; 文章目录 数据库系统概论&#xff08;个人笔记&#xff09;3、SQL介绍3.1 SQL查询语言概述3.2 SQL数据定义3.3 SQL查询的基本查询结构3.4 其他基本操作3.5 设置操作3.6 空值3.7 聚合函数3.8 嵌套子查询3.9 数据库的修改 3、SQL…

看车牌识别API如何应用到实际

车牌识别技术作为一种先进的识别系统&#xff0c;在现代城市的交通管理和安全领域扮演着日益重要的角色。本文将深入探讨车牌识别API 接口在智能停车、安全监控以及数据分析等方面的具体应用。通过详细研究这些应用场景&#xff0c;我们可以更好地理解这项技术如何提升交通流畅…

Laravel和ThinkPHP框架比较

一、开发体验与易用性比较 1. 代码可读性&#xff1a; - Laravel以其优雅的语法和良好的代码结构著称&#xff0c;使得代码更加易读易懂。 - 相比之下&#xff0c;ThinkPHP的代码可读性较为一般&#xff0c;在一些复杂业务场景下&#xff0c;可能会稍显混乱。 让您能够一站式…