--- ###### tags: `2020 師大附中校隊培訓` --- # iterator 與 STL 常用函數 ## 2020 師大附中校隊培訓 #### joylintp #### 10.26.2020 --- ## iterator 迭代器 ---- ### pointer & iterator ```cpp= int arr[] = {9, 4, 8, 7}; int *p = arr; cout << *p << ' ' << *(p + 1) << '\n'; // 9 4 vector<int> v = {9, 4, 8, 7}; vector<int>::iterator i = v.begin(); cout << *i << ' ' << *(i + 1) << '\n'; // 9 4 ``` ---- ### 各種 STL 的 iterator `list` / `set` / `multiset` / `map`：只能往前／後一個元素 `deque` / `vector`：可指定元素位置 ---- ### 各種 STL 的 iterator (cont.) ```cpp= set<int> st; st.insert(5), st.insert(9), st.insert(4), st.insert(8), st.insert(7); set<int>::iterator si = st.begin(); cout << *si << '\n'; // 4 si++, cout << *si << '\n'; // 5 si++, cout << *si << '\n'; // 7 si--, cout << *si << '\n'; // 5 ``` ```cpp= vector<int> v = {5, 9, 4, 8, 7}; vector<int>::iterator vi = v.begin(); cout << *vi << '\n'; // 5 vi++, cout << *vi << '\n'; // 9 vi += 2, cout << *vi << '\n'; // 8 vi -= 3, cout << *vi << '\n'; // 5 ``` ---- ### `next` / `prev` 回傳當前迭代器的下一個／前一個位置 ```cpp= set<int> st; st.insert(5), st.insert(9), st.insert(4), st.insert(8), st.insert(7); set<int>::iterator si = st.begin(); auto sj = si; si++, cout << *si << '\n'; // 5 sj = next(sj), cout << *sj << '\n'; // 5 si--, cout << *si << '\n'; // 4 sj = prev(sj), cout << *sj << '\n'; // 4 ``` ```cpp= vector<int> v = {5, 9, 4, 8, 7}; vector<int>::iterator vi = v.begin(); auto vj = vi; vi++, cout << *vi << '\n'; // 9 vj = next(vj), cout << *vj << '\n'; // 9 vi--, cout << *vi << '\n'; // 5 vj = prev(vj), cout << *vj << '\n'; // 5 ``` ---- ### 常用 iterator #### `v.begin()` `v` 中第一個元素的位置 #### `v.end()` `v` 中最後一個元素後面的位置，對此位置取值會是未知值 對於可指定元素的 STL，此位置即為 `v.begin() + v.size()` #### `v.rbegin()` `v` 中最後一個元素的位置，此為 `reverse_iterator`， 此位置的值與 `prev(v.end())` 相同 --- ## 其他常用函式 ---- ### `swap` 交換兩個型態相同的變數的值 ```cpp= int a = 5, b = 4; swap(a, b); vector<int> va = {5, 4}, vb = {8, 7}; swap(va, vb); swap(va[0], vb[0]); ``` ---- ### `sort` 將 STL 中元素排序，預設為遞減排序，亦可自行設定比較函式 若多元素權重相同則順序可能改變 時間複雜度 $O(n\ log(n))$ ```cpp= bool cmp(int a, int b) { return a % 2 < b % 2; } // ... vector<int> v = {5, 9, 4, 8, 7}; sort(v.begin() + 1, v.begin() + 4); // 5 4 8 9 7 sort(v.begin(), v.end()); // 4 5 7 8 9 sort(v.begin(), v.end(), greater<int>()); // 9 8 7 5 4 sort(v.begin(), v.end(), cmp); // 4 8 7 9 5 ``` ---- ### `stable_sort` 將 STL 中元素排序，預設為遞減排序，亦可自行設定比較函式 若多元素權重相同則在原始順序較前面者仍會在前面 若有額外空間則時間複雜度為 $O(n\ log(n))$；否則為 $O(n\ log^2(n))$ ```cpp= bool cmp(int a, int b) { return a % 2 < b % 2; } // ... vector<int> v = {5, 9, 4, 8, 7}; stable_sort(v.begin(), v.end(), cmp); // 4 8 5 9 7 ``` ---- ### `reverse` 將 STL 中元素前後反轉 時間複雜度 $O(n)$ ```cpp= vector<int> v = {5, 9, 4, 8, 7}; reverse(v.begin() + 1, v.begin() + 4); // 5 8 4 9 7 reverse(v.begin(), v.end()); // 7 9 4 8 5 ``` ---- ### `rotate` `rotate(a, a + i, b)` 向左旋轉 `[a, b)` 之間的元素， 使得原本的第 `a + i` 個元素變為原本第 `a` 個元素的位置 時間複雜度 $O(n)$ ```cpp= vector<int> v = {5, 9, 4, 8, 7}; rotate(v.begin() + 1, v.begin() + 2, v.begin() + 4); // 5 4 8 9 7 rotate(v.begin(), v.begin() + 2, v.end()); // 8 9 7 5 4 ``` ---- ### `prev_permutation` / `next_permutation` 將 STL 中的元素重新排成前一個／後一個字典序 若已是第一個／最後一個字典序會回傳 `false`；否則回傳 `true` 時間複雜度 $O(n)$ ```cpp= vector<int> v = {1, 2, 3}; do { for (int i : v) cout << i << ' '; cout << '\n'; } while (next_permutation(v.begin(), v.end())); // 1 2 3 // 1 3 2 // 2 1 3 // 2 3 1 // 3 1 2 // 3 2 1 ``` ---- ### `random_shuffle` 打亂 STL 中的元素 時間複雜度 $O(n)$ ```cpp= vector<int> v = {5, 9, 4, 8, 7}; random_shuffle(v.begin(), v.begin() + 3); // 4 9 5 8 7 random_shuffle(v.begin(), v.end()); // 8 4 7 5 9 ``` ---- ## `upper_bound` / `loewr_bound` 對於已排序的 STL 容器， `upper_bound` 回傳第一個嚴格大於指定值的元素迭代器 `lower_bound` 回傳第一個大於或等於指定值的元素迭代器 ---- `deque` / `vector` 等 STL 應使用 `lower_bound(v.begin(), v.end(), x)` `set` / `multiset` / `map` 等 STL 應使用 `st.lower_bound(x)` 時間複雜度 $log(n)$ 若 `set` 等 STL 使用了第一種方式， 時間複雜度可能退化成 $O(n)$ ---- ```cpp= vector<int> v = {5, 7}; for (int i = 4; i <= 8; i++) { auto p1 = lower_bound(v.begin(), v.end(), i); auto p2 = upper_bound(v.begin(), v.end(), i); cout << *p1 << ' ' << *p2 << '\n'; } // i == 4: 5 5 // i == 5: 5 7 // i == 6: 7 7 // i == 7: 7 ? // i == 8: ? ? ``` ---- ```cpp= set<int> st; st.insert(5), st.insert(7); for (int i = 4; i <= 8; i++) { auto p1 = st.lower_bound(i); auto p2 = st.upper_bound(i); cout << *p1 << ' ' << *p2 << '\n'; } // i == 4: 5 5 // i == 5: 5 7 // i == 6: 7 7 // i == 7: 7 ? // i == 8: ? ? ```