title: class: center, middle ## Introduction To STL --- ## Overview - Containers - vector - set - map - algorithm - stringstream --- ## Containers - 容器 - 儲存資料的方式 - Array - Linked-List - Tree - Hash Table - 操作資料的方式 - 新增到(開頭, 結尾) - push, pop - 移除特定元素 - 移除(開頭, 結尾) --- ### 操作複雜度  Ref: http://bigocheatsheet.com/ --- ### Iterator - 所有 Container 都會有的基本功能 - 類似指標，指出特定位置 - begin, end (第一個，最後一個) - 終止條件一定要用 __!=__ ```c++ vector<int> arr(3,4); for( vector<int>::iterator it = arr.begin() ; it != arr.end() ; ++it ) cout << (*it) << endl; ``` ```bash 4 4 4 ``` --- ### 容器內建函式 ```c++ vec.size(); //取得長度 vec.empty(); // 測試是否為空 vec.clear(); // 清空 ``` --- ### Vector - 動態 Array - 可以取代 __new, delete__ or __malloc, free__ - 新增/移除最後一個元素的速度快 --- ### Vector 宣告 ```c++ #include <vector> using namespace std; int main() { vector<int> arrS; // 空的vector vector<int> arrZ(3,4); // 3 個 4 vector<char> arrK(5, 'c'); // 5 個 'c' vector<int> arrJ(arrZ); // 複製別的vector int arr[3] = {1, 2, 3}; vector<int> arrG(arr, arr+3); // 複製一個array return 0; } ``` --- ### Vector 走訪 rbegin以相反的方向，從最後一個元素走到第一個 ```c++ int arr[5] = {1, 2, 3, 4, 5}; vector<int> vec(arr, arr+5); for( vector<int>::iterator it = vec.begin() ; it != vec.end() ; ++it ) cout << (*it) << endl; for( vector<int>::iterator it = vec.rbegin() ; it != vec.rend() ; ++it ) cout << (*it) << endl; for( int i = 0; i < vec.size(); ++i ) { cout << vec[i] << endl; } ``` __Wrong Case:__ Containers被__新增__或__移除__後，Iterator就會失效，可能導致程式崩潰 ```c++ for( vector<int>::iterator it = vec.begin() ; it != vec.end() ; ++it ) { if( *it == 3 ) { vec.insert( it, 50 ); // 不能在走訪過程中插入元素 } } ``` --- ### Vector 常用操作 ```c++ vector<int> vec(5, 6); // 6 6 6 6 6 vec.push_back(7); // 6 6 6 6 6 7 插入一個元素到最後面 int n = vec.back(); // n = 7 只是讀取 並未刪除 vec.pop_back(); // 6 6 6 6 6 移除最後一個元素 vec.insert(vec.begin(), 4); // 4 6 6 6 6 6 插入在該iterator的前面 vec.erase(vec.begin()+1); // 4 6 6 6 6 刪除該iterator ``` - front 是第一個元素、 back 是最後一個元素 - begin 是第一個元素的__位址__、 end是在back之後的元素  --- ### Vector 效能訣竅 - `arr.reserve(100)` 預先配置你最多可能會用到的空間 --- ### Exercise 寫一程式，讀取數個數字，並忽略最大和最小的數字後，計算其平均值和中位數。 Input: 每行一個數字，數字大小介於-1e8~+1e8，當讀到0代表輸入結束 ```bash -199 300 400 600 1000 0 ``` Output: ```bash 平均值: 433.33 中位數: 400 ``` --- ## Set - 集合 - 對於已有的元素會自動忽略 - 只能新增刪除，不能修改 --- ### Set 走訪 ```c++ set<string> S; S.insert("foo"); S.insert("bar"); S.insert("zebra"); S.insert("alpha"); for(set<string>::iterator it = S.begin(); it != S.end(); ++it) cout << (*it) << endl; ``` ```bash alpha bar foo zebra ``` 走訪時元素是__排序__好的 --- ### Set 操作 Insert ```c++ pair< set<int>::iterator ,bool> ret; ret = myset.insert(20); if (ret.second==false) puts("Insert failed, duplicated element."); ``` Erase ```c++ S.erase(S.begin()); S.erase("foo"); // 回傳被移除的元素數量 ``` Find ```c++ set<string>::iterator it = S.find("foo"); if(it == S.end()) puts("Element [foo] not found"); ``` --- ### Set 自訂 Compare ```c++ #include <iostream> #include <set> using namespace std; struct C { bool operator()(const string &a, const string &b) const { return b < a; } }; int main() { set<string, C> S; S.insert("foo"); S.insert("foo"); S.insert("fooo"); S.insert("bar"); S.insert("zebra"); S.insert("alpha"); for(set<string>::iterator it = S.begin(); it != S.end(); ++it) cout << (*it) << endl; return 0; } ``` --- ### 補充 - multiset - implemented as _binary search trees_ - 允許重複的值 - unordered_set - c++11 only - faster than set - Hash Table - unordered --- ### Exercise 寫一程式，輸入一篇文章，輸出出現過的單字集合，不得重複輸出同樣的單字 Input: 單字間以空白分隔，每個單字只會有大小寫英文字母，讀到EOF結束 ```bash alpha foo fooo zebra ``` Output: 每行一個單字，以單字長度大到小排序，如果長度相同，則以alphabetical order排序 ```bash alphz zebra fooo foo ``` --- ## Map - Python 中的 Dicts, PHP 中的 Array - 不同於陣列是用數字當index - Map 可以用字串當index ```c++ table["name"] = "John Doe"; table["age"] = "130"; if( table["age"] == "130" ) puts("Q_Q"); ``` --- ### Map 宣告 ```c++ map<string, string> table; ``` ```c++ map<string, string>::iterator it = table.begin(); // how to use? pair<string, string> p("age", "130"); ``` .center[] --- ### Map 走訪 ```c++ for(map<string, string>::iterator it = table.begin(); it != table.end(); ++it) { cout << "table[" << (it->first) << "] = " << (it->second) << endl; } ``` - table[key] = value - first => key - second => value --- ### Map 的 [] 運算子 - 可以讀取也可以寫入 - `if(table["age"] == "130")puts("Q_Q");` - 當table["age"]不存在會發生甚麼事? - 如果存在，會回傳value - 如果不存在，會__自動新增__這個value並回傳 - 要拿來進行條件判斷時，需要先用find找出這個元素，或用走訪的方式 --- find ```c++ map<string, string>::iterator it; it = table.find("age"); if(it != table.end() && it->second == "130") puts("Q_Q"); ``` insert - 新增元素前先檢查是否已經存在該key ```c++ pair<map<string, string>::iterator, bool> ret; ret = table.insert( pair<string, string>("age", "50") ); if(ret.second == false) { puts("key exists"); } ``` erase ```c++ table.erase(table.begin()); table.erase("age"); ``` --- ## Exercise 有一個Linked-List，我們只知道每個元素接下來的元素是甚麼，保證每個元素都不會重複，找出第一個和最後一個元素 Input: 第一個值為某元素，第二個值為該元素接下去的元素 ```bash b -> a c -> b a -> e g -> c ``` Output: ```bash head element: g last element: e ``` --- ## Algorithm 搭配begin, end作使用，成功回傳iterator，沒找到回傳end ```c++ #include <algorithm> find(arr.begin(), arr.end(), 30); sort(arr.begin(), arr.end()); binary_search(arr.begin(), arr.end(), 30); // sorted array ``` 直接回傳結果 ```c++ max(5,3); min(3,6); count(arr.begin(), arr.end(), 30); ``` 無回傳值 ```c++ replace(arr.begin(), arr.end(), 100, -1); reverse(arr.begin(), arr.end()); ``` --- ### permutation ```c++ int myints[] = {1,2,3}; do { cout << myints[0] << ' ' << myints[1] << ' ' << myints[2] << '\n'; } while ( next_permutation(myints,myints+3) ); cout << "After loop: " << myints[0] << ' ' << myints[1] << ' ' << myints[2]; ``` --- ## sstream 把字串當cin或cout來使用 ```c++ #include <sstream> string line = "xnum 123 456 0.5"; stringstream ss(line); string name; int a, b; double d; ss >> name >> a >> b >> d; ``` ```c++ stringstream ss; ss << name << "[" << a << "," << b << "]" << " / " << d; cout << ss.str() << endl; ``` --- ## 組合使用 時間日期讀取 ```c++ string input = "2017/5/15 17:59 AM"; replace(input.begin(), input.end(), '/', ' '); replace(input.begin(), input.end(), ':', ' '); stringstream ss(input); ss >> y >> m >> d >> hour >> min >> am; ``` --- ## Exercise 給你一個Matrix，算出每個column的總和 Input: ```bash [1, 2, 1, 3] [4, 3, 2, 3] [5, 5, 1, 3] ``` Output: ```bash [10, 10, 4, 9] ```