C++的deque(双端队列),priority_queue(优先级队列)

deque

deque是一个容器,是双端队列,从功能上来讲,deque是一个vector和list的结合体

顺序表和链表

deque的结构和优缺点

开辟buff小数组,空间不够了,不扩容,而是开辟一个新的小数组

开辟中控数组(指针数组)指向buff小数组

将已存在的数组指针存在中控数组中间,可以使用下标访问

头插向前插,尾插向后插,相比于vector可以较高效率的进行头尾操作

cur指向具体数据,node指向当前数组

first指向数组开始,last指向数组结束

遍历

it == end()后,将it.指向node->first,即下一个buff数组的第一个数据

deqeu的迭代器

用两个迭代器指向第一个和最后一个buff的位置

其余的buff可以通过+-来获得

注意,头插是将数据插入新的开头的buff的尾部

eg.

缺点

在buff小数组内插入删除数据,需要挪动数据,效率低于vector

[ ]访问的效率也不高

因此不能代替vector和list

priority_queue

优先级队列也是一个容器适配器

他的底层是一个堆(二叉堆),需要大量使用 [ ] 访问

优先级队列默认是大堆

迭代器区间构造

仿函数

由于优先级队列默认是大堆

如果想换成小堆,就要使用仿函数

eg.

仿函数就是函数对象:重载了operator()的类

类的对象可以想函数一样使用

eg.

这里的f1() = f1.operator()

即对象可以像函数一样使用

自定义类型

优先级队列需要用户在自定义类型中提供>和<的重载

eg.

日期类

底层

#pragma once
 
#include
template<class T>
class myless
{
	bool operator()(const T& x, const T& y)
	{
		return x < y;
	}
};
 
template<class T>
class mygreater
{
	bool operator()(const T& x, const T& y)
	{
		return x > y;
	}
};
namespace bit 
{
	template<class T, class Container = vector, class Compare >//分别是容器内存放的数据的类型,容器和用于比较的仿函数(默认是less)
	class priority_queue
	{
	public:
		//强制编译器生成默认构造
		priority_queue() = default;
 
		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)//迭代器区间构造
		{
			while (first != last)
			{
				_con.push_back(*first);//所有数据放入(现在还不是堆)
				++first;
			}
 
			//建堆
			for (int i = (_con.size() - 1 - 1) / 2; i < length; i++)//从倒数第一个非叶子节点开始建堆
			{
				adjust_down(i);
			}
		}
		void adjust_up(int child)//制造大堆
		{
			Compare comfunc;
			int parent = (child - 1) / 2;
			while (child > 0)
			{
				if (compfunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
				{
					break;
				}
			}
		}
 
		void push(const T& x)
		{
			_con.push_back(x);
			adjust_up(_con.size() - 1);//向上调整
 
		}
 
		void adjust_down(int parent)
		{
			Compare compfunc
			int child = parent * 2 + 1;//左孩子
			while (child < _con.size())
			{
				if (child + 1 < _con.size() && _con.[child] < _con[child + 1])//假设左孩子大且右孩存在
				{
					++child;
				}
 
				if (compfunc(_con[parent], _con[child]))
				{
					swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
				{
					break;
				}
			}
		}
 
		void pop()
		{
			swap(_con[0], _con[_con.size() - 1]);
			_con.pop_back();
 
			adjust_down(0);
		}
 
		const T& top()
		{
			return _con[0];
		}
 
		size_t size()
		{
			return _con.size();
		}
 
		bool empty()
		{
			return _con.empty();
		}
	private:
		Container _con;
 
	};
}