(第八步) STL: stl_priority_queue容器实现

priority queue

priority_queue带有权值观念，其内的元素并非依照被推人的次序排列，而是自动依照元素的权值排列（通常权值以实值表示），权值最高者，排在最前面。

priority_queue利用一个max-heap完成，map-heap是一个以vector表现的complete binary tree 。 max-heap可以满足priority_queue所需要的“依权值高低自动递增排序”的特性。

理解完上一节中的max-heap，很容易就理解priority queue的概念。

stl_priority_queue.h

#ifndef _PRIORITY_QUEUE_H_
#define _PRIORITY_QUEUE_H_

#include "../Includes/Functional.h"
#include "../p2_STL_Source/stl_vector.h"
#include "../Includes/Algorithm.h"

namespace mySTL {
	// priority queue队列
	// 实现max-heap或者min-heap，最好的容器选择为vector实现完全二叉树结构heap
	template <class T, class Container = mySTL::vector<T>,
		class Compare = mySTL::less<typename Container::value_type>>
		class priority_queue {
		public:
			typedef T										value_type;
			typedef Container								container_type;
			typedef typename Container::reference			reference;
			typedef typename Container::const_reference		const_reference;
			typedef typename Container::size_type			size_type;
		private:
			container_type container_;
			Compare compare_;

		public:
			explicit priority_queue(const Compare& comp = Compare(),
				const Container& ctnr = Container())
				: container_(ctnr), compare_(comp) {}

			template <class InputIterator>
			priority_queue(InputIterator first, InputIterator last,
				const Compare& comp = Compare(),
				const Container& ctnr = Container())
				: container_(ctnr), compare_(comp) {
				container_.insert(container_.end(), first, last);	// 在end() 位置插入
				mySTL::make_heap(container_.begin(), container_.end());	
			}

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

			size_type size() const {
				return container_.size();
			}

			reference top() {
				return container_.front();
			}

			void push(const value_type& val) {
				// 填入，然后改变完全二叉树结构
				container_.push_back(val);	
				mySTL::push_heap(container_.begin(), container_.end(), compare_);
			}
			void pop() {
				// 把根节点下沉，至末尾，然后再弹出
				mySTL::pop_heap(container_.begin(), container_.end(), compare_);
				container_.pop_back();
			}

			void swap(priority_queue& x) {
				mySTL::swap(container_, x.container_);
				mySTL::swap(compare_, x.compare_);
			}
		public:
			template <class T, class Container, class Compare>
			friend void swap(priority_queue<T, Container, Compare>& x, priority_queue<T, Container, Compare>& y);
	};
	template <class T, class Container, class Compare>
	void swap(priority_queue<T, Container, Compare>& x, priority_queue<T, Container, Compare>& y) {
		x.swap(y);
	}
}

#endif

stl_priority_queue_test.h

#pragma once

#include "../p2_STL_Source/stl_priority_queue.h"


#include <queue>

#include <algorithm>
#include <cassert>
#include <string>

namespace mySTL 
{
	namespace priorityQueueTest 
	{
		template<class T>
		using stdPQ = std::priority_queue < T >;
		template<class T>
		using myPQ = mySTL::priority_queue < T >;

		void test01();
		void test02();
		void test03();
		void test04();
	}
}

stl_priority_queue_test.cpp

#include "stl_priority_queue_test.h"

using namespace std;

namespace mySTL
{
	namespace priorityQueueTest
	{
		void test01()
		{
			int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, -1, -2, -3 };
			stdPQ<int> pq1(std::begin(arr), std::end(arr));
			myPQ<int> pq2(std::begin(arr), std::end(arr));

			cout << "stdPQ is empty: " << boolalpha << pq1.empty()
				<< "\tmyPQ is empty: " << pq2.empty() << endl;

			while (!pq1.empty() && !pq2.empty()) {
				cout << "stdPQ: " << pq1.top() << "\tmyPQ: " << pq2.top() << endl;
				pq1.pop(); pq2.pop();
			}

			cout << "stdPQ is empty: "<<boolalpha << pq1.empty() 
				<< "\tmyPQ is empty: " << pq2.empty() << endl;
		}

		void test02()
		{
			myPQ<std::string> pq;

			pq.push("zxh");
			cout << pq.top() << endl;
		}

		void test03()
		{
			myPQ<int> pq;
			auto i = 1;
			for (; i != 10; ++i) {
				pq.push(i);				
			}
			cout << "size is: " << pq.size() << endl;

			for (i = pq.size(); i != 0; --i) {
				pq.pop();
			}
			cout << "size is: " << pq.size() << endl;
		}

		void test04()
		{
			myPQ<int> foo, bar;
			foo.push(15); foo.push(30); foo.push(10);
			bar.push(101); bar.push(202);

			cout << "size1 is 3 : " << foo.size() << endl;
			cout << "size2 is 2 : " << bar.size() << endl;

			foo.swap(bar);
			cout << "size1 is 2 : " << foo.size() << endl;
			cout << "size2 is 3 : " << bar.size() << endl;

			mySTL::swap(foo, bar);
			cout << "size1 is 3 : " << foo.size() << endl;
			cout << "size2 is 2 : " << bar.size() << endl;
		}
	}
}