小言_互联网的博客

C++ STL-List源码分析

2021-04-26 22:25 536人阅读  评论(0)

文章目录：

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
查看评论
* 以上用户言论只代表其个人观点，不代表本网站的观点或立场