首页 > 电脑常识 > 区块链

C++ STL-List源码分析

admin 区块链 2021-04-26 16:00:33 c++   STL   数据结构   链表  
后台-系统设置-扩展变量-手机广告位-内容正文底部

文章目录:

  • STL-List-源码
  • 1. 对私有成员的数据类型进行声明
  • 2. 初始化,写入构造函数,申请一个头节点,
  • 3.尾插
  • 4. 构造迭代器
  • 5. 插入一个节点到_P位置
  • 6. 判空
  • 7. 取链表的第一个节点
  • 8. 取链表的尾节点(需- -)
  • 9. 三种构造函数
  • 10. 删除节点
  • 11. 最终刨析代码


STL-List-源码

List源码可查看—>[List源码]

1. 对私有成员的数据类型进行声明

源码中私有成员如下:

在这里插入图片描述

刨析后如下:

#include<iostream>
using namespace std;

namespace code
{
	template <class _Ty>
	class list
	{
	public:
		//类型的萃取
		typedef size_t size_type;//大小的类型
		typedef _Ty    value_type;//值类型
		typedef _Ty*   pointer_type;//指针类型
		typedef _Ty&   reference_type;//引用类型
		typedef const _Ty* const_pointer_type;//常指针类型
		typedef const _Ty& const_reference_type;//常引用类型
	public:
		struct _Node;
		typedef struct _Node* _Nodeptr;
	private:
		_Nodeptr _Head;
		size_type _Size;
	};
}

void main()
{
	code::list<int>mylist;
}

2. 初始化,写入构造函数,申请一个头节点,

相关源码如下:
在这里插入图片描述


在这里插入图片描述


在这里插入图片描述


刨析如下:

#include<iostream>
using namespace std;

namespace code
{
	template <class _Ty>
	class list
	{
	public:
		//类型的萃取
		typedef size_t size_type;//大小的类型
		typedef _Ty    value_type;//值类型
		typedef _Ty*   pointer_type;//指针类型
		typedef _Ty&   reference_type;//引用类型
		typedef const _Ty* const_pointer_type;//常指针类型
		typedef const _Ty& const_reference_type;//常引用类型
	public:
		struct _Node;
		typedef struct _Node* _Nodeptr;
		struct _Node
		{
			_Nodeptr _Next;
			_Nodeptr _Prev;
			_Ty    _value;
		};

		struct _Acc
		{
			typedef struct _Node* & _Nodepref;
			typedef _Ty&     _Vref;
			static _Nodepref _Next(_Nodeptr _P)
			{
				return (_P->_Next);
			}
			static _Nodepref _Prev(_Nodeptr _P)
			{
				return (_P->_Prev);
			}
			static _Vref _Value(_Nodeptr _P)
			{
				return (_P->_Value);
			}
		};

	//刨析写法一:

	//public:
	//	explicit list() :_Head(nullptr), _Size(0)
	//	{
	//		_Head = new _Node;
	//		_Head->_Next = _Head;
	//		_Head->_Prev = _Head;
	//	}

	//刨析写法二
	
	//public:
	//	explicit list() :_Head(_Buynode()), _Size(0)
	//	{}
	//protected:
	//	_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
	//	{
	//		_Nodeptr _S = new _Node;
	         //申请完节点可以直接连接它的前驱和后继
	//		_S->_Next = _Narg != 0 ? _Narg : _S;
	//		_S->_Prev = _Parg != 0 ? _Parg : _S;

	//		return _S;
	//	}

		//源码写法,封装性更好,不会让成员暴露
		public:
			explicit list() :_Head(_Buynode()), _Size(0)
			{}
		protected:
			_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
			{
				_Nodeptr _S = new _Node;
				_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
				_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;

				return _S;
			}


	private:
		_Nodeptr _Head;
		size_type _Size;
	};
}

void main()
{
	code::list<int>mylist;
}

如上三种写法的效果是一样的,但源码的写法不会将成员暴露出来,相对更好

测试效果如下:
在这里插入图片描述

3.尾插

相关源码如下:
在这里插入图片描述
刨析后数据结构写法如下:

	    public:
			void push_back(const _Ty& _X)
			{
				_Nodeptr _S = new _Node;
				_S->_Value = _X;
				_S->_Prev = _Head->_Prev;
				_S->_Next = _Head;
				_Head->_Prev = _S;
				_S->_Prev->_Next = _S;
				++_Size;
			}

优化后如下:

			//尾插
	    public:
			void push_back(const _Ty& _X)
			{
				_Nodeptr _S = _Buynode(_Head, _Acc::_Prev(_Head));
				_Acc::_Value(_S) = _X;
				_Acc::_Next(_Acc::_Prev(_S)) = _S;
				_Acc::_Prev(_Acc::_Next(_S)) = _S;
				++_Size;
			}

4. 构造迭代器

给一个私有成员变量_Ptr(一个指针),写出迭代器的默认构造函数

	public:
		//构造一个迭代器
		class iterator
		{
		public:
			iterator()
			{}
			iterator(_Nodeptr _P) :_Ptr(_P)
			{}
		private:
			_Nodeptr _Ptr;
		};

写一个begin()构造器,返回第一个真实节点;一个end()构造器,返回头节点

	public:
		//begin()迭代器 返回第一个真实节点
		iterator begin()
		{
			return iterator(_Acc::_Next(_Head));
		}
		//end()迭代器 返回头节点
		iterator end()
		{
			return iterator(_Head);
		}

重载++,–,*,!=,==

源码如下:
在这里插入图片描述

刨析后写法如下:

	public:
		//构造一个迭代器
		class iterator
		{
		public:
			iterator()
			{}
			iterator(_Nodeptr _P) :_Ptr(_P)
			{}
		public:
			//不等号重载
			bool operator!=(const iterator& _it)
			{
				return _Ptr != _it._Ptr;
			}
			//等号重载
			bool operator==(const iterator& _it)
			{
				return _Ptr == _it._Ptr;
			}
			//*的重载
			_Ty& operator*()
			{
				return _Acc::_Value(_Ptr);
			}
			//前置++的重载
			iterator& operator++()
			{
				_Ptr = _Acc::_Next(_Ptr);
				return *this;
			}
			//后置++的重载
			iterator operator++(int)
			{
				iterator tem(_Ptr);
				++*this;
				return tem;
			}
			//前置--的重载
			iterator& operator--()
			{
				_Ptr = _Acc::_Prev(_Ptr);
				return *this;
			}
			//后置--的重载
			iterator operator--(int)
			{
				iterator tmp(_Ptr);
				--*this;
				return tmp;
			}
		private:
			_Nodeptr _Ptr;
		};

打印测试:

void main()
{
	code::list<int>mylist;
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);

	code::list<int>::iterator it = mylist.begin();
	while (it != mylist.end())
	{
		cout << *it << "->";
		++it;
	}
	cout << "end" << endl;
}

测试效果如下:
在这里插入图片描述

5. 插入一个节点到_P位置

写入一个插入函数insert
源码如下:

在这里插入图片描述

刨析后代码如下:

	//数据结构写法

		//public:
		//	//指定一个位置进行插入
		//	iterator insert(iterator _P, const _Ty& _X = _Ty())
		//	{
		//		_Nodeptr _S = new _Node;
		//		_Acc::_Value(_S) = _X;
		//		
		//		_Nodeptr _N = _P._Mynode();
		//		_S->_Next = _N;
		//		_S->_Prev = _N->_Prev;
		//		_S->_Prev->_Next = _S;
		//		_S->_Next->_Prev = _S;
		//		++_Size;
		//		return iterator(_S);
		//	}

		public:
			iterator insert(iterator _P, const _Ty& _X = _Ty())
			{
				//_S指向_P位置
				_Nodeptr _S = _P._Mynode();
				//新节点连向它的后继和前驱,_P连接新节点
				_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
				//_S指向新节点
				_S = _Acc::_Prev(_S);
				//_S的前驱的后继指向_S
				_Acc::_Next(_Acc::_Prev(_S)) = _S;
				_Acc::_Value(_S) = _X;
				++_Size;
				return (iterator(_S));
			}

此时头插尾插可以优化为:

		//尾插
		void push_back(const _Ty& _X)
		{
			insert(end(), _X);
		}
		//头插
		void push_front(const _Ty& _X)
		{
			insert(begin(), _X);
		}

6. 判空

返回_Size的大小判断是否为0

在这里插入图片描述

7. 取链表的第一个节点

此处有两个方法一个针对普通对象,一个针对常对象

在这里插入图片描述

8. 取链表的尾节点(需- -)

end()取的是最后一个节点的下一个位置(_Head)

在这里插入图片描述

9. 三种构造函数

(1)默认构造函数(2)初始化为n个x(3)初始化一个区间

源码如下:
在这里插入图片描述

刨析如下:

        //默认构造函数
	    explicit list():_Head(_Buynode()),_Size(0)
		{}
		//初始化为n个x
		list(size_type _N, const _Ty& _V = _Ty())
			:_Head(_Buynode()), _Size(0)
		{
			insert(begin(), _N, _V);
		}
		//初始化一个区间
		list(const _Ty *_F, const _Ty *_L)
			:_Head(_Buynode()), _Size(0)
		{
			insert(begin(), _F, _L);
		}

10. 删除节点

		//删除节点
			iterator erase(iterator _P)
			{
				_Nodeptr _S = (_P++)._Mynode();
				_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
				_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
				_Deletenode(_S);
				--_Size;
				return (_P);
			}
			//删除一个区间
			iterator erase(iterator _F, iterator _L)
		    {
			    while (_F != _L)
			   	erase(_F++);
			    return (_F); 
		    }
		    //清除函数
		    void clear()
		    {
		    	erase(begin(), end());
		    }
			protected:
			void _Deletenode(_Nodeptr _S)
			{
				delete _S;
			}

11. 最终刨析代码

#include<iostream>
using namespace std;

namespace code
{
	template <class _Ty>
	class list
	{
	public:
		//类型的萃取
		typedef size_t size_type;//大小的类型
		typedef _Ty    value_type;//值类型
		typedef _Ty*   pointer_type;//指针类型
		typedef _Ty&   reference_type;//引用类型
		typedef const _Ty* const_pointer_type;//常指针类型
		typedef const _Ty& const_reference_type;//常引用类型
	public:
		struct _Node;
		typedef struct _Node* _Nodeptr;
		struct _Node
		{
			_Nodeptr _Next;
			_Nodeptr _Prev;
			_Ty    _Value;
		};

		struct _Acc
		{
			typedef struct _Node* & _Nodepref;
			typedef _Ty&     _Vref;
			static _Nodepref _Next(_Nodeptr _P)
			{
				return (_P->_Next);
			}
			static _Nodepref _Prev(_Nodeptr _P)
			{
				return (_P->_Prev);
			}
			static _Vref _Value(_Nodeptr _P)
			{
				return (_P->_Value);
			}
		};
	public:
		//构造一个迭代器
		class iterator
		{
		public:
			iterator()
			{}
			iterator(_Nodeptr _P) :_Ptr(_P)
			{}
		public:
			//不等号重载
			bool operator!=(const iterator& _it)
			{
				return _Ptr != _it._Ptr;
			}
			//等号重载
			bool operator==(const iterator& _it)
			{
				return _Ptr == _it._Ptr;
			}
			//*的重载
			_Ty& operator*()
			{
				return _Acc::_Value(_Ptr);
			}
			//前置++的重载
			iterator& operator++()
			{
				_Ptr = _Acc::_Next(_Ptr);
				return *this;
			}
			//后置++的重载
			iterator operator++(int)
			{
				iterator tem(_Ptr);
				++*this;
				return tem;
			}
			//前置--的重载
			iterator& operator--()
			{
				_Ptr = _Acc::_Prev(_Ptr);
				return *this;
			}
			//后置--的重载
			iterator operator--(int)
			{
				iterator tmp(_Ptr);
				--*this;
				return tmp;
			}
			//返回Ptr指针
			_Nodeptr _Mynode()
			{
				return _Ptr;
			}
		private:
			_Nodeptr _Ptr;
		};

	//刨析写法一:

	//public:
	//	explicit list() :_Head(nullptr), _Size(0)
	//	{
	//		_Head = new _Node;
	//		_Head->_Next = _Head;
	//		_Head->_Prev = _Head;
	//	}

	//刨析写法二
	//public:
	//	explicit list() :_Head(_Buynode()), _Size(0)
	//	{}
	//protected:
	//	_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
	//	{
	//		_Nodeptr _S = new _Node;
	//		_S->_Next = _Narg != 0 ? _Narg : _S;
	//		_S->_Prev = _Parg != 0 ? _Parg : _S;

	//		return _S;
	//	}

		//源码写法,封装性更好,不会让数据暴露
		public:
			//构造函数
			explicit list() :_Head(_Buynode()), _Size(0)
			{}
			list(size_type _N, const _Ty& _V = _Ty()):_Head(_Buynode()), _Size(0)
			{
				insert(begin(), _N, _V);
			}
			list(const _Ty *_F, const _Ty *_L)
				:_Head(_Buynode()), _Size(0)
			{
				insert(begin(), _F, _L);
			}
			//析构函数
			~list()
			{
				//erase(begin(), end());
				clear();
				_Deletenode(_Head);
				_Head = 0, _Size = 0;
			}
	  //  public:
			//void push_back(const _Ty& _X)
			//{
			//	_Nodeptr _S = new _Node;
			//	_S->_Value = _X;
			//	_S->_Prev = _Head->_Prev;
			//	_S->_Next = _Head;
			//	_Head->_Prev = _S;
			//	_S->_Prev->_Next = _S;
			//	++_Size;
			//}
	public:
		//begin()迭代器 返回第一个真实节点
		iterator begin()
		{
			return iterator(_Acc::_Next(_Head));
		}
		//end()迭代器 返回头节点
		iterator end()
		{
			return iterator(_Head);
		}
			尾插
	  //  public:
			//void push_back(const _Ty& _X)
			//{
			//	_Nodeptr _S = _Buynode(_Head, _Acc::_Prev(_Head));
			//	_Acc::_Value(_S) = _X;
			//	_Acc::_Next(_Acc::_Prev(_S)) = _S;
			//	_Acc::_Prev(_Acc::_Next(_S)) = _S;
			//	++_Size;
			//}

		//尾插
		void push_back(const _Ty& _X)
		{
			insert(end(), _X);
		}
		//头插
		void push_front(const _Ty& _X)
		{
			insert(begin(), _X);
		}

		//数据结构写法

		//public:
		//	//指定一个位置进行插入
		//	iterator insert(iterator _P, const _Ty& _X = _Ty())
		//	{
		//		_Nodeptr _S = new _Node;
		//		_Acc::_Value(_S) = _X;
		//		
		//		_Nodeptr _N = _P._Mynode();
		//		_S->_Next = _N;
		//		_S->_Prev = _N->_Prev;
		//		_S->_Prev->_Next = _S;
		//		_S->_Next->_Prev = _S;
		//		++_Size;
		//		return iterator(_S);
		//	}

		public:
			iterator insert(iterator _P, const _Ty& _X = _Ty())
			{
				//_S指向_P位置
				_Nodeptr _S = _P._Mynode();
				//新节点连向它的后继和前驱,_P连接新节点
				_Acc::_Prev(_S) = _Buynode(_S, _Acc::_Prev(_S));
				//_S指向新节点
				_S = _Acc::_Prev(_S);
				//_S的前驱的后继指向_S
				_Acc::_Next(_Acc::_Prev(_S)) = _S;
				_Acc::_Value(_S) = _X;
				++_Size;
				return (iterator(_S));
			}
			//删除节点
			iterator erase(iterator _P)
			{
				_Nodeptr _S = (_P++)._Mynode();
				_Acc::_Next(_Acc::_Prev(_S)) = _Acc::_Next(_S);
				_Acc::_Prev(_Acc::_Next(_S)) = _Acc::_Prev(_S);
				_Deletenode(_S);
				--_Size;
				return (_P);
			}
			void insert(iterator _P, size_type _M, const _Ty& _X)
			{
				for (; 0 < _M; --_M)
					insert(_P, _X);
			}
			void insert(iterator _P, const _Ty *_F, const _Ty *_L)
			{
				for (; _F != _L; ++_F)
					insert(_P, *_F);
			}
			//删除一个区间
			iterator erase(iterator _F, iterator _L)
			{
				while (_F != _L)
					erase(_F++);
				return (_F);
			}
			//清除函数
			void clear()
			{
				erase(begin(), end());
			}
			//申请节点
		protected:
			_Nodeptr _Buynode(_Nodeptr _Narg = 0, _Nodeptr _Parg = 0)
			{
				_Nodeptr _S = new _Node;
				_Acc::_Next(_S) = _Narg != 0 ? _Narg : _S;
				_Acc::_Prev(_S) = _Parg != 0 ? _Parg : _S;

				return _S;
			}
			void _Deletenode(_Nodeptr _S)
			{
				delete _S;
			}


	private:
		_Nodeptr _Head;
		size_type _Size;
	};
}

void main()
{
	code::list<int>mylist;
	mylist.push_back(1);
	mylist.push_back(2);
	mylist.push_back(3);
	//code::list<int>::iterator pos = mylist.begin();
	///*mylist.erase(pos);*/
	mylist.clear();
	code::list<int>::iterator it = mylist.begin();
	while (it != mylist.end())
	{
		cout << *it << "->";
		++it;
	}
	cout << "end" << endl;
}

文章来源:https://blog.csdn.net/weixin_50886514/article/details/116090940

后台-系统设置-扩展变量-手机广告位-内容正文底部
版权声明

本文仅代表作者观点,不代表本站立场。
本文系作者授权发表,未经许可,不得转载。
本文地址:https://jcdi.cn/diannaochangshi/qukuailian/799.html

留言与评论(共有 0 条评论)
   
验证码:
后台-系统设置-扩展变量-手机广告位-评论底部广告位

教程弟

https://www.jcdi.cn/

统计代码 | 京ICP1234567-2号

Powered By 教程弟 教程弟

使用手机软件扫描微信二维码