template<class T, class Container = vector<T>, class Compare = Less<T>>
//Container，Compare 是我們對庫里面的結構進行了顯示構造便于我們理解底層結構
class priority_queue {
public:
    priority_queue() = default;  // 編譯器生成默認構造
private:
    Container _con;               // 底層容器
};

template<class InputIterator>
priority_queue(InputIterator first, InputIterator last)
	:_con(first, last)
{
	//給一個迭代器區(qū)間構造優(yōu)先隊列的底層是堆結構
	//向下調整建隊構造
	for (int i = (_con.size() - 1 - 1) / 2; i >= 0; i--) {
		adjust_down(i);
	}
}

void adjust_down(size_t parent) {
	Compare com;
	size_t child = parent * 2 + 1;
	while (child < _con.size()) {
		if (child + 1 < _con.size() && com(_con[child], _con[child + 1])) {
			child++;
		}
		// 如果 父節(jié)點優(yōu)先級 < 孩子節(jié)點優(yōu)先級，則交換
		// 在大堆中：parent < child -> com(parent, child) 為 true -> 交換
		// 在小堆中：parent > child -> com(parent, child) 為 true -> 交換
		if (com(_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);
    adjust_up(_con.size() - 1);
}

void adjust_up(size_t child) {
	Compare com;
	size_t parent = (child - 1) / 2;
	while (child > 0) {
		//if (_con[parent] < _con[child])
		if(com(_con[parent],_con[child])){
			swap(_con[parent], _con[child]);//調用的庫里面的函數(shù)
			child = parent;
			parent = (child - 1) / 2;
		}
		else {
			break;
		}
	}
}

void pop() {
	assert(!empty());
    std::swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    adjust_down(0);
}

const T& top() const { return _con[0]; }
bool empty() const { return _con.empty(); }
size_t size() const { return _con.size(); }

template<class T, class Container = vector<T>, class Compare = Less<T>>
//Container讓我們可以很輕松的更改priority_queue的底層存儲邏輯
//這里只是給一個缺省值我們可以顯示給的
class priority_queue {
    Container _con;
};

template<class T>
class Less {
public:
	bool operator()(const T& x, const T& y) {
		return x < y;
	}
};
template<class T>
class Greater {
public:
	bool operator()(const T& x, const T& y) {
		return x > y;
	}
};

int main() {
//默認使用 Less → 大堆
	ZL::priority_queue<int> pq1;
//顯示指定Greater->建大堆
	ZL::priority_queue<int, vector<int>, Greater<int>> pq2;
	pq1.push(100);
	pq1.push(5);
	pq1.push(200);
	pq1.push(10);
	while (!pq1.empty()) {
		cout << pq1.top() << " ";
		pq1.pop();
	}
	return 0;
}

template<class T, class Compare>
void BubbleSort(T* a, int n, Compare com) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            if (com(a[j + 1], a[j]))   // 比較規(guī)則由仿函數(shù)決定
                swap(a[j], a[j + 1]);
        }
    }
}
int main() {
	int a[] = { 1,3,4,5,6,3,2 };
	//讓類可以像函數(shù)一樣調用
	BubbleSort(a, 7, Less<int>());//排升序
	BubbleSort(a, 7, Greater<int>());//排降序
	for (auto ch : a) {
		cout << ch;//自動迭代不用++
	}
	cout << endl;
}

struct OP1 {
	bool operator()(int x) {
		return x % 2 == 0;
	}
};
int main() {
	int a[] = { 1,3,2,9,1,3,4,5 };
	//查找第一個偶數(shù)
	auto it = find_if(a, a + 7, OP1());
	cout << *it << endl
	return 0;
}

struct OP2 {
		int operator()(int x) {
			if (x % 2 == 0)
				return x * 2;
			else
				return x;
		}

};
int main() {
	//transform 是 C++ 標準庫中的一個算法，用于對容器中的每個元素執(zhí)行某種操作，并將結果存儲到另一個位置。
	//它屬于 <algorithm> 頭文件。
	transform(v.begin(), v.end(), v.begin(), OP2());
	for (auto& e : v) {
		cout << e << " ";
	}
	cout << endl;
	return 0;
}

//struct PDateLess
//{
//	bool operator()(const Date* p1, const Date* p2)//仿函數(shù)
//	{
//	return *p1 < *p2;//這里能直接對存儲地址解引用對比出誰的日期大是因為
//在日期結構體中對<運算符進行了重載
//	}
int main() {
	ZL::priority_queue<Date*, vector<Date*>, PDateLess> q1;
	q1.push(new Date(2018, 10, 29));
	q1.push(new Date(2018, 10, 28));
	q1.push(new Date(2018, 10, 30));
	while (!q1.empty()) {
		cout << *q1.top() << " ";
		q1.pop();
	}
	cout << endl;
	return 0;
}