Skip to main content

12-3 Iterator 與 STL 演算法

和容器一樣，STL 也提供了很多通用演算法，適用於不同的資料型別和容器。

在使用 STL 的演算法時，除了要記得引入 <algorithm> 檔頭檔外，通常也需要提供一對 iterator，用來表示演算法作用的範圍。

用來表示範圍的 iterator，是左閉右開區間 [first, last)

一、排序 sort

排序所有元素

#include <algorithm>
vector<int> v = {5, 3, 1, 4, 2};

sort(v.begin(), v.end());           // 升冪
// v = {1, 2, 3, 4, 5}

sort(v.begin(), v.end(), greater<int>());  // 降冪
// v = {5, 4, 3, 2, 1}

只排序部分元素

vector<int> v = {5, 3, 1, 4, 2};
sort(v.begin() + 1, v.begin() + 4);  // 只排 index 1~3
// v = {5, 1, 3, 4, 2}

二、線性搜尋 find

對於容器內沒排序的資料，可以使用線性搜尋(就是循序搜尋)，在 [first, last) 中尋找指定的元素值。

若找到了，將回傳指向第一個與目標值相同元素的 iterator；若沒找到會回傳指向 last 的 iterator。

vector<int> v = {10, 20, 30, 40, 50};
auto it = find(v.begin(), v.end(), 30);

if (it != v.end()) {
    cout << "找到！位於 index " << (it - v.begin()) << endl;  // 2
} else {
    cout << "找不到" << endl;
}

三、二分搜尋 lower_bound, upper_bound

若 vector 裡的元素有排序過，可以使用二分搜尋這個高效率的搜尋演算法。

lower_bound(first, last, target) 會回傳第一個>=target元素的位置，若找不到則回傳 last。

upper_bound(first, last, target) 會回傳第一個>target元素的位置，若找不到則回傳 last。

vector<int> v = {1, 3, 3, 5, 7, 9};

// lower_bound：第一個 >= target 的位置
auto lo = lower_bound(v.begin(), v.end(), 3);
// 1, 3, 3, 5, 7, 9
//    ^
//    |
//    lo
cout << (lo - v.begin()) << endl;  // 1（index 1）

// upper_bound：第一個 > target 的位置
auto hi = upper_bound(v.begin(), v.end(), 3);
// 1, 3, 3, 5, 7, 9
//          ^
//          |
//         hi
cout << (hi - v.begin()) << endl;  // 3（index 3）

// 值 3 出現的次數：
cout << hi - lo << endl;  // 2

// 確認是否找到指定值
lo = lower_bound(v.begin(), b.end(), 4);
// lo = lower_bound(v.begin(), b.end(), 5);
if(lo!=v.end() && *lo==4)
{
  cout << "找到！位於 index " << (lo-v.begin()) << endl;
}
else
{
  cout << "找不到" << endl;
}

四、最大/最小值 max_element/min_element

vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};

auto mx = max_element(v.begin(), v.end());
cout << *mx << "\n";                    // 9
cout << (mx - v.begin()) << "\n";      // index 5

auto mn = min_element(v.begin(), v.end());
cout << *mn << "\n";                    // 1

五、反轉 reverse

vector<int> v = {1, 2, 3, 4, 5};
reverse(v.begin(), v.end());
// v = {5, 4, 3, 2, 1}

// 反轉部分：
reverse(v.begin() + 1, v.begin() + 4);
// v = {1, 4, 3, 2, 5}

六、計數 count

vector<int> v = {1, 2, 2, 3, 2, 4};
cout << count(v.begin(), v.end(), 2) << endl;  // 3

七、加總 accumulate

需 include <numeric>。

#include <numeric>
vector<int> v = {1, 2, 3, 4, 5};
int sum = accumulate(v.begin(), v.end(), 0);  // 初始值 0
cout << sum << endl;  // 15

八、去除相鄰重複 unique

特別注意「相鄰」這兩個字，unique 會移除相鄰出現的元素。 它的作法是略過相鄰相同的元素，把後續相異元素往前搬，覆蓋掉相鄰相同的元素，所以最後會回傳你新的結尾 iterator。要記得把「尾巴」刪掉。

vector<int> v = {1, 3, 2, 2, 3, 1};
auto newEnd = unique(v.begin(), v.end());  // 去重，回傳新的 end
// 1, 3, 2, 2, 3, 1
//   uniquer 之後
// 1, 3, 2, 3, 1, 1
//                ^
//                |
//              newEnd
v.erase(newEnd, v.end());       // 刪掉尾巴
// v = {1, 3, 2, 3, 1}

為了移除容器內的相同元素，通常我們會先 sort 再 unique，最後 erase 掉多餘元素。

vector<int> v = {1, 3, 2, 2, 3, 1};
sort(v.begin(), v.end());       // {1, 1, 2, 2, 3, 3}
auto newEnd = unique(v.begin(), v.end());  // 去重，回傳新的 end
v.erase(newEnd, v.end());       // 刪掉尾巴
// v = {1, 2, 3}
Back to top