C++:STL--List_c++ stl list

STL容器的代码设计中,模板编程和代码复用的思想贯穿始终,代码复用可以将各个成员接口统一起来从而大大增加程序的可读性和可维护性,模板编程使得容器类可以根据需要用于存储各种不同类型的数据.

一.STL-list的数据结构

C++STL标准库中的list使用的数据结构是带头双向循环链表;

• 链表的头结点不用于存储有效数据
• 以图示中的方式设计出来的循环链表,在链表中的任意位置的插入和删除结点操作的代码逻辑都是一样的,而且无须区分空表和非空表的情形,代码实现起来非常方便

链表结点模板

	template<class DataType>
	struct ListNode
	{
		ListNode(const DataType& val = DataType())
			:_prev(nullptr)
			,_next(nullptr)
			,_data(val)
		{}
		
		ListNode<DataType>* _prev;
		ListNode<DataType>* _next;
		DataType _data;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13

二.List的框架与迭代器的实现

1.STL中的容器迭代器

STL容器的迭代器是用于访问容器中数据元素的工具,其本质上是将数据元素指针封装成类(或类模板),该类(或类模板)会对外提供成员接口(一般是运算符重载),使得迭代器对象可以像指向数组元素的普通指针一样被使用(通常支持++,- -,比较(= =,! =),解引用(*,->)等等操作)(于是遍历容器中数据元素的代码形式也变得和遍历数组元素的代码形式一致) ,从而实现容器元素遍历访问方式的高级抽象

2.List的迭代器

List正向遍历迭代器类模板(对ListNode< T >* 指针的封装)

	template <class Datatype, class Ref, class Ptr>
	class ListIterator
	{
	public:
		//告诉编译器Ptr和Ref是类型名,而不是全局变量,为实现反向迭代器做准备
		typedef Ref Ref;
		typedef Ptr Ptr;

		//简化迭代器命名,方便代码编写
		typedef ListIterator<Datatype, Ref, Ptr> Self;
		//在迭代器中实例化结点模板
		typedef ListNode<Datatype> Node;

		//构造函数
		ListIterator(Node* ptr = nullptr)
		{
			_PtrNode = ptr;
		}
		//ListIterator(const Node* ptr) 
		//{
		//	_PtrNode = ptr;
		//}
		
		//重载*运算符,返回结点数据的引用
		Ref operator*() const
		{
			return _PtrNode->_data;
		}

		//重载->,函数返回值是结点数据的地址
		//当结点数据类型仍然为自定义结构时会用到,
		Ptr operator->() const
		{
			return &(_PtrNode->_data);
		}

		//重载前置++,函数返回值是迭代器的自引用
		Self& operator++()
		{
			_PtrNode = _PtrNode->_next;
			return (*this);
		}

		//重载后置++,函数返回值是迭代器的自引用
		Self operator++(int)
		{
			Self tem(*this);
			_PtrNode = _PtrNode->next;
			return tem;
		}

		//重载前置--,函数返回值是迭代器的自引用
		Self& operator--()
		{
			_PtrNode = _PtrNode->_prev;
			return (*this);
		}

		//重载后置--,函数返回值是迭代器的自引用
		Self operator--(int)
		{
			Self tem(*this);
			_PtrNode = _PtrNode->_prev;
			return tem;
		}

		//重载比较运算符==
		bool operator==(const Self It) const
		{
			return _PtrNode == It._PtrNode;
		}

		//重载比较运算符!=
		bool operator!= (const Self It) const
		{
			return !((*this) == It);
		}
		
		//提供获取节点指针的接口
		Node* GetPtr()
		{
			return _PtrNode;
		}
		const Node* GetPtr()const
		{
			return _PtrNode;
		}
	    //成员指针
		Node* _PtrNode;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

• 在迭代器中需要通过typedef对结点模板进行实例化:
  

• 正向迭代器模板之所以要设计三个模板参数是为了能够利用同一个迭代器模板去实例化出普通迭代器和const迭代器:

• const迭代器是只能访问数据元素而不能修改数据元素的迭代器(一般供const对象使用)
  

反向遍历迭代器的类模板(对正向迭代器的封装)

• List反向迭代器是通过复用正向迭代器类模板实现的

	template<class Iterator>
	class ReverseListIterator
	{
	public:

		//告诉编译器Ref和Ptr是Iterator类域中的类型名称
		typedef typename Iterator::Ref Ref;
		typedef typename Iterator::Ptr Ptr;
		
		typedef ReverseListIterator<Iterator> Self;

		//构造函数
		ReverseListIterator(const Iterator& Rit = Iterator())
			:_Rit(Rit)
		{}

		//重载*运算符,返回结点数据的引用
		Ref operator*() const
		{
			return *_Rit;
		}

		//重载->,函数返回值是结点数据的地址
		//当结点数据类型仍然为自定义结构时会用到,
		Ptr operator->() const
		{
			return &(*_Rit);
		}

		//重载前置++,函数返回值是迭代器的自引用
		Self& operator++()
		{
			--_Rit;
			return (*this);
		}

		//重载后置++,函数返回值是迭代器的自引用
		Self operator++(int)
		{
			Self tem(*this);
			--_Rit;
			return tem;
		}

		//重载前置--,函数返回值是迭代器的自引用
		Self& operator--()
		{
			++_Rit;
			return (*this);
		}

		//重载后置--,函数返回值是迭代器的自引用
		Self operator--(int)
		{
			Self tem(*this);
			++_Rit;
			return tem;
		}

		//重载比较运算符==
		bool operator==(const Self It) const
		{
			return It._Rit== _Rit;
		}

		//重载比较运算符!=
		bool operator!= (const Self It) const
		{
			return !((*this) == It);
		}

	
		Iterator _Rit;
	};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

3.List的实现框架

	template<class T>
	class List
	{
	public:
		//实例化并重命名链表结点模板
		typedef ListNode<T> Node;
		
		//实例化并重命名正向迭代器模板
		typedef ListIterator<T, T&, T*> iterator;
		typedef ListIterator<T, const T&, const T*> const_iterator;

		//实例化并重命名反向迭代器模板
		typedef ReverseListIterator<iterator> reverse_iterator;
		typedef ReverseListIterator<const_iterator> const_reverse_iterator;

		//获取迭代器的成员接口
		iterator begin()
		{
			return iterator(_Node->_next);
		}
		const_iterator begin() const
		{
			return const_iterator(_Node->_next);
		}
		iterator end()
		{
			return iterator(_Node);
		}
		const_iterator end() const
		{
			return const_iterator (_Node);
		}
		reverse_iterator rbegin()
		{
			return reverse_iterator(--end());
		}
		reverse_iterator rbegin() const
		{
			return reverse_iterator(--end());
		}
		reverse_iterator rend()
		{
			return reverse_iterator(--begin());
		}
		const_reverse_iterator rend()  const
		{
			return const_reverse_iterator(--begin());
		}





		//基本功能的成员接口
		//申请链表结点的接口
		Node* BuyListNode(const T& val = T());
		//清空List
		//采用头删删除(寻址比较方便)
		void clear();
		//交换两个list对象的内容
		void swap(List<T>& list);
	private:
		//创建头节点的私有成员接口
		void Creathead();
	public:




		//List容器的数据进出接口
		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val);
		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos);
		//链表尾插接口
		void push_back(const T& val);
		//链表尾删接口
		void pop_back();
		//链表头插接口
		void push_front(const T& val);
		//链表头删接口
		void pop_front();








		//List的构造函数
		//默认构造函数
		List();
		//构造函数模板
		//(用迭代器区间构造List对象,迭代器可以是其他类型容器的迭代器)     	
		template <class Iterator>
		List(Iterator first, Iterator last);
		//拷贝构造函数
		List(const List<T>& list);
		//创建n个T值节点的构造函数
		List(int n, const T& value = T());
		
		//List的赋值运算符重载
		List<T>& operator=(List<T> templist);

		


		//访问List各种存储信息的接口
		size_t size()const;
		//链表判空接口
		bool empty() const;
		//重新设置链表节点个数的接口
		void resize(size_t newsize, const T& data = T());

		//返回首数据元素
		T& front();
		//const重载(const修饰this指针使得const对象可以调用该接口)
		const T& front()const;
		//返回尾数据元素
		T& back();
		//const重载(const修饰this指针使得const对象可以调用该接口)
		const T& back()const;


		//List的析构函数
		~List();

	private:
		Node* _Node;
	};
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

• List对象的成员变量只有一个结点指针,用于指向链表的头节点
• List的框架中有五个需要实例化的模板:链表结点模板,正向迭代器模板,const正向迭代器模板,反向迭代器模板,const反向迭代器模板,创建List对象时模板的实例化过程:

三. List的成员接口的实现

1.在List类中经常被复用的接口

• void Creathead();创建链表头节点时注意修改头节点的指针域使其指向头节点自身:

		void Creathead()
		{
			_Node = new Node;
			_Node->_next = _Node;
			_Node->_prev = _Node;
		}
1
2
3
4
5
6

• void clear();清空链表的接口

		//清空List
		//采用头删删除(寻址比较方便)
		void clear()
		{
			Node* cur = _Node->_next;
			while (cur != _Node)
			{
				Node *tem = cur->_next;
				delete cur;
				cur = tem;
			}
			//注意恢复空表的指针状态
			_Node->_next = _Node;
			_Node->_prev = _Node;
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• void swap(List<T>& list)交换两个链表的所有内容:实质上就是交换头节点指针的指向

		//交换两个list对象的内容
		void swap(List<T>& list)
		{
			std::swap(_Node, list._Node);
		}
1
2
3
4
5

2.List的四个构造函数重载和一个赋值运算符重载

		//List的构造函数
		//默认构造函数
		List()
		{
			Creathead();
		}
		//用容器迭代器区间去初始化List对象
		template <class Iterator>
		List(Iterator first, Iterator last)
		{
			Creathead();
			while (first != last)
			{
				push_back(*first);
				++first;
			}
		}
		//拷贝构造函数(复用迭代器构造函数实现)
		List(const List<T>& list)
		{
			//创建空表
			Creathead();
			List<T> tem(list.begin(), list.end());
			this->swap(tem);
		}
		//构造n个节点的链表的构造函数(复用尾插接口实现)
		List(int n, const T& value = T())
		{
			Creathead();
			while (n--)
			{
				push_back(value);
			}
		}

		//List的赋值运算符重载(复用交换函数和拷贝构造函数实现)
		List<T>& operator=(List<T> templist)
		{
			this->swap(templist);
			return (*this);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

• 赋值运算符重载被调用时,函数形参也是一个List对象(存在函数栈上),因此形参压栈时会调用拷贝构造函数完成被复制的对象的拷贝操作,函数返回时,templist会自动调用析构函数完成无用数据的清理

3.List容器的数据进出接口

		// 在pos位置前插入值为val的节点
		iterator insert(iterator pos, const T& val)
		{
			Node* temprve = pos._PtrNode->_prev;

			Node * NodenewNode = BuyListNode(val);
			temprve->_next = NodenewNode;
			pos._PtrNode->_prev = NodenewNode;

			NodenewNode->_next = pos._PtrNode;
			NodenewNode->_prev = temprve;

			--pos;
			return pos;
		}
		// 删除pos位置的节点，返回该节点的下一个位置
		iterator erase(iterator pos)
		{
			assert(!empty());
			Node* temprev = pos.GetPtr()->_prev;
			Node* tempnext = pos.GetPtr()->_next;

			iterator tem = pos;
			++tem;

			temprev->_next = tempnext;
			tempnext->_prev = temprev;
			delete pos.GetPtr();
			return tem;
		}
		//链表尾插接口
		void push_back(const T& val)
		{
			insert(end(), val);
		}
		//链表尾删接口
		void pop_back()
		{
			assert(!empty());
			erase(--end());
		}
		//链表头插接口
		void push_front(const T& val)
		{
			insert(begin(), val);
		}
		//链表头删接口
		void pop_front()
		{
			assert(!empty());
			erase(begin());
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

• 尾插,尾删,头插,头删接口都是通过接口复用的方式实现的

4.访问List各种存储信息的接口(以及resize接口)

		//获取节点个数
		size_t size()const
		{
			int count = 0;
			for (auto it : (*this))
			{
				count++;
			}
			return count;
		}
		//链表判空
		bool empty() const
		{
			return (begin() == end());
		}
		//调整链表节点个数(复用尾插尾删接口实现)
		void resize(size_t newsize, const T& data = T())
		{
			int Size = size();
			if (Size > newsize)
			{
				int Erase = Size - newsize;
				while (Erase--)
				{
					pop_back();
				}
			}
			else
			{
				int create = newsize - Size;
				while (create--)
				{
					push_back(T);
				}
			}
		}
		//获取表头数据
		T& front()
		{
			assert(!empty());
			return *begin();
		}
		const T& front()const
		{
			assert(!empty());
			return *begin();
		}
		//获取表尾数据
		T& back()
		{
			assert(!empty());
			return *(--end());
		}
		const T& back()const
		{
			assert(!empty());
			return *(--end());
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

5.List的析构函数

• 通过复用clear接口实现,当对象被销毁时由编译器自动调用完成内存清理工作

		~List()
		{
			clear();
			delete _Node;
			_Node = nullptr;
		}
1
2
3
4
5
6