stack,queue和prioriy_queue

MySTL

stack和queue

template <class T, class Container = deque<T> > 
class queue;

template <class T, class Container = deque<T> > 
class stack;

选择适配器的宗旨是要能达到预想的功能
queue——只能使用list和deque
stack——可以使用vector和list和deque

priority_queue

template

	template<class T,class Container=vector<T>,class Com = less<T>>

需要注意的是依赖的容器一定是一个随机访问的容器，支持[]的容器

---

up和down的时间复杂度

up——O(n*log(n))
down——O(n)
down优于up

down易错点

		void _down(int parent)
		{
			Com com;
			int n = _con.size();
			int child = parent * 2 + 1;
			//while (child < n && child + 1 < n)
			// 两个child能不能交换都要先进去
			while(child < n)
			{
				if (child +1 < n 
					&& com(_con[child + 1],_con[child])) 
					child++;
				if (com(  _con[child],_con[parent])) swap(_con[parent], _con[child]);
				parent = child;
				child = parent * 2 + 1;
			}
		}

不能将while条件(child < n && child + 1 < n),而是写成while(child < n)
因为可能只有左节点，没有右节点，对于这种情况，当满足交换的调价的时候也是需要交换的

对于这种情况，如果1可以和2进行交换，不能写成(child < n && child + 1 < n)，如果要进行交换最起码先进去吧

---

仿函数

	template<class T>
	struct less
	{
		bool operator()(T& a, T& b)
		{
			return a > b;
		}
	};

对于仿函数，需要理解当判断为True的时候，执行需要做的语句；那么这也就需要在传a,b的时候注意顺序

---

		template<class Iterator>
		priority_queue(const Iterator& first, const Iterator& end)
			:_con(first,end)
		{
			//for (int i = 0; i < _con.size(); i++)
			//	_up(i);
			// 向下调整建堆O(n)
			// 向上调整建堆O(n*log(n))
			for (int i = _con.size() - 1; i >= 0; i--)
				_down(i);
		}

Iterator传的是一个迭代器类型，可以利用_con的迭代器构造

priority_queue对于指针的特殊处理

	void test2()
	{
		int* c = new int(4);
		int* a = new int(1);
		int* b = new int(2);
		int* d = new int(3);
		int* nums[10] = { a,b,c,d };
		priority_queue<int*> q;
		for (int i = 0; i < 4; i++)
			q.push(nums[i]);
		while (q.size())
		{
			cout << *(q.top()) << " ";
			q.pop();
		}
		puts("");

		priority_queue<int> qt;
		qt.push(4);
		qt.push(1);
		qt.push(2);
		qt.push(3);
		while (qt.size())
		{
			cout << qt.top() << " ";
			qt.pop();
		}
	}
}

插入顺序完全相同的优先队列，为什么最后的结果回不一样

对于内置数据类型，比较的时候是直接进行比较；对于自定义数据类型，重载关系运算符进行比较
这里默认进行的就是直接比较

进行如下修改
priority_queue<int*,vector<int*>,Com<int*>> q;

		template<class T>
		struct Com
		{
			bool operator()(const T& a, const T& b)
			{
				return *a < *b;
			}
		};

		int* c = new int(4);
		int* a = new int(1);
		int* b = new int(2);
		int* d = new int(3);
		int* nums[10] = { a,b,c,d };
		priority_queue<int*,vector<int*>,Com<int*>> q;
		for (int i = 0; i < 4; i++)
			q.push(nums[i]);
		while (q.size())
		{
			cout << *(q.top()) << " ";
			q.pop();
		}
		puts("");