C++s

線段樹 Segment Tree 簡介 線段樹是演算法中常用來維護區間訊息的資料結構。 空間複雜度為 \(O(n)\)，\(n\) 代表區間數。 查詢的時間複雜度為 \(O(\log n+k)\)，\(k\) 代表符合條件的區間數量。 線段樹將每個長度為為 1 的區間劃分為左右兩個區間遞迴求解，把整個線段劃分為一個樹型結構，通過合併左右兩個區間訊息來求得該區間的訊息。 在實現時，我們考慮遞迴建樹，設當前的根節點為 root，如果根節點管轄的區間長度已經是 1，則可以直接根據數組上相應位置的值初始化該節點。否則需將該區間從中點處分割為兩個子區間，分別進入左右子節點遞迴建樹，最後合併兩個子節點的訊息， 建樹 build void build(int s, int t, int p, const vector<int>& arr){ if (s == t){ tree[p] = SegmentItem(arr[s], 1); return; } int m = s + ((t - s) >> 1); build(s, m, p*2, arr); build(m+1, t, p*2+1, arr); // push_up tree[p] = tree[p*2] + tree[(p*2)+1]; } 查詢 query SegmentItem find(int l, int r, int s, int t, int p){ if (l <= s && t <= r){ return tree[p]; } int m = s + ((t - s) >> 1); SegmentItem sum; if (r <= m) return find(l, r, s, m, p*2); if (l > m) return find(l, r, m+1, t, p*2+1); return find(l, r, s, m, p*2) + find(l, r, m+1, t, p*2+1); } zkw 線段樹 來自清華大學張昆瑋(zkw)-《統計的力量》 以非遞迴的方式構建，效率更高，程式更短。 普通的線段樹是從上到下做處理，容易定位根節點，卻不容易定位子節點。 zkw 線段樹是當二叉樹是滿二叉樹時，因為子節點的編號具有以下規律： 葉子節點(left) 全部退化為線段 \([x,x]\) 。 \(n\) 個數據點則取大於等 \(n\)且為 \(2\) 的冪次的兩倍作為數組大小。 \((m=2^a\ge n)\) for (int m = 1; m <= n; m >>= 1) 維護點為 \(n\) 個。索引為\([m,m+n)\)。 子葉數目為 \(m\) 個。索引為\([m,2m)\) 節點數為 \(2m-1\) 個。(數組大小需設 \(2m\) 因為 zkw tree是 1-index的) 樹高 \(H=\log_2(m)+1\) 層。 第 \(h\) 層有 \(2^{h-1}\) 個節點， 該層線段長度為 \(2^{H-h}\)。 若某節點為 \(p\)，父節點為 \(p/2\)，子節點為 \(2p\) 和 \(2p+1\) int parent = p >> 1; int left = p << 1; int right = p << 1 | 1; 若兩節點為 \(p\) 與 \(q\)，且兩節點互為兄弟節點，則 \(p\oplus q=1\) if (left ^ right) // left 與 right 為兄弟節點 else // left 與 right 不為兄弟節點 除根節點外，左節點皆為偶數，右節點皆為奇數 if (i == 1) // i 為根節點 else if (i & 1) // i 為奇數，為右節點 else if (!(i & 1)) // i 為偶數，為左節點 結構 線段樹索引堆疊： 轉成二進制： 規律： 一個節點的父節點是該數右移 1，低位捨棄。 一個節點的左子節點是該數左移 1，右子節點是該數左移 1 再加 1。 同一層的節點是依次遞增的，第 \(n\) 層有 \(2^{n-1}\)個節點 最後一層有多少個節點，值域就是多少。 建樹 build 取 m 值有許多版本，有些版本會直接取 \(m=2^{log_2(n+5)+1}\)以節省迭代計算 寫成 int n = 1 << __lg(n+5)+1; 可以有開區間與閉區間兩種做法，差別在於從子葉節點的最左邊 \(m+i\) 開始，或是第二個子葉節點 \(m+1+i\) 開始。 由下而上更新時，開區間與閉區間的終止條件不同： 開區間的終止條件為兩子節點互為兄弟節點 while (i^j^1) // operation 閉區間的終止條件為右節點小於左節點 while (i <= j) // operation class Tree { private: vector<int> arr; int n, m; // n 為維護點數, m 為 zkw-tree 子葉節點數 public: Tree (vector<int>& nums){ n = nums.size(); for (m = 1; m <= n; m <<= 1); // 取大於等於 n 且為 2 的冪次的最小整數 arr.assign(2*m, 0); // 節點數設為 2m 個，其中 0 為空節點 } void build(vector<int> nums){ for (int i = 0; i < n; i++) { arr[i+m] = nums[i]; // 從子葉節點最左邊往右更新節點。 mx[i+m] = nums[i]; mn[i+m] = nums[i]; } for (int i = m-1; i; i--){ // 向上更新父節點。 arr[i] = in(x); } } }; 根據不同需求代換 \(\text{in(x)}\)：取和、最大值、最小平 // 取和 arr[i] = arr[i<<1] + arr[i<<1|1]; // 取最大值 arr[i] = max(arr[i<<1], arr[i<<1|1]); // 取最小值 arr[i] = min(arr[i<<1], arr[i<<1|1]); 更新 update 單點修改(以和為例) 更新時，以差分方式，將所有父節點加上更新點的差值。 void update(int i, int val){ int diff = val - arr[m+i] // 原值 arr[m+i] 與新值 val 的差 for (i += m; i; i >>= 1){ arr[i] += diff; } } 查詢 query 單點查詢(以和為例)：閉區間做法 判斷左邊界是否為右節點，若為右節點則加上後往右邊的父節點移動。 判斷右邊界是否為左節點，若為左節點則加上後往左邊的父節點移動。 int query(int left, int right){ int sum = 0; int i = left+m; // 左閉區間 int j = right+m; // 右閉區間 for (; i <= j; i >>= 1, j >>= 1){ if (i & 1) sum += arr[i++]; if (!(j & 1)) sum += arr[j--]; } return sum; } 備註：開區間作法 (0-index 時會出現 -1 的情形，建議使用閉區間) int query(int left, int right){ int sum = 0; int i = left+m-1; int j = right+m+1; for(; i^j^1; i >>= 1, j >>= 1){ if (~i & 1) sum += arr[i^1]; if (j & 1) sum += arr[j^1]; } return sum; } 區間修改 在非遞迴的情況下，標記下傳是比較困難的，所以作法上改成將標記永久化。 具體而言，與查詢類似，當左端點是左子節點且右端點是右子節點時，我們對它的兄弟節點進行修改並標記，表示這顆子樹中的每個節點都要被修改。但單純這樣還不夠，因上述修改還會波及到這些節點的各級祖先，所以我們需要在途中根據實際修改的區間長度來更新各級祖先的值，這種操作需要一路上推到根節點。 (開區間作法) void update(int left, int right, int diff){ int len = 1, cntl = 0, cntr = 0; // cntl, cntr 是左右邊分別實際修改的區間長度 left += m-1; right += m+1; for (; left^right^1; left >> 1, right >> 1, len << 1){ arr[left] += cntl * diff; arr[right] += cntr * diff; if (~left & 1) { arr[left^1] += diff * len; mark[left^1] += diff; cntl += len; } if (right & 1) { arr[right^1] += diff * len; mark[right^1] += diff; cntr += len; } } for (; left; left >>= 1, right >>= 1){ arr[left] += cntl * diff; arr[right] += cntr * diff; } } 在有區間修改存在時，區間查詢也需要考慮標記的影響。 所以除了加上端點的兄弟節點訊息，沿途中遇到的標記也對答案有貢獻，同樣需要上推到根節點。 int query(int left, int right){ int sum = 0, len = 1, cntl = 0, cntr = 0; left += m - 1; right += m + 1; for (; left^right^1; left >>= 1, right >>= 1, len << 1){ sum += cntl * mark[left] + cntr * mark[right]; if (~left & 1) sum += arr[left^1], cntl += len; if (right & 1) sum += arr[right^1], cntr += len; } for (; left; left >> 1, right >> 1){ sum += cntl * mark[left] + cntr * mark[right]; } return sum; } 區間查詢最大值： void update(int l, int r, int d) { for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) { if (l < N) tree[l] = max(tree[l << 1], tree[l << 1 | 1]) + mark[l], tree[r] = max(tree[r << 1], tree[r << 1 | 1]) + mark[r]; if (~l & 1) tree[l ^ 1] += d, mark[l ^ 1] += d; if (r & 1) tree[r ^ 1] += d, mark[r ^ 1] += d; } for (; l; l >>= 1, r >>= 1) if (l < N) tree[l] = max(tree[l << 1], tree[l << 1 | 1]) + mark[l], tree[r] = max(tree[r << 1], tree[r << 1 | 1]) + mark[r]; }; int query(int l, int r) { int maxl = -INF, maxr = -INF; for (l += N - 1, r += N + 1; l ^ r ^ 1; l >>= 1, r >>= 1) { maxl += mark[l], maxr += mark[r]; if (~l & 1) cmax(maxl, tree[l ^ 1]); if (r & 1) cmax(maxr, tree[r ^ 1]); } for (; l; l >>= 1, r >>= 1) maxl += mark[l], maxr += mark[r]; return max(maxl, maxr); }; Leetcode. 307 範例 https://leetcode.com/problems/range-sum-query-mutable/ TreeNode 變形 class NumArray { class SegTree { public: int val; int begin, end; SegTree* left, *right; SegTree(int v):val(v) {} SegTree(int v, int b, int e):val(v), begin(b), end(e) {} SegTree(int v, int b, int e, SegTree* l, SegTree* r) :val(v), begin(b), end(e), left(l), right(r) {} }; SegTree* root; SegTree* build(vector<int>& nums, int b, int e){ if (e < b) return NULL; if (b == e) return new SegTree(nums[b], b, b); int mid = b + (e-b)/2; SegTree* left = build(nums, b, mid); SegTree* right = build(nums, mid+1, e); return new SegTree(left->val + right->val, b, e, left, right); } void update(SegTree* node, int index, int val){ if (node->begin == index && node->end == index){ node->val = val; } else { int mid = node->begin + (node->end - node->begin)/2; if (index <= mid){ update(node->left, index, val); } else { update(node->right, index, val); } node->val = node->left->val + node->right->val; } } int query(SegTree* node, int left, int right){ if (node->begin == left && node->end == right){ return node->val; } int mid = node->begin + (node->end - node->begin)/2; if (right <= mid){ return query(node->left, left, right); } else if (left > mid){ return query(node->right, left, right); } return query(node->left, left, mid) + query(node->right, mid+1, right); } public: NumArray(vector<int>& nums) { root = build(nums, 0, nums.size()-1); } void update(int index, int val) { update(root, index, val); } int sumRange(int left, int right) { return query(root, left, right); } }; zkw 線段樹 class NumArray { class SegTree { vector<int> arr; int m, n; public: SegTree(vector<int>& nums) { n = nums.size(); for (m = 1; m < n; m <<= 1); build(nums); } void build(vector<int>& nums) { arr.assign(2*m, 0); for (int i = 0; i < n; ++i) arr[m+i] = nums[i]; for (int i = m-1; i; --i) arr[i] = arr[i<<1] + arr[i<<1|1]; } void update(int index, int val) { int diff = val - arr[m+index]; for (index += m; index; index >>= 1) arr[index] += diff; } int query(int left, int right) { int sum = 0; for (int i = left+m, j = right+m; i <= j; i >>= 1, j >>= 1){ if (i & 1) sum += arr[i++]; if (!(j & 1)) sum += arr[j--]; } return sum; } }; public: SegTree* root; NumArray(vector<int>& nums) { root = new SegTree(nums); } void update(int index, int val) { root->update(index, val); } int sumRange(int left, int right) { return root->query(left, right); } }; BIT(binary indexed tree) class NumArray { public: class Bit { public: vector<int> bit; int n; Bit(vector<int>& nums) { n = nums.size(); bit.assign(n+1, 0); for (int i = 0; i < n; i++){ build(i+1, nums[i]); } } void build(int index, int val) { while (index <= n){ bit[index] += val; index = next(index); } } int next(int index) { return index + (index & -index); } int parent(int index) { return index - (index & -index); } int getSum(int index) { int sum = 0; while (index){ sum += bit[index]; index = parent(index); } return sum; } }; Bit* bit; NumArray(vector<int>& nums) { bit = new Bit(nums); } void update(int index, int val) { int diff = val - sumRange(index, index); bit->build(index+1, diff); } int sumRange(int left, int right) { return bit->getSum(right+1) - bit->getSum(left); } };

stringstream 需引用 <sstream> , <iostream>, <string>函式庫 配合 str() 將 stringstream 類轉換成 string 類別。 split() vector<string> split(string& str, char del){ stringstream ss(str); string item; vector<string> res; while (getline(ss, item, del)){ if (!item.empty()){ res.push_back(item); } } return res; } concat() string concat(vector<string>& svec, char del){ stringstream ss; for (const auto& s : svec){ ss << s << del; } return ss.str(); } [leetcode 1859. Sorting the Sentence] class Solution { public: string sortSentence(string s) { vector<string> tmp = split(s, ' '); int n = tmp.size(); vector<string> svec(n); for (const string& s : tmp){ int pos = s.back() - '1'; svec[pos] = s.substr(0, s.length()-1); } return concat(svec, ' '); } string concat(vector<string>& svec, char del){ string res; stringstream ss; for (const string& s : svec) ss << del << s; res = ss.str(); return res.substr(1); } vector<string> split(string& str, char del){ vector<string> res; stringstream ss(str); string item; while (getline(ss, item, del)){ if (!item.empty()){ res.push_back(item); } } return res; } };

Deque 不同於 stack 與 queues， deques 兩個端點都支援擴展。 基於 doubly linked list，deques 有幾項額外的特徵： 支援隨機存取 插入元素時間 \(O(1)\) 函式 1. push_front() 2. push_back() 3. front() 4. back() 5. begin() 6. end() 7. insert() 8. erase() 9. pop_front() 10. pop_back() 11. empty() 12. clear() 13. random_access() 內部運作原理 上述所有函數和操作都在雙鏈表中以O（1）時間執行，但這些清單不能隨機訪問任何元素。C++中的deque也是如此。這個 O（1） 在 deque 中可以使用圓形陣列來實現。使用循環陣列，可以在O（1）時間內實現從陣列的正面和背面插入和刪除等操作以及元素的隨機訪問。但這帶來了一個問題。當 deque 增長到超出容量時，使用者將需要將數位大小加倍，並將所有數據複製到陣列中。此外，如果數據是某個使用者定義的對象，那麼加倍和複製數據的成本就會變得非常昂貴。 這是一個基本的解決方案。Deque使用一些棘手的實現，當它說O（1）來push_back（）和push_front（）時，它實際上是調用的複製構造函數數量的常數時間。因此，如果數據物件是具有多個成員的某個類物件，則最小化複製構造函數調用的數量將節省時間。此外，複製構造函數調用的次數是恆定的。現在讓我們看看如何實現這一點。 這可以通過使用指向一些固定大小的塊的指標數位來實現，這些塊包含deque數據。下面是一個說明性示例。 這些 Deque 數據被劃分為固定大小的塊。在這裡，我們考慮了將數據劃分為大小為5的固定塊。 塊的填充從指標的兩個 deque 陣列的中間開始，並使用push_front和push_back操作向前和向後擴展。中間塊通常是滿的，當它被填滿時，數據被移動到上部或下部塊。 在上部塊中，元素以相反的順序推送，因為在這種情況下，填充數據的第一個位置將是4，然後是3，2，1，0。但是在中間和下部塊中，數據按正向順序填充，如0，1，2，3，4等。 當上面的塊被填滿時，指標將創建一個新塊並開始指向一個新的數位塊。這為更多數據創造了空間。在這種情況下，也可以填充指標塊。這會導致一個問題。 這是加倍來救援的時候。在加倍時，指標陣列的大小加倍。這不會複製整個數據，而只會複製指標。這是許多人在討論恆定時間時提出的一般論點。時間在調用的複製構造函數數方面保持不變。 如果數據集非常大，則指標塊幾乎不會執行加倍，因為單個指標可以指向大量數據塊。因此，指標陣列被填充並加倍的可能性非常小。

C++ Custom Comparator sort(iter, iter, comp) Lambda function int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Usual boolean function bool comp(const int& a, const int& b){ return a < b; } int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp); // 1,2,3,4,5,6,7,8,9 } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; sort(vec.begin(), vec.end(), comp()); // 1,2,3,4,5,6,7,8,9 } priority_queue(element, container, comp) Modern C++20 Solution(lambda) We can use lambda function as comparator. As usual, comparator should return boolean value, indicating whether the element passed as first argument is considered to go before the second in the specific strict weak ordering it defines. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq; for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Modern C++11 Solution(lambda) Before C++20 we need to pass lambda function as argument to set constructor. int main(){ auto comp = [](int a, int b){ return a < b; } vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Usual function Make comparator as usual boolean function bool comp(int a, int b){ return a < b; } int main(){ vector<int> vec = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); // priority_queue<int, vector<int, decltype(comp)*> pq(comp); // in C++20, constructor can be ignored the same as lambda function. for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Old solution using struct/class with () operator struct cmp { bool operator() (int a, int b) const { return a < b; } }; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int>, comp> pq(vec.begin(), vec.end()); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; } Alternative solution: create struct/class from boolean function bool comp(int a, int b){ return a < b; } #include <type_traits> using Cmp = integral_constant<decltype(&comp), &comp>; int main(){ vector<int> = {3,6,7,2,1,9,5,4,8}; priority_queue<int, vector<int, decltype(&comp)> pq(comp); for (int num : vec) pq.push(num); while (!pq.empty()) { cout << pq.top() << " "; // 9,8,7,6,5,4,3,2,1 pq.pop(); } cout << endl; }

pair 函式庫 #include <utility> 宣告 pair<data_type1, data_type2> Pair_name; 初始化 pair<int, int> p1; // 宣告但不初始化 pair<int, char> p2(1, 'a'); // 不同資料型態的初始化 pair<int, int> p3(1, 10); // 同資料型態的初始化 pair<int, int> p4(p3); // 利用其它 pair 來初始化 pair<int, int> p5 = {1, 2} // 用 assign 的方式初始化 p2 = make_pair(1, 'a'); // 利用 make_pair 函式 成員 .first .second 函式 1. make_pair(v1, v2); 2. pair1.swap(pair2); 3. tie(a,b) 示例 #include <iostream> #include <utility> using namespace std; int main(){ // initialize pair<int,int> p1; pair<int,int> p2(2,4); pair<int,char> p3(3,'c'); pair<int,int> p4(p2); pair<int,int> p5 = {5,10}; // member cout << p2.first << " " << p2.second << endl; // 2 4 cout << p3.first << " " << p3.second << endl; // 3 c cout << p4.first << " " << p4.second << endl; // 2 4 cout << p5.first << " " << p5.second << endl; // 5 10 // function p1 = make_pair(1,2); cout << p1.first << " " << p1.second << endl; // 1 2 // a.swap(b) p1.swap(p2); cout << p1.first << " " << p1.second << endl; // 2 4 cout << p2.first << " " << p2.second << endl; // 1 2 // tie(a,b) = pair int a, b; tie(a, b) = p1; cout << a << " " << b << endl; // 2 4 return 0; }

map 宣告 map <int, int> mp; // key和value都是整數 方法 mp[key] = value; 加入新的key-value pair mp.count(key); 檢查 key 是否存在 map 中 mp.erase(key); 刪除 key mp.clear(); 清空 map 中的所有元素： value = mp[key] 利用 key 取值 mp.empty() 判斷是否為空的map map 的遍歷 遍歷整個map時，利用iterator操作： 取key：it->first 或 *(it).first 取value：it->second 或 *(it).second for (auto it = mp.begin(); it != mp.end(); ++it){ cout << it->first << " => " << it->second << '\n'; } for (auto it = mp.begin(); it != mp.end(); ++it){ cout << (*it).first << " => " << (*it).second << '\n'; }

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