C++ STL中的容器适配器实现

namespace czh
{
	template<class T, class Container = deque<T>>
	// template<class T, class Container = list<T>>
	// template<class T, class Container = vector<T>>
	class stack
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

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

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

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

	private:
		Container _con;
	};
}

namespace czh
{
	// 设计模式 -- 适配器模式(配接器)
	template<class T, class Container = deque<T>>
	class queue
	{
	public:
		void push(const T& x)
		{
			_con.push_back(x);
		}

		void pop()
		{
			_con.pop_front();
		}
        T& front()
		{
			return _con.front();
		}
		const T& front() const
		{
			return _con.front();
		}
		T& back()
		{
			return _con.back();
		}
		const T& back() const
		{
			return _con.back();
		}

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

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

	private:
		Container _con;
	};
}

#include <iOStream>
#include <vector>
#include <queue>
#include <functional> // greater算法的头文件
void TestPriorityQueue()
{
 // 默认情况下，创建的是大堆，其底层按照小于号比较
 vector<int> v{3,2,7,6,0,4,1,9,8,5};
 priority_queue<int> q1;
 for (auto& e : v)
 q1.push(e);
 cout << q1.top() << endl;
 // 如果要创建小堆，将第三个模板参数换成greater比较方式
 priority_queue<int, vector<int>, greater<int>> q2(v.begin(), v.end());
 cout << q2.top() << endl; 
 
 }

#include <iostream>
#include "priority_queue.h"
#include <alGorithm>
#include <vector>

using namespace std;

//仿函数的应用
struct Phone{
	int saleNum;
	int price;
	//.....
};
struct LessPhonePrice{
	bool operator()(const Phone& p1, const Phone& p2)
	{
		return p1.price < p2.price;
	}
};
struct LessPhoneSaleNum{
	bool operator()(const Phone& p1, const Phone& p2)
	{
		return p1.saleNum < p2.saleNum;
	}
};
void TestSort()
{
	vector <Phone> gv = { { 1, 3 }, { 5, 2 }, { 2, 10 } };
	sort(gv.begin(), gv.end(),LessPhoneSaleNum());//匿名对象会在STL中调用我自己写的比较方法
	sort(gv.begin(), gv.end(), LessPhonePrice());

}
int main()
{
	TestSort();
	return 0;
}

#pragma once

//仿函数
template<class T>
class Less{
public:
	bool operator()(const T& t1, const T& t2) const
	{
		return t1 < t2;
	}
};

template<class T>
class Greater{
public:
	bool operator()(const T& t1, const T& t2) const
	{
		return t1 > t2;
	}
};
namespace czh{

	template<class T, class Container = vector<T>, class Compare = Greater<T>>
	class priority_queue {

	public:
		priority_queue() = default;
		

		template<class InputIterator>
		priority_queue(InputIterator first, InputIterator last)
			:_con(first, last)
		{
			//利用向下调整算法，从下到上建堆
			
			利用向上调整算法，从上到下调整
			for (size_t i = 1; i < _con.size(); i++)
			{
				AdjustUp(i);
			}
		}
		void push(const T& data)
		{
			_con.push_back(data);
			// 向上调整
			AdjustUp(_con.size() - 1);
		}
		void pop()
		{
			if (empty()) return;

			swap(_con.front(),_con.back());
			_con.pop_back();
			AdjustDown(0);
		}
		size_t size() const
		{
			return _con.size();
		}
		const T& top() const
		{ 
			return _con.front();
		}
		bool empty() const
		{
			return _con.empty();
		}
	private:
		//向上调整算法
		void AdjustUp(int child)
		{
			Compare com;
			int parent = (child - 1) >> 1;
			while (child > 0)
			{
				
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					child = parent;
					parent = (child - 1) >> 1;
				}
				else
				{
					break;
				}
			}
		}
		void AdjustDown(int parent)
		{
			Compare com;
			size_t child = 2 * parent + 1;
			while (child < _con.size())
			{
				
				if (child + 1 < _con.size() && com(_con[child + 1], _con[child]))
				{
					child++;
				}
				
				if (com(_con[child], _con[parent]))
				{
					swap(_con[child], _con[parent]);
					parent = child;
					child = 2 * parent + 1;
				}
				else
				{
					break;
				}
			}
		}
		//向下调整算法
		Container _con;
	};
}