C++

容器(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

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

vector 的介紹 vector 是可變大小陣列的序列容器，採用連續的儲存空間來儲存元素，意味著可以採用下標來對 vector 的元素進行存取，和陣列 array 一樣高效，但是又不像陣列的大小是固定的，vector 的大小可以被動態處理，隨著元素量而增加。 #include <vector> vector 的使用 建構式 constructor vector<int> v1; // 不進行初始化 vector<int> v2 = {1,2,3}; // 像陣列一樣初始化 vector<int> v3(v2); // 利用vector初始化 vector<int> v4(v2.begin(), v2.end()-1); // 利用iterator初始化 vector<int> v5(3, 0); // 含有3個0的vector 談一下特殊的二維vector，其實就是二維矩陣，寫法為 vector<vector<int>> vv(3, vector<int>(5, 0)); // vv[0] = [0, 0, 0, 0, 0] // vv[1] = [0, 0, 0, 0, 0] // vv[2] = [0, 0, 0, 0, 0] 遍歷 traverse 遍歷的方法有三種，分別是iterator，for loop，[]，其中**[]下標運算子只有string和vector**可以使用，因為他們的地址是連續的。 三種方法均是可讀、可寫。 vector<int> v = {0, 9, 3, 1, 6, 3, 9, 4, 3, 3}; // 1. iterator vector<int>::iterator it = v.begin(); while (it != v.end()){ cout << *it << " "; it++; } cout << endl; // 2. for loop for (int e : v){ cout << e << " "; cout << endl; } // 3. [] for (size_t i = 0; i < v.size(); ++i){ cout << v[i] << " "; cout << endl; } 資料的資刪查改 \( \def\arraystrecth{1.4}\begin{array}{|l|l|}\hline \text{methods}&\text{description}\\\hline\hline \text{push\_back}&\text{Add element at the end}\\\hline \text{pop\_back}&\text{Delete last element}\\\hline \text{insert}&\text{Insert elements}\\\hline \text{erase}&\text{Erase elements}\\\hline \end{array} \) ...

如何初始化 vector 事先準備 #include <iostream> #include <vector> using namespace std; 1. 利用 push_back() 函式 vector<int> A; A.push_back(1); A.push_back(2); A.push_back(3); // A = [1,2,3] 2. 利用重載建構子(overloaded constructor) int size = 5; int fill = 2; vector<int> B(size, fill); // B = [2,2,2,2,2] 3. 將 array 傳給 vector 的建構子(-std=c++11) vector<int> C{1, 2, 3, 4, 5}; // C = [1,2,3,4,5] 4. 利用既有的 array int array[] = {1,2,3,4,5}; vector<int> D(array, array+4); // D = [1,2,3,4] 5. 利用既有的 vector vector<int> E(C.begin()+1, C.end()-3); // E = [2] 6. 利用 fill 函式 vector<int> F(6); fill(F.begin(), F.end(), 3); // F = [3,3,3,3,3,3] Reference ...