list模拟实现


铁汁们，今天给大家分享一篇list模拟实现+反向迭代器，来吧，开造⛳️

list定义

💡 list< typename> name ;

  • list底层是带头双向循环链表结构，且该容器可以前后双向迭代。

  • 双向链表中每个元素存储互不相关的独立节点，在结点中通过指针访问其前一个元素和后一个元素。

  • list允许在任意位置进行插入和删除操作，时间复杂度为O(1)，时间效率高。

  • list不支持任意位置的随即访问，若想要访问某个位置，必须从已知的位置（头部或者尾部）迭代到该位置，时间开销为O(n)。

  • list需要额外的空间开销，用来保存每个节点的相关联信息。

  • typename为任意类型，例如：int、char、double、string、vector。
    在这里插入图片描述

list用法

list iterator的使用

begin() + end()

💡iterator begin( )、const_iterator begin( )const ；

  • 功能：返回第一个元素的位置(迭代器）。

Tips：const_iterator表示对迭代器进行解引用后的值(*it)不能被修改,而迭代器本身(it)可以被修改。const修饰this指针，表示在该成员函数中成员变量不允许被修改，此处const的用法只能用于类中的成员函数。

💡iterator end( )、const_iterator end( )const ；

  • 功能：返回最后一个元素的下一个位置(迭代器）。

rbegin()+rend()

💡iterator begin( )、const_iterator rbegin( )const ；

  • 功能：返回第一个元素的前一个位置(迭代器）。

💡iterator rend( )、const_iterator rend( )const ；

  • 功能：返回第一个元素的位置(迭代器）。
    在这里插入图片描述

reverse()

💡 void reverse( ) ;

  • 功能 : 逆置，将list中元素的顺序进行颠倒 。

sort()

💡 void sort( ) ;

  • 功能：排序，默认为升序。模板参数中的默认仿函数为less。

Tips：list中的sort为归并排序，算法库中的sort为快排。

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(4);
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(2);

    lt1.sort();

    for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
    
    return 0;
}

在这里插入图片描述

merge()

💡void merge(list& lt) ;

  • 功能：将两个已经有序的链表进行合并，默认为升序 。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(4);
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(2);

	list<int> lt2;
	lt2.push_back(9);
	lt2.push_back(7);
	lt2.push_back(10);
	lt2.push_back(8);

	lt1.sort();
	lt2.sort();

	lt1.merge(lt2);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;

	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;
    
	return 0;
}

在这里插入图片描述

unique()

💡 void unique( ) ;

  • 功能：去重，将链表中连续相等的元素组中删除除第一个元素外的所有元素。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(4);
	lt1.push_back(4);
	lt1.push_back(4);
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(3);
	lt1.push_back(2);
	lt1.push_back(4);
	lt1.push_back(4);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	
	lt1.unique();

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

remove()

💡 void remove(const T& val) ;

  • 功能：去除，将链表中值为val的元素删除。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(4);
	lt1.push_back(1);
	lt1.push_back(3);
	lt1.push_back(2);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	
	lt1.remove(4);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

splice()

💡 void splice(iterator position , list& lt) ;

  • 功能 ：将容器lt中所有的元素转移到容器中指定位置（迭代器）的前面，容器lt的大小为0。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);

	list<int> lt2(3, 2);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	lt1.splice(lt1.begin(), lt2);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

💡 void splice(iterator position , list& lt , iterator i ) ;

  • 功能：将容器lt中迭代器i指向的节点转移到容器中指定位置（迭代器）的前面，容器lt的大小减一。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);

	list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(11);
	lt2.push_back(12);

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	lt1.splice(lt1.begin(), lt2, ++lt2.begin());

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

💡 void splice(iterator position , list& lt , iterator first , iterator last ) ；

  • 功能：将容器lt中[first, last)范围中的元素转移到容器中指定位置（迭代器）的前面。
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<list>

using namespace std;

int main()
{
	list<int> lt1;
	lt1.push_back(1);
	lt1.push_back(2);
	lt1.push_back(3);

	list<int> lt2;
	lt2.push_back(10);
	lt2.push_back(11);
	lt2.push_back(12);
	lt2.push_back(13);


	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	lt1.splice(lt1.begin(), lt2, ++lt2.begin(),--lt2.end());

	for (auto& e : lt1)
	{
		cout << e << ' ';
	}
	cout << endl;
	for (auto& e : lt2)
	{
		cout << e << ' ';
	}
	cout << endl;

	return 0;
}

在这里插入图片描述

list模拟实现

struct和class的区别

  • 在c++中，struct和class都可以定义类，但两者默认的访问权限(即在变量或函数定义处不写访问限定符)不同，struct默认访问权限为public(为了兼容c)，class默认访问权限为private。
  • 访问限定符有三种，分别为public、private、protect。public修饰的变量或函数在类外可以通过类名+域作用限定符或者 类对象 + . 进行访问，protect、private修饰的变量或函数在类外不可以进行访问。

list三个类模板

  • Tips : list本质为带头双向循环链表，模拟实现list，要实现以下三个类：模拟实现节点的类、模拟实现带头双向循环链表结构的类、模拟实现迭代器的类。
template<class T>  //节点 
struct ListNode {  //struct类未用访问限定符修饰的变量为public,在类外指定类域就可以直接进行访问
	ListNode* _prev;  //带头双向循环链表
	ListNode* _next;
	T _data;
}


template<class T> //链表-带头双向循环链表，存储的元素为节点
class list {   //class类未用访问限定符修饰的变量为private,在类外不可以访问
public:
	typedef ListNode<T> Node; 

		//为了符合规范，需要将迭代器的类型typedef为iterator
	typedef list_iterator<T, T&, T*> iterator;   //非const
	typedef list_iterator<T, const T&, const T*> const_iterator;  //const

	Node* _head; //头指针，该指针指向的节点为头节点，不存储任何有效数据
	//头节点中的_data不能存储后面节点的总个数，原因:若T为char型，数据个数过大，会数据溢出
}


template<class T, class Ref, class Ptr>  //迭代器  Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定
struct list_iterator { 
	typedef ListNode<T> Node;  //节点
	typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型

	Node* _node; //节点指针
}

在这里插入图片描述

list<int> lt1(2, 10);
lt1.push_back(3);
lt1.push_back(2);
lt1.push_back(1);

zzx::list<int>::iterator it1 = lt1.begin();
while (it1 != lt1.end())
{
	cout << *it1 << ' ';
	it1++;
}
cout << endl;

const list<int> lt2(lt1.begin(), --lt1.end());

zzx::list<int>::const_iterator it2 = lt2.begin();
while (it2 != lt2.end())
{
	cout << *it2 << ' ';
	it2++;
}
cout << endl;

在这里插入图片描述

默认成员函数

构造函数

void CreatHead() //创造带头双向循环链表结构
{
	_head = new Node;
	_head->_prev = _head;
	_head->_next = _head;
}
  • 构造函数有很多种，但都需要先创造出带头双向循环链表结构，会造成代码冗余，增加了代码量和复杂性，为了解决这个问题，就将此板块的代码实现定义在CreatHead()函数体内。

💡list( ) { } ;

  • 功能：构造无参的对象。
list() //无参构造
{
	CreatHead();
}

💡list(size_t n, const T& val = T( ) ) ；

  • 功能：构造含n个val值的对象。
list(size_t n, const T& val) //用n个val值构造
{
	CreatHead();

	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

list(int n, const T& val)  //为了防止出现“非法间接寻址”错误
{
	CreatHead();

	for (int i = 0; i < n; i++)
	{
		push_back(val);
	}
}

Tips: 因为模板参数的匹配原则，会出现防止“非法间接寻址”错误。

💡list( InputIterator first, InputIterator last ) ；

  • 功能：构造与[first, last)范围一样多元素的对象。
template<class InputIterator>  //  注意：模板内可以在嵌套模板
list(InputIterator first, InputIterator last)  //用迭代区间进行构造
{
	CreatHead();

	while (first != last)
	{
		push_back(*first);
    	++first;
	}
}

拷贝构造函数

💡list(const list& v) ；

  • 功能：用一个已经存在的对象创建新的对象，两对象中的值相同。
list(const list& lt) //拷贝构造函数，深拷贝-》浅拷贝，指向同一块空间，析构两次
{
	CreatHead();

	for (auto& e : lt)
	{
		push_back(e);
	}
}

Tips : 深拷贝，否则会造成指向同一块空间，被析构两次。

list<int> lt1(5, 2); // 先构造的对象后析构	
list<int> lt2 = lt1; //编译器会优化，构造 + 拷贝 - 》构造，默认拷贝构造为值拷贝
lt1.push_back(1);

for (auto& e : lt1)
{
	cout << e << ' ';
}
cout << endl;

for (auto& e : lt2)
{
		cout << e << ' ';
}
cout << endl;

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

赋值运算符重载

💡list& operator=(list v) ；

  • 功能：赋值，两对象已经存在。
list<T>& operator=(list lt)  //赋值运算符
{
	swap(lt);
	return *this;
}

Tips : 深拷贝，否则会造成指向同一块空间，被析构两次。

析构函数

💡~vector( ) { } ；

  • 功能：将列表中的元素全部删除(销毁)，并链表结构也被销毁。
~list() //析构函数
{
	clear();

	delete _head;  //
	_head = nullptr;
}

数据修改操作

push_back()

💡void push_back(const T& val) ;

  • 功能：尾插。
void push_back(const T& val) //尾插
{
	/*传统写法
	Node* newnode = new Node(val);

	Node* tail = _head->_prev;
	tail->_next = newnode;
	newnode->_prev = tail;
	newnode->_next = _head;
	_head->_prev = newnode;
	*/

	insert(end(), val);
}

push_front()

💡void push_front(const T& val) ;

  • 功能：头插。
void push_front(const T& val) //头插
{
	insert(begin(), val);
}

pop_back()

💡void pop_back( ) ；

  • 功能：尾删。
void pop_back()  //尾删
{
	erase(--end());
}

pop_front()

💡void pop_front( ) ;

  • 功能：头删。
void pop_front()  //头删
{
	erase(begin());
}

swap()

💡void swap(list& lt) ;

  • 功能：交换。
void swap(list<T>& lt) //交换
{
	std::swap(_head, lt._head);
}

clear()

💡void clear( ) ；

  • 功能：从列表容器中删除所有元素（已销毁），并使容器的大小为0，但带头双向链表结构仍在。
void clear()  //清空链表中的节点，哨兵位头节点除外，带头双向循环链表结构未被破坏
{
	iterator it = begin();
	while (it != end())
	{
		it = erase(it);
	}
}

insert()

💡void insert(iterator position , const T& val) ；

  • 功能：在指定的位置(迭代器）前插入元素x。
/*insert中迭代器不会失效
		原因:未扩容未引起底层空间发生变化，position迭代器未发生变化，仍指向了正确的位置，即使在使用此迭代器仍可以完成insert*/
iterator insert(iterator position, const T& val)
{
	Node* newnode = new Node(val);
	Node* cur = position._node;  //struct中public变量访问可以 对象.变量名
	Node* prev = cur->_prev;

	prev->_next = newnode;
	newnode->_prev = prev;
	newnode->_next = cur;
	cur->_prev = newnode;

	return newnode;  //有返回值，与erase匹配

}
  • nsert为了与erase匹配，有返回值 ，返回一个指向 新插入 的元素节点的迭代器。
  • Tips : insert中迭代器不会失效 。原因 : 未扩容未引起底层空间发生变化，position迭代器未发生变化，仍指向了正确的位置，即使在使用此迭代器仍可以完成insert。

在这里插入图片描述

erase()

💡iterator erase(iterator pos) ;

  • 功能: 删除指定位置(迭代器)处的值。
//erase中迭代器会失效,原因:position迭代器被delete了，此迭代器不能在被使用了
iterator erase(iterator position)
{
	assert(position != end());  //断言，防止删除哨兵位头节点
    
	Node* cur = position._node;
	Node* prev = cur->_prev;
	Node* next = cur->_next;

	prev->_next = next;
	next->_prev = prev;

	delete cur;  //
	cur = nullptr;

	return next;  //返回删除节点的下一个节点
}
  • Tips : erase中迭代器会失效 ,原因 :position迭代器被delete了，此迭代器不能在被使用了，但其他迭代器不受影响，仍然可以正常被使用。
  • erase为了防止迭代器失效，有返回值 ，返回一个指向要删除节点的下一个节点的迭代器。
  • delete cur ：delete->析构+free , 因为对象里面(节点)进行了资源申请，要调用析构函数，进行资源销毁，在调用free将对象(指针)的空间进行销毁。
    在这里插入图片描述

容量操作

size

💡size_t size( )const ;

  • 功能：计算元素的总个数。
size_t size()const
{
	size_t count = 0;
	for (auto const& e : *this)
	{
		count++;
	}

	return count;
}
  • const对象以及非const对象均可以调用const成员函数，原因：权限不能放大(const对象不能调用非const成员函数）。const对象->权限平移，非const对象->权限缩小。

empty

💡bool empty( )const ;

  • 功能：判断list中是否存在元素，为空，则返回true,不为空，则返回false。
bool empty()const
{
	return size() == 0;
}

数据访问操作

front()

💡T& front( ) ;

  • 功能：返回第一个节点中的元素。
T& front()
{
	return _head->_next->_data;
}

const T& front()const
{
	return _head->_next->_data;
}

back()

💡T& back( ) ;

  • 功能：返回最后一个节点中的元素。
T& back()
{
	return _head->_prev->_data;
}

const T& back()const
{
    return _head->_prev->_data;
}

迭代器

正向迭代器

template<class T, class Ref, class Ptr>  //迭代器  Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定
struct list_iterator { 
	typedef ListNode<T> Node;  //节点
	typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型

	Node* _node; //节点指针
}

list<int> lt1;
lt1.push_back(1);
lt1.push_back(2);
lt1.push_back(3);

//it1: 内置类型
ListNode<int>* it1 = lt1._head->_next;  
//it2：自定义类型
list<int>::iterator it2 = lt1.begin();
		
/*尽管it1和it2的值是相同的，但进行++操作时，
编译器将it1当作内置类型(由语言标准指定的)进行处理,*表示取其指向空间中的值，++表示向后走sizeof(类型)的步长
it2为自定义类型，去调用operator*()、operator++()运算符*/
*it1;
++it1;

*it2;
++it2;
cout << sizeof(it1) << endl;
cout << sizeof(it2) << endl;

在这里插入图片描述
在这里插入图片描述

  • 提供统一的方式进行访问和修改，摒弃了底层的细节，使容器进行访问和修改更加容易。
  • 底层为原生指针 ,因为list底层结构为链表，物理空间是不连续的，需要运算符重载，而重载运算符需要是自定义类型，指针为内置类型，所以对指针进行了封装list_iterator。
  • 为了符合规范，需要typedef将迭代器类型命名为iterator。

Tips ：将模拟实现迭代器的类定义为struct类，且指针_node默认访问权限为public, 原因:list类中的insert、erase，position类型为迭代器，为了类型要匹配(node*),则在类外用迭代器._node进行访问，否则在类外就访问不到_node。

💡不用显示写析构函数，原因:若显示写了，则表示是把该指针指向的节点一并删除，此处并不希望删除链表中的节点，默认生成的析构函数对内置类型不做处理。
未进行资源申请。

💡不用显示写拷贝构造函数，默认生成的拷贝构造函数进行值拷贝，尽管两个指针指向同一块空间，一个指针被销毁，会去调用析构函数，因未显示写析构函数，析构函数对内置类型不做处理,指针变量会被销毁，系统将其回收了，但该指针变量指向的节点还在;

构造函数

💡list_iterator(Node* node = nullptr) ；

list_iterator(Node* node = nullptr) //单参数构造函数支持隐式类型转换 Node*->iterator
	:_node(node)
{ }

Tips : 单参数构造函数支持隐式类型转换 Node*->iterator 。

begin() + end()

💡iterator begin( ) ；

  • 功能：返回第一个元素的位置(迭代器）。

Tips：list对象为非const对象，就调用begin()、end()，list为const对象，就调用const_iterator begin()const、const_iterator end()const。

iterator begin()   //list对象为非const对象
{
	return _head->_next;  //单参数构造函数支持隐式类型转换
}

💡iterator end( ) ；

  • 功能：返回最后一个元素的下一个位置(迭代器）。
iterator end()
{
	return _head;
}
const_iterator begin()/end()const

💡const_iterator begin( )const ;

Tips : const_iterator表示对迭代器解引用(*)的值不可以被修改，而迭代器本身可以被修改，const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改。

/*const_iterator表示* 迭代器的值不可以被修改，而迭代器本身可以被修改，
		const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改 */
const_iterator begin()const   //list对象为const对象， const对象才能调用const成员函数
{
	return _head->_next;  //单参数构造函数支持隐式类型转换
}

💡const_iterator end( )const ;

const_iterator end()const
{
	return _head;
}
operator*()

💡Ref operator*( ) ；

/*oprator*()不用const，原因:iterator普通迭代器调用普通成员函数，const_iterator中迭代器为非const对象，指向的内容可以被修改
		*/
Ref operator*() //只有返回值类型不一致-》模板参数
{
	return _node->_data;
}
  • const_iterator、iterator区别就在与，const_iterator返回值只可读不可以修改(constT&)，iterator返回值既可读又可以修改(T&)，两者只是返回值类型不同，可以将其定义为模板参数，因为模板参数修饰的是类型。
operator->()

💡Ptr operator->( ) ；

Ptr operator->() //结构体指针，_data为结构体，*it只能取到结构体(自定义类型），若需要cout<<*it，则需要重载<<
{//特殊处理，为了可读性，省略了一个 ->
	return &_node->_data; //it->_a1 -》 it.operator->()->_a1
}

struct AA{  
	int _a1;
	int _a2;

	AA(int a1 = 1, int a2 = 2)
		:_a1(a1)
    	,_a2(a2)
	{ }
};

list<AA> lt4; 
lt4.push_back(AA()); //AA()为匿名对象
lt4.push_back(AA(10, 20));
zzx::list<AA>::iterator it2 = lt4.begin();
while (it2 != lt4.end())
{
	cout << it2->_a1 << ":" << it2->_a2 << endl;
	++it2;
}
cout << endl;

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述

operator!=()

💡bool operator!=(const Self& tmp) ;

bool operator!=(const Self& tmp)
{
	return _node != tmp._node;  //指针为内置类型，可以直接进行比较
}
operator==()

💡bool operator==(const Self& tmp) ;

bool operator==(const Self& tmp)
{
	return _node == tmp._node;
}
前置++和后置++

💡Self& operator++( ) ；

Self& operator++() //前置++
{
	_node = _node->_next;
	return *this;  //引用返回，出了作用域,*this还在，提高返回效率
}

💡Self operator++(int) ；

Self operator++(int)  //后置++
{
	Self tmp(*this);
	_node = _node->_next;
	return tmp;  //传值返回，出了作用域,tmp就被销毁
}
  • 前置++的效率高于后置++，因为前置的++没有生成额外的对象，意味着不需要过多的内存，也就是不需要在栈上开辟额外的空间。而后置的++需要在栈上额外创建对象，占用栈空间，返回后就要调用析构函数。
  • 为了与前置++区分，C++规定：后置++重载时多增加一个int类型的参数，但调用函数时该参数不用传递，由编译器自动传递。
前置–和后置–

💡Self& operator–( ) ；

Self& operator--() //前置--
{
	_node = _node->_prev;
	return *this;  //引用返回，出了作用域,*this还在，提高返回效率
}

💡Self operator–(int) ；

Self operator--(int)  //后置--
{
	Self tmp(*this);
	_node = _node->_prev;
	return tmp;  //传值返回，出了作用域,tmp就被销毁
}

反向迭代器

定义
  • 正向迭代器为begin()、end()，反向迭代器为rbegin()、rend()。
  • 反向迭代器的++就是正向迭代器的–，反向迭代器的–就是正向迭代器的++，所以反向迭代器的实现可以借助于正向迭代器来实现，将正向迭代器转换为反向迭代器，即：迭代器适配器。
  • 迭代器适配器：给了我任何容器的正向迭代器，就可以适配出该容器的反向迭代器。将正向迭代器的类型定义为类模板，在反向迭代器中根据类模板参数定义正向迭代器对象，反向迭代器各接口的实现均通过调用正向迭代器的接口来实现。
    在这里插入图片描述
构造函数

💡list_reverse_iterator(iterator cur) ；

//正向迭代器封装了Node*指针，其构造函数参数为Node*,反向迭代器封装了iterator,其构造函数参数为iterator
list_reverse_iterator(iterator cur) //构造函数
	:_cur(cur)  //单参数构造函数支持隐式类型转换 iterator-》reverse_iterator
{ }
  • 单参数构造函数支持隐式类型转换 iterator-》reverse_iterator。
  • 正向迭代器封装了Node指针，其构造函数参数为Node,反向迭代器封装了iterator,其构造函数参数为iterator。
rbegin() + rend()

💡reverse_iterator rbegin( ) ；

  • 功能：返回第一个元素的前一个位置(迭代器）。
reverse_iterator rbegin() //非const对象
{
	return end();
}

💡reverse_iterator rend( ) ；

  • 功能：返回第一个元素的位置(迭代器）。
reverse_iterator rend()
{
	return begin();
}
const_reverse_iterator rbegin()/rend()const

💡const_reverse_iterator rbegin( )const ;

const_reverse_iterator rbegin()const //const对象
{
	return end();
}

💡const_reverse_iterator rend( )const ;

const_reverse_iterator rend()const
{
	return begin();
}
operator*()

💡Ref operator*( ) ；

Ref operator*() //只是取其所指向的节点中的值，指针的值并未发生变化
{  //rbegin()=end()、rend()=begin()
	iterator tmp = _cur; 
	--tmp;    
	return *tmp;
}

在这里插入图片描述

operator->()

💡Ptr operator->( ) ；

//正向迭代器operator->()是返回结构体的地址(结构体指针)
Ptr operator->()  //结构体指针
{
	return &(operator*());
}
  • 与正向迭代器的实现相同，正向迭代器operator->()是返回节点值(结构体)的地址(结构体指针)，反向迭代器的operator*()返回的是节点的值。
operator!=()

💡bool operator!=(const Self& s) ;

bool operator!=(const Self& s) 
{
	return _cur != s._cur;
}
operator==()

💡bool operator==(const Self& s) ;

bool operator==(const Self& s)
{
	return _cur == s._cur;
}
前置++和后置++

在这里插入图片描述

💡Self& operator++( ) ；

Self& operator++() //前置++
{ 
	--_cur;  //正向迭代器往前走
	return *this;
}

💡Self operator++(int) ；

Self operator++(int) //后置++
{
	Self tmp = *this;
	--_cur;

	return tmp;
}
前置–和后置–

💡Self& operator–( ) ；

Self& operator--()  //前置--
{
	++_cur;  //正向迭代器往后走
	return *this;
}

💡Self operator–(int) ；

Self operator--(int) //后置--
{
	Self tmp = *this;
	++_cur;
    
	return tmp;
}

list模拟实现总代码

#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<assert.h>
#include<list>

#include"Reserve_Iterator.h"

using namespace std;

namespace zzx {
	struct AA{  
		int _a1;
		int _a2;

		AA(int a1 = 1, int a2 = 2)
			:_a1(a1)
			,_a2(a2)
		{ }
	};

	template<class T>  //节点 
	struct ListNode {  //struct类未用访问限定符修饰的变量为public,在类外指定类域就可以直接进行访问
		ListNode* _prev;  //带头双向循环链表
		ListNode* _next;
		T _data;

		ListNode(const T& val = T()) //缺省值-》防止无参调用，因无默认构造函数，又显示写了构造函数，编译器会报错
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{ }
	};

	/*迭代器:1.提供统一的方式进行访问和修改，摒弃了底层的细节，使容器进行访问和修改更加容易;
	*        2.底层为原生指针,因为list底层结构为链表，物理空间是不连续的，需要运算符重载，而重载运算符需要是自定义类型，指针为内置类型，
	*        所以对指针进行了封装list_iterator；
	*        3.为了符合规范，需要typedef将迭代器类型命名为iterator
	*/
	template<class T, class Ref, class Ptr>  //迭代器  Ref(T、const T)、Ptr(T*、const T*):*、->的返回值是否被修改，根据实际清况而定
	struct list_iterator { 
		typedef ListNode<T> Node;  //节点
		typedef list_iterator<T, Ref, Ptr> Self; //迭代器类型

		Node* _node; //节点指针

		/*不用显示写析构函数，原因:若显示写了，则表示是把该指针指向的节点一并删除，此处并不希望删除链表中的节点，
		默认生成的析构函数对内置类型不做处理。 未进行资源申请;
		不用显示写拷贝构造函数，默认生成的拷贝构造函数进行值拷贝，尽管两个指针指向同一块空间，一个指针被销毁，
		会去调用析构函数，因未显示写析构函数，析构函数对内置类型不做处理,指针变量会被销毁，系统将其回收了，但该指针变量指向的节点还在;
		*/

		list_iterator(Node* node = nullptr) //单参数构造函数支持隐式类型转换 Node*->iterator
			:_node(node)
		{ }

		Ptr operator->() //结构体指针，_data为结构体，*it只能取到结构体(自定义类型），若需要cout<<*it，则需要重载<<
		{//特殊处理，为了可读性，省略了一个 ->
			return &_node->_data; //it->_a1 -》 it.operator->()->_a1
		}

		/*oprator*()不用const，原因:iterator普通迭代器调用普通成员函数，const_iterator中迭代器为非const对象，指向的内容可以被修改
		*/
		Ref operator*() //只有返回值类型不一致-》模板参数
		{
			return _node->_data;
		}

		Self& operator++() //前置++
		{
			_node = _node->_next;
			return *this;  //引用返回，出了作用域,*this还在，提高返回效率
		}

		Self operator++(int)  //后置++
		{
			Self tmp(*this);
			_node = _node->_next;
			return tmp;  //传值返回，出了作用域,tmp就被销毁
		}

		Self& operator--() //前置--
		{
			_node = _node->_prev;
			return *this;  //引用返回，出了作用域,*this还在，提高返回效率
		}

		Self operator--(int)  //后置--
		{
			Self tmp(*this);
			_node = _node->_prev;
			return tmp;  //传值返回，出了作用域,tmp就被销毁
		}

		bool operator!=(const Self& tmp)
		{
			return _node != tmp._node;  //指针为内置类型，可以直接进行比较
		}

		bool operator==(const Self& tmp)
		{
			return _node == tmp._node;
		}
	};

    template<class iterator, class Ref, class Ptr>  //反向迭代器:通过正向迭代器转换而来(迭代器适配器)
    struct list_reverse_iterator {

    	iterator _cur;  //迭代器适配器

    	typedef list_reverse_iterator<iterator, Ref, Ptr> Self;

	//正向迭代器封装了Node*指针，其构造函数参数为Node*,反向迭代器封装了iterator,其构造函数参数为iterator
    	list_reverse_iterator(iterator cur) //构造函数
    		:_cur(cur)  //单参数构造函数支持隐式类型转换 iterator-》reverse_iterator
    	{ }

    	Ref operator*() //只是取其所指向的节点中的值，指针的值并未发生变化
    	{  //rbegin()=end()、rend()=begin()
    		iterator tmp = _cur;
    		--tmp;
    		return *tmp;
    	}

    	Self& operator++() //前置++
    	{
    		--_cur;  //正向迭代器往前走
    		return *this;
    	}

    	Self operator++(int) //后置++
    	{
    		Self tmp = *this;
    		--_cur;

    		return tmp;
    	}

    	Self& operator--()  //前置--
    	{
    		++_cur;  //正向迭代器往后走
    		return *this;
    	}	

    	Self operator--(int) //后置--
        {
    		Self tmp = *this;
    		++_cur;

    		return tmp;
    	}
    	//正向迭代器operator->()是返回结构体的地址(结构体指针)
    	Ptr operator->()  //结构体指针
    	{
    		return &(operator*());
    	}

    	bool operator!=(const Self& s)
    	{
    		return _cur != s._cur;
    	}

    	bool operator==(const Self& s)
    	{
    		return _cur == s._cur;
        }
   };

	template<class T> //链表-带头双向循环链表，存储的元素为节点
	class list {   //class类未用访问限定符修饰的变量为private,在类外不可以访问
	public:
		typedef ListNode<T> Node; 

		//为了符合规范，需要将迭代器的类型typedef为iterator
		typedef list_iterator<T, T&, T*> iterator;   // 正向迭代器 、非const
		typedef list_iterator<T, const T&, const T*> const_iterator;  //const

		typedef list_reverse_iterator<iterator, T&, T*> reverse_iterator;  // 反向迭代器 、非const
		typedef list_reverse_iterator<const_iterator, const T&, const T*> const_reverse_iterator; //const

		//正向迭代器
		iterator begin()   //list对象为非const对象
		{
			return _head->_next;  //单参数构造函数支持隐式类型转换
		}

		iterator end()
		{
			return _head;
		}

		/*const_iterator表示* 迭代器的值不可以被修改，而迭代器本身可以被修改，
		const修饰类成员函数，实际修饰该成员函数隐含的this指针，表明在该成员函数中不能对类的任何成员进行修改 */
		const_iterator begin()const   //list对象为const对象， const对象才能调用const成员函数
		{
			return _head->_next;  //单参数构造函数支持隐式类型转换
		}

		const_iterator end()const
		{
			return _head;
		}

		//反向迭代器
		reverse_iterator rbegin()
		{
			return end();
		}

		reverse_iterator rend()
		{
			return begin();
		}

		const_reverse_iterator rbegin()const
		{
			return end();
		}

		const_reverse_iterator rend()const
		{
			return begin();
		}

		void CreatHead() //创造带头双向循环链表结构
		{
			_head = new Node;
			_head->_prev = _head;
			_head->_next = _head;
		}

		//构造函数
		list() //无参构造
		{
			CreatHead();
		}

		list(size_t n, const T& val) //用n个val值构造
		{
			CreatHead();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		list(int n, const T& val)  //为了防止出现“非法间接寻址”错误
		{
			CreatHead();

			for (int i = 0; i < n; i++)
			{
				push_back(val);
			}
		}

		template<class InputIterator>  //  注意： 模板内可以在嵌套模板
		list(InputIterator first, InputIterator last)  //用迭代区间进行构造
		{
			CreatHead();

			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}

		list(const list& lt) //拷贝构造函数，深拷贝-》浅拷贝，指向同一块空间，析构两次
		{
			CreatHead();

			for (auto& e : lt)
			{
				push_back(e);
			}
		}

		list<T>& operator=(list lt)  //赋值运算符
		{
			swap(lt);
			return *this;
		}

		~list()  //析构函数
		{
			clear();

			delete _head;  //
			_head = nullptr;
		}

		//修改
		void swap(list<T>& lt) //交换
		{
			std::swap(_head, lt._head);
		}

		void clear()  //清空链表中的节点，哨兵位头节点除外，带头双向循环链表结构未被破坏
		{
			iterator it = begin();
			while (it != end())
			{
				it = erase(it);
			}
		}

		void push_back(const T& val) //尾插
		{
			/*传统写法
			Node* newnode = new Node(val);

			Node* tail = _head->_prev;
			tail->_next = newnode;
			newnode->_prev = tail;
			newnode->_next = _head;
			_head->_prev = newnode;
			*/

			insert(end(), val);
		}

		void push_front(const T& val) //头插
		{
			insert(begin(), val);
		}

		void pop_back()  //尾删
		{
			erase(--end());
		}
		
		void pop_front()  //头删
		{
			erase(begin());
		}

		/*insert中迭代器不会失效
		原因:未扩容未引起底层空间发生变化，position迭代器未发生变化，仍指向了正确的位置，即使在使用此迭代器仍可以完成insert*/
		iterator insert(iterator position, const T& val)
		{
			Node* newnode = new Node(val);
			Node* cur = position._node;  //struct中public变量访问可以 对象.变量名
			Node* prev = cur->_prev;

			prev->_next = newnode;
			newnode->_prev = prev;
			newnode->_next = cur;
			cur->_prev = newnode;

			return newnode;  //有返回值，与erase匹配

		}

		//erase中迭代器会失效,原因:position迭代器被delete了，此迭代器不能在被使用了
		iterator erase(iterator position)
		{
			assert(position != end());  //断言，防止删除哨兵位头节点

			Node* cur = position._node;
			Node* prev = cur->_prev;
			Node* next = cur->_next;

			prev->_next = next;
			next->_prev = prev;

			delete cur;  //
			cur = nullptr;

			return next;  //返回删除节点的下一个节点
		}

		//Access
		T& front()
		{
			return _head->_next->_data;
		}

		const T& front()const
		{
			return _head->_next->_data;
		}
		
		T& back()
		{
			return _head->_prev->_data;
		}

		const T& back()const
		{
			return _head->_prev->_data;
		}

		//Capacity
		size_t size()const
		{
			size_t count = 0;
			for (auto const& e : *this)
			{
				count++;
			}

			return count;
		}

		bool empty()const
		{
			return size() == 0;
		}

		Node* _head; //头指针，该指针指向的节点为头节点，不存储任何有效数据
		//头节点中的_data不能存储后面节点的总个数，原因:若T为char型，数据个数过大，会数据溢出
	};
}

铁铁们，list模拟实现+反向迭代器就到此结束啦，若博主有不好的地方，请指正，欢迎铁铁们留言，请动动你们的手给作者点个👍鼓励吧，你们的鼓励就是我的动力✨

# c++ # list # 开发语言 # c语言 # 数据结构 # 迭代加深
Logo
西安城市开发者社区

欢迎加入西安开发者社区！我们致力于为西安地区的开发者提供学习、合作和成长的机会。参与我们的活动，与专家分享最新技术趋势，解决挑战，探索创新。加入我们，共同打造技术社区！

更多推荐

cover

华为Mate70系列彻底火了！—预约人数突破200万，未来市场可期！

avatar 西安城市开发者社区
cover

我的创作3+1周年纪念日：猫头虎的四年创作之旅

avatar 西安城市开发者社区
cover

超哥赠书第三期：引领未来科技浪潮：揭秘《人形机器人》的革新技术

avatar 西安城市开发者社区