queue和priority_queue使用+模拟实现

queue

queue和stack一样也是一个容器适配器，并且他们的底层都是deque也就是双端队列。

队列是一种先进先出的容器。与stack类似，其适配器也可以其他容器比如list，但是queue不可以使用vector封装实现，因为vector缺少了头删接口，因为vector的头删效率很低，一般queue的实现都是使用的list或deque。

queue的函数接口

这里的emplace也是和push功能式一样的，只是引入了C++11中的右值引用。

queue的模拟实现

#pragma once
#include

namespace xzj
{
	template<class T,class Container = std::deque<T>>
	class queue
	{
	public:

		void push(const T& val)
		{
			_con.push_back(val);
		}
		void pop()
		{
			_con.pop_front();
		}
		size_t size() const
		{
			return _con.size();
		}
		T& front()
		{
			return _con.front();
		}
		T& back()
		{
			return _con.back();
		}
		const T& front() const
		{
			return _con.front();
		}
		const T& back() const
		{
			return _con.back();
		}
		bool empty() const
		{
			return _con.empty();
		}

	private:
		Container _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

仿函数

仿函数就是一种类的对象，类里面重载了括号运算符，这样这个类的对象就可以像函数一样使用了。

#include

using std::cout;
using std::endl;

template<class T>
struct compare_greater
{
	bool operator()(const T& x,const T& y)
	{
		return  x > y;
	}
};

template<class T> 
bool fun_greater(const T& x, const T& y)
{
	return x > y;
}

int main()
{
	compare_greater<int> ls;
	cout << ls(10, 9) << endl;
	cout << fun_greater(1, 10) << endl;
	return 0;
}
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

这就是简单的仿函数的结构和使用，将仿函数生成一个比较器类型，在定义模板类的时候就可以使用这个类型作为一个模板类型的缺省参数，通过在模板类内创建一个对象就可以实现在类内部使用对象来完成像函数一样的比较大小的作用。
方便的是，如果想要将大于改为小于不需要改类内部的代码，只需要在实例化的时候传一个比较器类型即可。
下面priority_queue的实现代码中_compare就是仿函数的应用，只需要在实例化的时候传不同的比较器类型就可以实现大堆和小堆的转换

priority_queue

priority是优先级的意思，所以这个容器就是优先级队列。

这里的参数可以看到多了一个Compare，这第三个参数就是仿函数。仿函数是一个函数对象，这个对象的类通过重载运算符，使得这个类的对象可以像函数一样使用。

优先级队列就是出队列的时候按照元素的优先级出，其实就是按照大小出，优先级队列的底层适配器是vector，但是加上了堆的算法，成了优先级队列，实际底层就是一个堆。优先级根据底层是大堆还是小堆来确定，在实例化的时候可以通过仿函数来控制，less就是<的比较。就是大堆。反之greater是>的比较，就是小堆。大堆是less，小堆是greater正好是相反的需要特殊记住。

priority_queue的使用

这里的成员函数基本类似于queue，这里不做过多的赘述，实际上这些函数的操作也是和队列一样的，只是在出队列的时候并不是先入先出，而是按照优先级出队列。

priority_queue的模拟实现

priority_queue这个容器适配器底层容器是vector，同时加入了堆的heap_push,heap_pop,make_heap等等算法的封装构成了priority_queue，这里的底层容器我们也可以使用deque，但是选择的底层容器必须支持随机访问。

#pragma once
#include
#include

namespace xzj
{
    //模板类型，底层容器适配器给默认缺省类型，比较器用仿函数给出默认是less小于比较，所以这里是大堆
	template<class T,class Container = std::vector<T> ,class Compare = std::less<T>>
	class priority_queue
	{
	public:
        //无参构造，只需要不传参数针对自定义类型编译器会自动调用vector的构造函数
		priority_queue()
			:_con()
		{}
        //用迭代器区间构造
        //先用迭代器区间构造vector，然后对vector进行建堆，这里使用的建堆算法是从底部开始
        //向下调整算法，是最优的建堆算法，时间复杂度是O（N）
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first,last)
		{
			for (int i = (_con.size() - 2) / 2; i >= 0; i--)
			{
				AdjustDown(_con.size(),i);
			}
		}
        //向上调整算法，是heap_push核心算法，插入的新数据
        //需要使用向上调整，使其到达正确位置
		void AdjustUp(int child)
		{
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (_compare(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					break;
			}
		}
        //向下调整算法，用于heap_make，和heap_pop删除元素时先让第一个元素和最后元素交换
        //然后使用向下调整算法。
		void AdjustDown(int n, int parent)
		{
			int child = parent * 2 + 1;
			while (child < n)
			{
				//建大堆选大孩子
				if (child + 1 < n && _con[child] < _con[child + 1])
					child++;
				if (_con[parent] < _con[child])
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					break;
			}
		}
		void push(const T& x)
		{
			_con.push_back(x);
			AdjustUp( _con.size() - 1);
		}
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
			AdjustDown( _con.size(), 0);
		}

		bool empty() const
		{
			return _con.empty();
		}
		T& top()
		{
			return _con[0];
		}
		size_t size() const
		{
			return _con.size();
		}
	private:
		Container _con;
		Compare _compare;
	};
}
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

这里的成员变量Compare类型的_compare变量就是仿函数的应用，只需要在实例化的时候传不同的比较器类型就可以实现大堆和小堆的转换。

关于容器适配器

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

前面说到的queue和stack都是容器适配器。
形象的理解可以是手机的充电器或者是电脑的电源适配器，因为我们的手机和电脑不可能直接使用220v交流电进行充电，所以需要通过适配器进行转换。容器适配器也是一样的，将底层的容器接口通过封装转换成我们需要的接口。

deque

deque的特性

deque是双端队列，他的结构如下图：

deque的成员函数很多

经过观察我们发现，deque不仅支持[ ]随机访问，并且支持头插和头删，vector里面是没有头插和头删的，同时deque也支持中间任意位置的插入和删除。所以说deque就像是list和vector的结合体。

那么，deque能不能替代vector和list呢？

答案是：不可以

首先deque的特性，适合头尾的插入和删除，但是不适合大量的中间位置的插入和删除，以及大量的随机访问。虽然deque能做到随机访问但是效率远不如vector，同时中间位置的插入和删除的效率也是不如list的。因此deque是不能替代vector和list的。

vector的特性
1.适合尾部插入和删除，随机访问的效率很高
2.头部和中间插入删除的效率很低
3.空间不够的时候需要增容，增容需要付出性能消耗，代价大。
list的特性
1.任意位置的插入删除都是O（1）
2.按需要申请和释放空间
3.致命缺点：不支持随机访问

deque的内部结构

deque为什么具有vector和list的特性呢？
deque的内部结构是由很多个定长数组组成的，同时有一个指针数组作为中控，将这些数组的地址保存下来。
同时为了适应随机访问，deque的迭代器设计的较为复杂。下面我们来看一下deque的内部结构

deque的成员变量有迭代器start和finish，指针数组map，和map数组的大小，map_size；

在这里优先使用的是map数组里面的中间部分，所以头插的时候需要再次开辟一个buff数组然后让start迭代器中的first和last指向新数组的头尾，在尾部插入数据，cur指向该数据，node向前移动。

总结deque

deque与vector比较，头部的插入和删除不需要移动数据效率更高
扩容的时候因为map数组里面存放的是指针，所以在扩容的时候的拷贝会比vector拷贝全部数据的效率高很多。

与list相比，存储空间是连续的，空间利用率高，同时缓存命中率高，因为连续的数据空间，每次缓存加载的时候都是加载一块空间而不是单个数据空间。

但是，deque有一个致命缺陷：不适合遍历，因为在遍历时，deque的迭代器要频繁的去检测其是否移动到某段小数组的边界，到达边界需要将遍历迭代器it的node先移动到下一个位置，然后改变first和last指针，然后使用cur从小数组的头部开始遍历，导致效率低下，而序列式场景中，可能需要经常遍历，因此在实际中，需要线性结构时，大多数情况下优先考虑vector和list，deque的应用并不多，而目前能看到的一个应用就是，STL用其作为stack和queue的底层容器。

deque为什么能作为stack和queue的底层容器

因为stack需要一端比如尾部的插入和删除，而deque在尾部的插入和删除的效率很高，并且在扩容的时候效率也是高于vector的。而queue这种数据结构直需要尾插和头删接口就可以实现，deque在头尾的插入删除效率也很高，同时deque是连续的空间，在缓存命中率上更高。内存使用效率高。
最重要的是：stack和queue不需要遍历，这正好避开了deque的缺陷。

因此deque比vector和list更适合作为stack和queue的底层容器。