容器适配器【stack、queue、priority_queue和反向迭代器】

全文目录

• 适配器原理
• `stack`和`queue`
• • deque
• 模拟实现stack
• 模拟实现queue
• 模拟实现priority_queue
• 反向迭代器

适配器原理

适配器：适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总结)，该种模式是将一个类的接口转换成客户希望的另外一个接口。

stack和queue

虽然stack和queue中也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器，这是因为 stack和queue只是对其他容器的接口进行了包装 ，STL中stack和queue默认使用deque

deque

deque（double-ended queue，双端队列）是一种具有队列和栈的性质的数据结构。双端队列中的元素可以从两端弹出，相比list增加[]运算符重载。

详细介绍：deque概述

模拟实现stack

使用vector的接口实现stack的功能

#pragma once

#include <iostream>
#include <vector>

using namespace std;

namespace zwj
{
	template<typename T, typename Contaner = vector<T>>
	class stack
	{
	public:
		size_t size() const
		{
			return _con.size();
		}

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_back();
		}

		T& top()
		{
			return _con.back();
		}

		const T& top() const
		{
			return _con.back();
		}

		bool empty() const
		{
			return _con.empty();
		}

		void swap(stack& st)
		{
			_con.swap(st._con);
		}


	private:
		Contaner _con;
	};
}
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

模拟实现queue

使用list的接口实现queue的功能

#pragma once


#include <iostream>
#include <list>

using namespace std;

namespace zwj
{
	template<typename T, typename Contaner = list<T>>
	class queue
	{
	public:
		size_t size() const
		{
			return _con.size();
		}

		void push(const T& val)
		{
			_con.push_back(val);
		}

		void pop()
		{
			_con.pop_front();
		}

		T& back()
		{
			return _con.back();
		}

		const T& back() const
		{
			return _con.back();
		}

		T& front()
		{
			return _con.front();
		}

		const T& front() const
		{
			return _con.front();
		}

		bool empty() const
		{
			return _con.empty();
		}

		void swap(queue& q)
		{
			_con.swap(q._con);
		}


	private:
		Contaner _con;
	};
}
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

模拟实现priority_queue

优先级队列，底层就是一个堆结构。

priority_queue比stack和queue多了一个比较类的函数，默认传的是less（大端），传greater才会是小堆。

比较类的函数就是重载了operator()的类

#pragma once

#include <iostream>
#include <vector>
#include <functional>
#include <assert.h>

using namespace std;

namespace zwj
{
	template<typename T, typename Contaner = vector<T>, typename Compare = less<T>>
	class priority_queue
	{
	public:
		void adjust_down(size_t parent)
		{
			assert(parent <= _con.size());

			size_t child = parent * 2 + 1;
			size_t sz = _con.size();
			Compare com;
			while (child < sz)
			{
				if (child + 1 < sz && com(_con[child], _con[child + 1]))
					child++;

				if (com(_con[parent], _con[child]))
				{
					::swap(_con[child], _con[parent]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}

		void adjust_up(size_t child)
		{
			assert(child < _con.size());

			size_t parent = (child - 1) / 2;
			Compare com;
			while (child > 0)
			{
				if (com(_con[parent], _con[child]))
				{
					::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}

		priority_queue()
		{}

		template <class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			: _con(first, last)
		{
			for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--)
			{
				adjust_down(i);
			}
		}


		size_t size() const
		{
			return _con.size();
		}

		bool empty() const
		{
			return _con.empty();
		}

		
		const T& top() const
		{
			return _con[0];
		}

		void push(const T& val)
		{
			_con.push_back(val);
			adjust_up(_con.size() - 1);
		}

		void pop()
		{
			::swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			adjust_down(0);
		}


		void swap(priority_queue& pq)
		{
			_con.swap(pq._con);
		}

	private:
		Contaner _con;
	};
}
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

反向迭代器

反向迭代器的功能与正向迭代器是一样的，只是遍历的顺序不同，符合适配器模式，所以可以通过正向迭代器的接口实现反向迭代器。

注意事项：

1. 正反迭代器的begin和end是相对的，所以反向迭代器总是指向需要访问元素的后一个元素
2. $反向迭代器的++==正向迭代器的--$
3. 反向迭代器访问元素之前需要先 $--$ 才行。

以list的反向迭代器为例：

template<typename Iterator, typename Ref, typename Ptr>
class __reserve_iterator
{
public:
	typedef __reserve_iterator<Iterator, Ref, Ptr> self;

	// 正向迭代器
	Iterator _cur;

	// 通过正向迭代器构造反向迭代器
	__reserve_iterator(Iterator cur)
		: _cur(cur)
	{}


	// 反向操作
	self& operator++()
	{
		--_cur;
		return *this;
	}

	self operator++(int)
	{
		self tmp(_cur);
		--_cur;
		return tmp;
	}

	self& operator--()
	{
		++_cur;
		return *this;
	}

	self operator--(int)
	{
		self tmp(_cur);
		++_cur;
		return tmp;
	}

	// 先++(反向++）后访问
	Ref operator*()
	{
		auto tmp = _cur;
		--tmp;
		//self tmp(_cur);
		//++tmp;
		return *tmp;
	}

	Ptr operator->()
	{
		return &(operator*());
	}

	bool operator!=(const self& it)
	{
		return _cur != it._cur;
	}
};
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