Programming

程式碼 static final int hash(Object key){ int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } h » 16 的用途 h是key.hashCode()，h >>> 16代表的是取其高位的16位 key.hashCode() ^ (h » 16) 這與 Java1.8 中 tab[(n-1) & hash] 的原理有關 static int indexFor(int h, int length){ return h & (length - 1); } 返回的值即為陣列的下標。 大多數情況下，capacity 都小於2^16，所以在此的 & 運算，只會對 h 的低16位進行 & 運算。 若將高位16位也加入計算，可以增加下標的發散度，避免衝突的次數。 而使用 XOR 的原因是，更較於 AND 或 OR 均勻，因為 AND 會使結果趨向於 0，OR 會使結果趨向於 1。

C++ 易錯題目收集 1. bit-format expression #include <bits/stdc++.h> using namespace std; int main(){ unsigned int x = -1; int y = ~0; if (x==y) cout << "same"; else cout << "not same"; return 0; } 結果 same 解析 unsigned int x = -1 相當於11111111 y = ~0 也相當於11111111 2. 如何使 C(n,3) 正確且 n 的有效值最大? 結果 return n*(n-1)/2*(n-2)/3; 解析 n*(n-1)必為基偶相乘 n*(n-1)*(n-2)必為3的倍數 故此題的作法可避免因整數除法而造成的小數位消去 3. register在C++中的用法 #include <bits/stdc++.h> using namespace std; int main(){ register int i = 10; int *ptr = &i; cout << *ptr; return 0; } 選項 Prints 10 on all compilers Prints 0 on all compilers May generate Compilation Error May generate Runtime Error 結果 May generate Compilation Error 解析 register關鍵字用來分配變數儲存於CPU的register，以達到快速存取。所以對其提取有可能造成編譯錯誤，因為指標指向的位址不在在RAM上。 在大部分的C++編譯器，不推薦使用register關鍵字，因為沒有任何意義，儘管他會被默認成auto關鍵字，使得C++編譯器可能可能適用。 4. 有趣的 for loop 問題 int fun(){ static int num = 16; return num--; } int main(){ for(fun(); fun(); fun()) cout << fun(); return 0; } 結果 14 11 8 5 2 解析 main()中的 for-loop 可以寫成等效的 while-loop 如下 int main(){ int num = 16; num--; // num = 15 while (num-- != 0){ // 先判斷後遞減 15 !=0, num = 14 cout << (num--) << " "; // 先印出後遞減印出 14, num = 13 num--; // 遞減後回到while, num = 12 } return 0; } static int num = 16 設定初值為 16，並遞減，故 num = 15 判斷 num 是否為真，後遞減。15 != 0，遞減使 num = 14，進入迴圈 印出 num = 14 後，遞減，num = 13 迴圈結束前作遞減，num = 12，重新回到 step2 5. const 與 volatile Pick the correct statemewnt for const and volatile keywords. 選項 const is the opposite of volatile and vice versa const and volatile can’t be used for struct and union const and volatile can’t be used for enum const and volatile can’t be used for typedef const and volatile are independent i.e. it’s possible that a variable is defined as both const and volatile 結果 const and volatile are independent i.e. it's possible that a variable is defined as both const and volatile 解析 const 是確保變數不會變修改，使其值變成唯讀。 volatile 通常用在具有最佳化或多執行緒相關的變數或物件，volatile用來阻止編譯器因誤認某段程式碼無法被程式碼本身所改變，而造成的過度優化。volatile會使得每次存取這個變數或物件時，都會直接從變數位址中取得資料，避免可能使用暫存器中的值，在變數可能被其他程式更新的狀況下，產生錯誤的值。 6. operator priority int main(){ cout << (1 << 2 + 3 << 4); return 0 } 結果 512 解析 +優先於<< 故此段敘述等效於 cout << (1 << (2 + 3) << 4); cout << (1 << 5 << 4); cout << (32 << 4); cout << 512; 7. floating constant Suppose a C++ program has floating constant 1.414, what's the best way to convert this as "float" data type? 選項 (float)1.414 float(1.414) 1.414f or 1.414F 1.414 itself of “float” data type i.e. nothing else required 結果 `1.414f` or `1.414F` 解析 floating constant 被預設為 double 資料型態，故利用f或F的suffix，即可將之轉為 float 資料型態。 8. array pointer int main(){ int arr[5]; // Assume base address of arr is 2000 and size of integer is 32 bit printf(%u %u, arr+1, &arr+1); return 0; } 結果 2004 2020 解析 array 的名稱會傳回第一個元素的地址(除了使用 sizeof)。 對 array 加 1 會加上 sizeof(type)。 &array 代表整個 array 的地址，加 1 回加上 sizeof(while array)。 9. initialize array int main(){ int a[][] = {{1,2},{3,4}}; int i, j; for (int i = 0; i < 2; i++){ for (int j = 0; j < 2; j++){ printf("%d ", a[i][j]); } } return 0; } 結果 Compilation Error 解析 Array 在記憶體中是以row-major的型式儲存的。 儘管 array 是多維陣列，他都是被儲存成單一線性的區塊 下列 assign 的方式是合法的，(第一個可被省略) int a[] = {...}; int a[][10] = {{...}, ...}; int a[][5][10] = {{{...},...},...};

list Lists 是序列式容器，但其記憶體的分配並非連續的。 跟 vector 相比，其遍歷的速度會較慢\(O(n)\，但一旦位置確定後，其插入(insert)或移除(delete)元素的速度很快\(O(1)\)。 一般來說，List 指的是雙向鏈結陣列(doubly linked list)。 而單向鏈結陣列則為 forward_list 函式庫 #include <list> 宣告 list<data_type> list_name; 初始化 list<int> lst; // 宣告 函式 1. front() 2. back() 3. push_front() 4. push_back() 5. pop_front() 6. pop_back() 7. list::begin() 8. list::end() 9. list::rbegin() 10. list::rend() 11. list::cbegin() 12. list::cend() 13. list::crbegin() 14. list::crend() 15. empty() 16. insert() 17. erase() 18. assign() 19. remove() 20. list::remove_if() 21. reverse() 22. size() 23. list::resize() 24. sort() 25. list::max_size() 26. list::unique() 27. list::emplace_front() 28. list::emplace_back() 29. list::clear() 30. list::operator= 31. list::swap() 32. list::splice() 33. list::merge()4 34. list::emplace() 示例 #include <iostream> #include <iterator> #include <list> using namespace std; void print(list<int> lst){ list<int>::iterator it; for (it = lst.begin(); it != lst.end(); ++it){ cout << *it << " "; } cout << "\n"; } int main(){ list<int> lst1, lst2; for (int i = 0; i < 10; ++i){ lst1.push_back(i); lst2.push_front(i); } cout << "List1 is : "; print(lst1); cout << "List2 is : "; print(lst2); cout << "List1.front() : " << lst1.front() << "\n"; cout << "List2.back() : " << lst2.back() << "\n"; cout << "After List1.pop_front() : "; lst1.pop_front(); print(lst1); cout << "After List2.pop_back() : "; lst2.pop_back(); print(lst2); cout << "After List1.reverse() : "; lst1.reverse(); print(lst1); cout << "After List2.sort() : "; lst2.sort(); print(lst2); return 0; } 函式(functions) 1. list.front() Returns the value of the first element in the list. 2. list.back() Returns the value of the last element in the list. 3. list.push_front(E val) Adds a new element val at the beginning of the list. 4. list.push_back(E val) Adds a new element val at the end of the list. 5. list.pop_front() Removes the first element of the list, and reduces size of the list by 1. Won’t return value. 6. list.pop_back() Removes the last element of the list, and reduces size of the list by 1. Won’t return value. 7. list.begin() Returns a iterator pointing to the first element of the list. 6. list.end() Returns a iterator pointing to the theoretical last element which follows the last element. 7. list.rbegin() Returns a reverse iterator which points to the last element of the list. 8. list.rend() Returns a reverse iterator which points to the position before the beginning of the list. 9. list.cbegin() Returns a constant random access iterator which points to the beginning of the list. 10. list.cend() Returns a constant random access iterator which points to the end of the list. 11. list.crbegin() Returns a constant reverse random access iterator which points to the beginning of the list. 12. list.crend() Returns a constant reverse random access iterator which points to the end of the list. 13. list.empty() Returns whether the list is empty or not. 14. list.insert(pos, n, val) pos: iterator, to point out the position to insert n: the numbers of val to insert (optional, default = 1) val: the insert elements Inserts new elements in the list before the element at a specified position. 15. list.erase(pos) pos: iterator, to point out the position to erase Removes a single element from the list. 16. list.erase(first, last) first: iterator, to point out the begining of the range. last: iterator, to point out the end of the range. Removes a range of elements from the list. 17. list.assign() 18. list.remove() 19. list.remove_if() 20. list.reverse() 21. list.size() 22. list.resize() 23. list.sort() 24. list.max_size() 25. list.unique() 26. list.emplace_front() 27. list.emplace_back() 28. list.clear() 29. list.swap() 30. list.splice() 31. list.merge() 32. list.emplace() 你可能會想繼續閱讀… 回到容器(Containers) vector deque arrays forward_list

vector Vectors 是一動態陣列，可以自動的調整其容器的容量。 Vector 的元素被儲存在連續的記憶體空間，所以可以使用迭代器(iterators)來進行存取。 在 vectors 中，元素是被插入在尾端的，插入尾端的時間取決於是否須進行容量的調整。 在 vectors 中，刪除尾端元素的時間複雜度則是固定的\(O(1)\)，因為不會發生容量調整。 在 vectors 的前端或中間插入元素或是清除元素，時間的複雜度都是\(O(n)\)。 迭代器(Iterators) 1. vec.begin() 回傳指向 vector 中第一個元素的迭代器 (vec[0]) 2. vec.end() 回傳指向 vector 中最後一個元素之後一個的迭代器 (vec[n+1]) 3. vec.rbegin() 回傳指向 vector 中最後一個元素的反向迭代器 (vec[n]) 4. vec.rend() 回傳指向 vector 中第一個元素之前一個的反向迭代器 (vec[-1]) 5. vec.cbegin() 回傳指向 vector 中第一個元素的常數迭代器 (vec[0]) 6. vec.cend() 回傳指向 vector 中最後一個元素之後一個的常數迭代器 (vec[n+1]) 7. vec.crbegin() 回傳指向 vector 中最後一個元素的反向常數迭代器 (vec[n]) 8. vec.crend() 回傳指向 vector 中第一個元素之前一個的反向常數迭代器 (vec[-1]) #include <bits/stdc++.h> using namespace std; int main(){ int arr[] = {1,1,2,3,5,8,13,21,34,55}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // initialize with array cout << "Output of begin() and end(): "; for (auto i = vec.begin(); i != vec.end(); ++i) cout << *i << " "; cout << "\nOutput of rbegin() and rend(): "; for (auto i = vec.rbegin(); i != vec.rend(); ++i) cout << *i << " "; cout << "\nOutput of cbegin() and cend(): "; for (auto i = vec.cbegin(); i != vec.cend(); ++i) cout << *i << " "; cout << "\nOutput of crbegin() and crend(): "; for (auto i = vec.crbegin(); i != vec.crend(); ++i) cout << *i << " "; return 0; } 結果： ...

容器(Containers) C++ container 基本上分為四大類： Sequence containers Container adaptors Associative containers Unordered associative containers 還有兩個特殊 containers: valarray, bitset \(\begin{array}{|l|l|l|l|l|l|}\hline \text{Name}&\text{Iterators}&\text{Capacity}&\text{Access}&\text{Modifiers}&\text{Others} \\\hline \text{array}&\text{begin}&\text{size}&\text{[]}&\text{swap} \\&\text{end}&\text{empty}&\text{at} \\&&&\text{front} \\&&&\text{back} \\\hline \text{vector}&\text{begin}&\text{size}&\text{[]}&\text{push\_back}&\text{} \\&\text{end}&\text{empty}&\text{at}&\text{pop\_back} \\&&\text{capacity}&\text{front}&\text{insert} \\&&&\text{back}&\text{erase} \\&&&&\text{swap} \\&&&&\text{clear} \\\hline \text{deque}&\text{begin}&\text{size}&\text{[]}&\text{push\_back}&\text{} \\&\text{end}&\text{empty}&\text{at}&\text{pop\_back} \\&&&\text{front}&\text{insert} \\&&&\text{back}&\text{erase} \\&&&&\text{swap} \\&&&&\text{clear} \\\hline \text{list}&\text{begin}&\text{size}&\text{front}&\text{push\_back}&\text{sort} \\&\text{end}&\text{empty}&\text{back}&\text{pop\_back}&\text{reverse} \\&&&&\text{insert} \\&&&&\text{erase} \\&&&&\text{swap} \\&&&&\text{clear} \\\hline \text{forward\_list}&\text{begin}&\text{empty}&\text{front}&\text{push\_front}&\text{sort} \\&\text{end}&&&\text{pop\_back}&\text{reverse} \\&&&&\text{insert\_after} \\&&&&\text{erase\_after} \\&&&&\text{swap} \\&&&&\text{clear} \\\hline \end{array} \) 基礎容器 pair 序列式容器(Sequence Containers) 特點是不會對儲存的元素進行排序，元素排列的順序取決於儲存的順序。 vector list, forward_list deque arrays 容器適配器(Container Adaptors) 用於封裝序列容器的類模板，在一般的序列容器的基礎上提供一些不同的功能，通過實現適配器的介面來提供不同的功能。 queue priority_queue stack 關聯性容器(Associative Containers) 又名 Map、Dictionary，是一種抽象的資料結構，包含著類似於(key, value)的有序對(entry)。 一個關聯陣列中的有序對(entry)可以重複(如multimap)，也可以不重複(map)。 利用雜湊表(Hash Table)或搜尋樹(search tree)實現，有些情況下，有可以使用直接定址的陣列、二元搜尋樹或其他專門的結構。 set multiset map multimap 無序關聯容器(Unordered Associative Containers(C++11)) 通過雜湊表(Hash Table)實現的資料結構。 無序是指元素的名字(或者鍵值)的儲存是無序的；這與用平衡二元樹實現的有序的關聯性容器是相對概念。 unordered_set unordered_multiset unordered_map unordered_mutlimap 你可能會想繼續閱讀… 演算法(Algorithms) 函式(Functions) 迭代器(Iterators) Utility Library

前言 在做 WAT 量測後的資料處理時，IDAS 老舊的 VBA macro 執行時間實在過於久，且佔用大量的記憶體，於是就下了一個命題，想減少產生報表的時間。 想法 通常量測多片 wafer 的狀況下，不同 wafer 的排列順序是一致的，如果可以加入 Java 中 HashMap 的資料結構來處理 VBA 中 Lookup()，便可大幅減少 summary table 時，對 rawdata 做搜尋的時間。 令時間複雜度從\(O(n)\)進步到\(O(1)\)。 做法 產生 Dictionary 物件 由於 VBA 預設並沒有 Dictionary 的物，所以需要用 CreateObject("Scritping.Dictionary") 的程式碼，引入 Dictionary。 其 Dictionary 物件的 method 可參考 Microsoft 的文件：點此 在此先預先定義一個 function setDict() 可以對初始化 Dictionary。 接著宣告兩個 Dictionary 物件來存取 spec 和 data 工作頁的列數(row)。 Dim SpecDict As Object ' Claim a dict to store spec rows in worksheet SPEC. Dim DataDict As Object ' Claim a dict to store rawdata rows in worksheet Data. Set SpecDict = CreateObject("Scripting.Dictionary") Set DataDict = CreateObject("Scripting.Dictionary") Call setDict("SPEC", 3, SpecDict, Worksheets("SPEC").UsedRange, True) Call setDict("Data", 2, DataDict, Range(Worksheets("Data").Names(1)), True) 實作 setDict() 函數 利用 HashTable 的概念對不同的 parameter 列數先做一次記錄，因為只需一次迴圈，故時間複雜度是 \(O(n)\)，其中 n = SPEC 的列數 或是 量測的 parameter 數。 在此設計了五個 arguments，方便在未來如果還有使用到 Dictionary 的需求時，可以方便使用。 sheetName 字串，需要作儲存的工作頁(worksheet)。 Target 要儲存的列數(row)或欄數(column)。 Dict 要存放的 Dictionary 物件。 mRange 要做儲存的資料範圍，若表頭並是在第一列或第一欄時可指定。 若表頭是第一列或第一欄時，可直接代入 Worksheets("工作頁名稱").UsedRange byRows 看要儲存的對象是列(row)或是欄(column)，預設是以列來搜尋。 Public Function setDict(ByVal sheetName As String, ByVal Target As Integer, ByRef Dict As Object, ByVal mRange As Range, Optional ByVal byRows As Boolean = True) Dim nowSheet As Worksheet If Not IsExistSheet(sheetName) Then Exit Function Set nowSheet = Worksheets(sheetName) Dim i As Long Dim n As Long On Error Resume Next If byRows = True Then For i = 1 To mRange.Rows.Count If Not Trim(mRange.Cells(i, Target).Value) = "" Then Dict.Add mRange.Cells(i, Target).Value, i End If Next i Else For i = 1 To mRange.Columns.Count If Not Trim(mRange.Cells(Target, i).Value) = "" Then Dict.Add mRange.Cells(Target, i).Value, i End If Next i End If End Function 對 getSPECByPara() 做重製 將 parameter or SPEC 做 hashing 的處理後，可以用 Dictionary 物件來查值，時間複雜度為 \(O(1)\)。 在此不對原本的設計做更動，只做單純的 implement。 nowPara 要搜尋的 parameter 字串。 n 要搜尋的欄數(column)，specColumn是原作者預設的 enum，存放工作頁 SPEC 的每一欄的表頭。 sheetName 要搜尋的工作頁，預設為 SPECTEMP，是按完 initial，從 SPEC 工作頁複製出來的隱藏工作頁。 Public Function getSPECByPara(ByVal nowPara As String, ByVal n As specColumn, Optional sheetName As String = "SPECTEMP") Dim reValue Dim nowRange As Range Dim TargetSheet As Worksheet If Left(nowPara, 1) = "'" Then nowPara = Mid(nowPara, 2) Set TargetSheet = Worksheets(sheetName) Set nowRange = TargetSheet.UsedRange On Error Resume Next reValue = TargetSheet.Cells(SpecDict(nowPara), n) If Not IsEmpty(reValue) Then If Trim(reValue) = "" Then Set reValue = Nothing End If getSPECByPara = reValue End Function 對 getRangeByPara() 做重製 將 parameter or SPEC 做 hashing 的處理後，可以用 Dictionary 物件來查值，時間複雜度為 \(O(1)\)。 Public Function getRangeByPara(nowWafer As String, nowPara As String, Optional dieNum As Integer = 0) Dim nowRow As Long Dim nowRange As Range Set nowRange = Worksheets("Data").Range("wafer_" & nowWafer) Set getRangeByPara = Nothing If DataDict.Exists(nowPara) Then nowRow = DataDict(nowPara) Set getRangeByPara = nowRange.Range(N2L(4) & CStr(nowRow) & ":" & N2L(dieNum + 3) & CStr(nowRow)) End If End Function 解析 優點：較快的執行速度。經測試可以將 2~3 分鐘的執行時間縮短到 30 秒內。 缺點：若修改 rawdata，會發生錯誤。但若針對每一片 wafer 都做 setDict()的話，會浪費太多 memory。

rand() 函數 在 C/C++ 中可以使用 rand() 這個函數，產生最簡單的亂數： 需引用 <stdlib.h> 函式庫 在呼叫 rand() 前需要先使用srand()設定初始的亂數種子，增加「亂度」。(實際上產生的亂數是有規則的，以示例為例，是以時間做為種子，故是有可能被預測的) 其產生的亂數是一個介於 0 到 RAND_MAX(INT_MAX)的整數。 C 與 C++ 幾乎一樣，只差在表頭檔的使用。 C-style #include <stdio.h> #include <stdlib.h> #include <time.h> int main(){ srand(time(NULL)); // random seed int x = rand(); printf("x = %d\n", x); return 0; } Cpp-style #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main(){ srand(time(NULL)); int x = rand(); cout << "x = " << x << endl; cout << "x is between 0 and " << RAND_MAX << endl; return 0; } 亂數種子 由於電腦實際上並沒有辦法自己產生「真正的亂數」，只能透過複雜的數學演算法模擬出類似亂數的數值資料，而在模擬亂數時，需要設定一個亂數種子，電腦會根據這個亂數種子來計算出一連串的亂數，相同的亂數種子就會產生相同的亂數序列，所以如果要讓產生的亂數每次都不同，就要設定不同的亂數種子。 上例中使用的亂數種子是時間，因為時間每分每秒都在變化，所以每次產生的亂數都會不同，如果是用於數值模擬的話， 固定亂數種子 由於電腦實際上並沒有辦法自己產生「真正的亂數」，只能透過複雜的數學演算法模擬出類似亂數的數值資料，而在模擬亂數時，需要設定一個亂數種子，電腦會根據這個亂數種子來計算出一連串的亂數，相同的亂數種子就會產生相同的亂數序列，所以如果要讓產生的亂數每次都不同，就要設定不同的亂數種子。若是做數值模擬的話，通常會讓模擬結果具有可重復性(repeatability)，方便除錯與驗證，這種狀況就可以將亂數種子固定不變，以確保每次的結果都相同。 [0, 1) 浮點數亂數 [0, 1) 代表 0 <= x < 1 若要產生 0 到 1 之間的浮點數亂數，可以這樣寫： #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main(){ srand(time(NULL)); double x = (double)rand()/(RAND_MAX + 1.0); cout << "x = " << x << endl; return 0; } [a, b)特定範圍浮點數亂數 [a, b) 表 a <= x < b #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main(){ srand(time(NULL)); double x = (double)rand()/(RAND_MAX + 1.0); cout << "x = " << x << endl; return 0; } [a, b)特定範圍整數亂數 #include <iostream> #include <cstdlib> #include <ctime> using namespace std; int main(){ srand(time(NULL)); int a = 1; // min int b = 100; // max int x = rand() % (b - a + 1) + a; cout << "x = " << x << endl; return 0; } 上面這種使用餘數運算（%）的方式只是比較方便的寫法，事實上使用餘數運算所產生的整數亂數在理論上不是標準的均勻分布。 ...

cout Functions 設定顯示小數點位數 setprecision(int n) and fixed #include <iostream> #include <iomanip> using namespace std; int main(){ double a = 5.43/2.653; cout << a << endl; // 2.04674 cout << setprecision(3) << fixed; cout << a << endl; // 2.047 return 0; } 顯示 Boolean 值 std::boolalpha #include <iostream> using namespace std; int main(){ bool a = true; cout << a << endl; // 1 cout << std::boolalpha; cout << a << endl; // true return 0; }

演算法(Algorithms) Non-Manupulating Algorithms 1. sort() sort(first_iterator, last_iterator) 對 vector 作排序 2. reverse() reverse(first_iterator, last_iterator) 反轉 vector 的排序 3. *max_element() *max_element(first_iterator, last_iterator) 找出 vector 的最大值 4. *min_element() *min_element(first_iterator, last_iterator)` 找出 vector 的最小值 5. accumulate accumulate(first_iterator, last_iterator, initial value of sum) 計算 vector 的總和 #include <iostream> #include <algorithm> #include <vector> #include <numeric> using namespace std; void print(vector<int>& vec){ for (vector<int>::iterator it = vec.begin(); it != vec.end(); it++){ cout << *it << " "; } cout << endl; } int main(){ int arr[] = {10, 20, 5, 23, 42, 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // print initial vector print(vec); // [10, 20, 5, 23, 42, 15] // sort sort(vec.begin(), vec.end()); // [5, 10, 15, 20, 23, 42] print(vec); // reverse reverse(vec.begin(), vec.end()); // [42, 23, 20, 15, 10, 5] print(vec); // max & min cout << *max_element(vec.begin(), vec.end()) << endl; // 42 cout << *min_element(vec.begin(), vec.end()) << endl; // 5 // accumulate cout << accumulate(vec.begin(), vec.end(), 0) << endl; // 115 return 0; } 6. count() count(first_iterator, last_iterator, x) 計算 vector 中 x 的數量 7. find() find(fist_iterator, last_iterator, x) 回傳 vector 中第一個符合的 iterator，若無則傳回 v.end()。 #include <algorithm> #include <iostream> #include <vector> using namespace std; int main() { int arr[] = {10, 20, 5, 23 ,42, 20, 15}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); cout << count(vec.begin(), vec.end(), 20); // 2 find(vec.begin(), vec.end(),5) != vec.end() ? // Element found cout << "\nElement found": cout << "\nElement not found"; return 0; } 8. binary_search() binary_search(first_iterator, last_iterator, x) 測試 x 是否存在已排序的 vector 中 9. lower_bound() lower_bound(first_iterator, last_iterator, x) 傳回指向不大於 x 的元素的 iterator 10. upper_bound() upper_bound(first_iterator, last_iterator, x) 傳回指向大於 x 的元素的 iterator #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {5, 10, 15, 20, 20, 23, 42, 45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); sort(vec.begin(), vec.end()); cout << binary_search(vec.begin(), vec.end(), 20) << endl; // 1 cout << (lower_bound(vec.begin(), vec.end(), 20) - vec.begin()) << endl; // 3 cout << (upper_bound(vec.begin(), vec.end(), 20) - vec.begin()) << endl; // 5 return 0; } Manipulating Algorithms 1. vec.erase() arr.erase(position_to_be_deleted) 移除指定位置的元素 2. vec.erase(unique()) arr.erase(unique(arr.begin(), arr.end()), arr.end()) 移除已排序的 vector 中重複的元素 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {5, 10, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // [5, 10, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20] vec.erase(vec.begin() + 1); // [5, 15, 20, 20, 23, 42, 45, 20, 20, 20, 20, 20] sort(vec.begin(), vec.end()); // [5, 15, 20, 20, 20, 20, 20, 20, 20, 23, 42, 45] vec.erase(unique(vec.begin(), vec.end()), vec.end()); // [5, 15, 20, 23, 42, 45] return 0; } 3. next_permutation() next_permutation(first_iterator, last_iterator) 對 vector 作動成下一個字典排序 4. prev_permutation() prev_permutation(first_iterator, last_iterator) 對 vector 作動成上一個字典排序 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ int arr[] = {1,2,3,4,5,6,7}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); // [1,2,3,4,5,6,7] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,5,7,6] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,5,7] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,7,5] next_permutation(vec.begin(), vec.end()); // [1,2,3,4,7,5,6] prev_permutation(vec.begin(), vec.end()); // [1,2,3,4,6,7,5] return 0; } 5. distance() distance(first_iterator, last_iterator) #include <iostream> #include <algorithm> #include <vector> #include "print.cc" using namespace std; int main(){ int arr[] = {5,10,15,20,20,23,42,45}; int n = sizeof(arr)/sizeof(arr[0]); vector<int> vec(arr, arr + n); cout << distance(vec.begin(), max_element(vec.begin(), vec.end())) << endl; // 7 // == max_element(vec.begin(), vec.end()) - vec.begin(); return 0; } Array algorithms 1. any_of() any_of(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否有任何元素滿足條件 2. all_of() all(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否有全部元素滿足條件 3 none_of() none_of(first_iterator, last_iterator, [](passing_value { return statement; })) ? if_true : if_false; vector 中是否沒有元素滿足條件 #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ vector<int> vec1 {1,3,7,9,11,17,23}; all_of(vec1.begin(), vec1.end(), [](int x) { return (x & 1) == 1;}) ? cout << "All odds\n" : cout << "Not all odds\n"; vector<int> vec2 {1,3,6,8,9,11,13}; any_of(vec2.begin(), vec2.end(), [](int x) { return (x & 1) == 0;}) ? cout << "There are at least one even\n" : cout << "There are no any even\n"; none_of(vec1.begin(), vec1.end(), [](int x) { return (x & 1) == 0;}) ? cout << "There are no any even\n" : cout << "There are at least one even\n"; return 0; } 4. copy_n() copy_n(source_array, array_size, target_array) 複製陣列 #include <iostream> #include <algorithm> using namespace std; int main(){ int arr[] = {1,2,3,4,5,6}; int arr2[6]; copy_n(arr, 6, arr2); for (int i : arr2){ cout << i << " "; } return 0; } 5. iota() iota(array_name, array_size, starting_number) 逐一增加並寫入指定大小的陣列 // C++ code to demonstrate working of iota() #include<iostream> #include<numeric> // for iota() using namespace std; int main(){ // Initializing array with 0 values int ar[6] = {0}; // Using iota() to assign values iota(ar, ar+6, 20); // Displaying the new array cout << "The new array after assigning values is : "; for (int i=0; i<6 ; i++) cout << ar[i] << " "; return 0; } Partition operations C++ 在標準模板資料庫(STL)中有一個 class 可以來做 partition 的演算法。 Partition 就是用來將容器裡面的元素依指定的條件做分隔。 1. partition() partition(begin, end, conditon) 依照指定條件做分隔。 2. is_partition() is_partitioned(begin, end, condition 判斷元素是否依照條件分開。 #include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ vector<int> vec = {2,1,5,6,8,7}; is_partitioned(vec.begin(), vec.end(), [](int x){ return x % 2 == 0; }) ? cout << "Vector is partitioned": cout << "Vector is not partitioned"; cout << endl; partition(vec.begin(), vec.end(), [](int x){ return x % 2 == 0; }) ? cout << "The partitioned vector is : "; for (int &x : vec) cout << x << " "; return 0; } 3. stable_partition() stable_partition(begin, end, condition) 依指定條件作分隔，同時保留元素的相對位置。 4. partition_point() partition_point(begin, end, condition) 返回指向分隔位置的迭代器，也就是在 [begin, end] 範圍內的第一個元素。 This function returns an iterator pointing to the partition point of container i.e. the first element in the partitioned range [beg,end) for which condition is not true. The container should already be partitioned for this function to work. // C++ code to demonstrate the working of // stable_partition() and partition_point() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // partitioning vector using stable_partition() // in sorted order stable_partition(vect.begin(), vect.end(), [](int x) { return x%2 == 0; }); // Displaying partitioned Vector cout << "The partitioned vector is : "; for (int &x : vect) cout << x << " "; cout << endl; // Declaring iterator vector<int>::iterator it1; // using partition_point() to get ending position of partition auto it = partition_point(vect.begin(), vect.end(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The vector elements returning true for condition are : "; for ( it1= vect.begin(); it1!=it; it1++) cout << *it1 << " "; cout << endl; return 0; } 5. partition_copy() partition_copy(begin, end, begin1, begin2, condition) This function copies the partitioned elements in the different containers mentioned in its arguments. It takes 5 arguments. Beginning and ending position of container, beginning position of new container where elements have to be copied (elements returning true for condition), beginning position of new container where other elements have to be copied (elements returning false for condition) and the condition. Resizing new containers is necessary for this function. // C++ code to demonstrate the working of // partition_copy() #include<iostream> #include<algorithm> // for partition algorithm #include<vector> // for vector using namespace std; int main() { // Initializing vector vector<int> vect = { 2, 1, 5, 6, 8, 7 }; // Declaring vector1 vector<int> vect1; // Declaring vector1 vector<int> vect2; // Resizing vectors to suitable size using count_if() and resize() int n = count_if (vect.begin(), vect.end(), [](int x) { return x%2==0; } ); vect1.resize(n); vect2.resize(vect.size()-n); // Using partition_copy() to copy partitions partition_copy(vect.begin(), vect.end(), vect1.begin(), vect2.begin(), [](int x) { return x%2==0; }); // Displaying partitioned Vector cout << "The elements that return true for condition are : "; for (int &x : vect1) cout << x << " "; cout << endl; // Displaying partitioned Vector cout << "The elements that return false for condition are : "; for (int &x : vect2) cout << x << " "; cout << endl; return 0; } Numeric algorithms 1. apply() apply([](int x){return operation;}) 對陣列所有元素做運算 2. arr.sum() arr.sum() 計算陣列所有元素的總合 // C++ code to demonstrate the working of // apply() and sum() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1 ; // Using apply() to increment all elements by 5 varr1 = varr.apply([](int x){return x=x+5;}); // Displaying new elements value cout << "The new valarray with manipulated values is : "; for (int &x: varr1) cout << x << " "; cout << endl; // Displaying sum of both old and new valarray cout << "The sum of old valarray is : "; cout << varr.sum() << endl; cout << "The sum of new valarray is : "; cout << varr1.sum() << endl; return 0; } 3. arr.min() arr.min() 傳回陣列中最小的元素 4. arr.max() arr.max() 傳回陣列中最大的元素 // C++ code to demonstrate the working of // max() and min() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Displaying largest element of valarray cout << "The largest element of valarray is : "; cout << varr.max() << endl; // Displaying smallest element of valarray cout << "The smallest element of valarray is : "; cout << varr.min() << endl; return 0; } 5. arr.shift() arr.shift(int n) 對陣列做 n 個位的移動，正為向右移，負為向左移，缺位補零。 6. cshift() arr.cshift(int n) 對陣列做 n 個位的移動，正為向右移，負為向左移，缺位使用循環補位。 // C++ code to demonstrate the working of // shift() and cshift() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main() { // Initializing valarray valarray<int> varr = { 10, 2, 20, 1, 30 }; // Declaring new valarray valarray<int> varr1; // using shift() to shift elements to left // shifts valarray by 2 position varr1 = varr.shift(2); // Displaying elements of valarray after shifting cout << "The new valarray after shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; // using cshift() to circulary shift elements to right // rotates valarray by 3 position varr1 = varr.cshift(-3); // Displaying elements of valarray after circular shifting cout << "The new valarray after circular shifting is : "; for ( int&x : varr1) cout << x << " "; cout << endl; return 0; } 7. arr1.swap(arr2) arr1.swap(arr2) 陣列做交換 // C++ code to demonstrate the working of // swap() #include<iostream> #include<valarray> // for valarray functions using namespace std; int main(){ // Initializing 1st valarray valarray<int> varr1 = {1, 2, 3, 4}; // Initializing 2nd valarray valarray<int> varr2 = {2, 4, 6, 8}; // Displaying valarrays before swapping cout << "The contents of 1st valarray " "before swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray " "before swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; // Use of swap() to swap the valarrays varr1.swap(varr2); // Displaying valarrays after swapping cout << "The contents of 1st valarray " "after swapping are : "; for (int &x : varr1) cout << x << " "; cout << endl; cout << "The contents of 2nd valarray " "after swapping are : "; for (int &x : varr2) cout << x << " "; cout << endl; return 0; } 你可能會想繼續閱讀… 容器(Containers) 函式(Functions) 迭代器(Iterators) Utility Library

STL 標準模板庫(Standard Template Library, STL)是提供常用資料結構模板的程式庫，其包含了類別(classes)、演算法(algorithms)與迭代器(iterators)。 STL 是通用的程式庫，所以所有的元素都是泛型的，可以點此瞭解更多模板(template)的內容。 STL 的四大組成 演算法(Algorithms) 容器(Containers) 函式(Functions) 迭代器(Iterators) 補充 Utility Library