分享到plurk 分享到twitter 分享到facebook

acm/course/STL

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

#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: 父節點的值總是小於或等於任何一個子節點的值


Max-Heap: 父節點的值總是大於或等於任何一個子節點的值


  • 時間複雜度:
    • 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

/*寫法一*/
struct _DATA {
	int data1, data2;
	char data3;

	bool operator<(const struct _DATA &rhs) const {
		return data1 < rhs.data1;
	}
};
/*寫法二*/
struct _DATA {
	int data1, data2;
	char data3;

	bool operator<(const int val) const {
		return data1 < val;
	}
};