版本 7c653bee685c6d3f89a4d610614e477025ed0b23
Changes from 7c653bee685c6d3f89a4d610614e477025ed0b23 to current
Week 4: STL
===========
STL(Standard Template Library, 標準函式庫)
-------------------------
說明：
是一個C++軟體庫，也是C++標準程式庫的一部分，其中包含4個元件，分別為演算法、容器、函式、迭代器。
##lower/upper_bound
* 利用STL完成Binary Search
* 需引入 algorithm 函式庫
* 使用對象需是已經 `sort` 的array
* lower_bound(array, array+N, a)：回傳array中value `>=` a 的index
upper_bound(array, array+N, a)：回傳array中value `>` a 的index
```c++
#include <cstdio>
#include <algorithm>
using namespace std;
int main() {
int array[] = {6, 13, 14, 25, 33, 43, 51, 53, 64, 72, 84, 93, 95, 96, 97};
printf("%d\n", lower_bound(array, array + 15, 34) - array - 1);
return 0;
}
```
##pair/tuple
* pair: (x, y)
* tuple: (x1, x2, …, xn), **`需在 C++11 環境下使用`**
* 範例
`pair<string, int> data = make_pair("吳勃興", 0)`
`tuple<string, string, string, string, int> = make_tuple("吳勃興", "帥哥", "卷哥", "夯哥", 100)`
##priority_queue
* 說明：有別於一般的 queue，每一個 element 都額外帶有優先值，愈優先的 (一般來說是優先值愈低的) 放在愈前面。
* 特性：
1. 底層以 Binary Heap 實作
2. 是一棵 Complete Binary Tree
3. 滿足 Heap 的條件
* 類別：
Min-Heap: 父節點的值總是小於或等於任何一個子節點的值
: <br />
Max-Heap: 父節點的值總是大於或等於任何一個子節點的值
: <br />
* 時間複雜度：
+ Insertion: O(lgn)
+ Removal: O(lgn)
* 用法：
+ 宣告：
+ 實作Max-Heap： `priority_queue<int> prique`
+ 實作Min-Heap： `priority_queue<int, vector<int>, greater<int> > prique`
+ 原型：`template <class T, class Container = vector<T>, class Compare = less<typename Container::value_type> > class priority_queue;`
+ 用法：常用operator有 **`empty()、size()、front()、push_back()、pop_back()`** ，呼叫方式與queue相似
##struct比較
* 原理：使用運算子重載
* 應用於 sort, priority_queue, lower/upper_bound
```c++
/*寫法一*/
struct _DATA {
int data1, data2;
char data3;
bool operator<(const struct _DATA &rhs) const {
return data1 < rhs.data1;
}
};
```
```c++
/*寫法二*/
struct _DATA {
int data1, data2;
char data3;
bool operator<(const int val) const {
return data1 < val;
}
};
```
