分享到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;
	}
};