12-3 Iterator 與 STL 演算法
和容器一樣，STL 也提供了很多通用演算法，適用於不同的資料型別和容器。
在使用 STL 的演算法時，除了要記得引入 <algorithm> 檔頭檔外，通常也需要提供一對 iterator，用來表示演算法作用的範圍。
用來表示範圍的 iterator，是左閉右開區間 [first, last)
一、常用的演算法
1. 排序 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}
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;
}
3. 二分搜尋 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;
}
4. 最大/最小值 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
5. 反轉 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}
6. 計數 count
vector<int> v = {1, 2, 2, 3, 2, 4};
cout << count(v.begin(), v.end(), 2) << endl; // 3
7. 加總 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
8. 去除相鄰重複 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}
二、Compare
在使用 sort 排序時，你可能注意到了，除了用 [first, end) 標定排序範圍外，在尾巴我們還有提供一個 greater<int>() 或 less<int>() 來決定是由大到小亦或由小到大排序。
由於 STL 的 sort 是藉由比較兩個元素的大小來決定誰要排在前面，所以需要我們告訴它要怎麼決定誰排在前面。
1. Compare function
最簡單的方式，就是提供一個函數讓 sort 叫用，它會呼叫這個函數並傳入兩個值 a, b，如果 a 應該排在 b 前面，我們就回傳 true，否則回傳 false。
以下是個實例
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 小的排前面
bool comp1(const int &a, const int &b)
{
return a<b;
}
// 大的排前面
bool comp2(const int &a, const int &b)
{
return a>b;
}
int main()
{
vector<int> v = {1, 3, 5, 6, 4, 2};
sort(v.begin(), v.end(), comp1);
for(int i: v) {
cout << i << " ";
}
cout << endl;
// 1 2 3 4 5 6
sort(v.begin(), v.end(), comp2);
for(int i: v) {
cout << i << " ";
}
cout << endl;
// 6 5 4 3 2 1
return 0;
}
2. lambda 函數
在 C++11 之後，在這種場合我們可以直接在 sort 的參數列裡建立一個 lambda funtion 讓 sort 叫用如下。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {1, 3, 5, 6, 4, 2};
// 小的排前面
sort(v.begin(), v.end(), [] (const int &a, const int &b)->bool {
return a<b;
}
);
for(int i: v) {
cout << i << " ";
}
cout << endl;
// 大的排前面
sort(v.begin(), v.end(), [] (const int &a, const int &b)->bool {
return a>b;
}
);
for(int i: v) {
cout << i << " ";
}
cout << endl;
return 0;
}
lambda 函數是一個匿名的函數，可以直接寫在程式碼裡。
我們來拆解檢視一下這個 lambda 函數。
[] (const int &a, const int &b)->bool {
return a<b;
}
[] 這個我們先不看，當 lambda 函數裡需要存取外面的變數時才需要它。
(const int &a, const int &b)->bool 這表示該 lambda 函數有兩個參數，回傳值是 bool 型別。
{ ... } 大括號裡是函數的實作部分。
3. functor
前面提到的 greater<int>() 和 less<int>() 是所謂的函式物件 function object，也叫 functor。
本質上它是一個「行為表現得像一般函式的物件（Object）」，只要一個類別（class）或結構（struct）重載了「函式呼叫運算子」 operator()，由它所建立出來的物件就是一個 Functor。
例如：以下是一個用來計算兩整數相加的 functor。
#include <iostream>
using namespace std;
class AplusB {
public:
int operator()(int a, int b)
{
return a+b;
}
};
int main()
{
AplusB sum;
cout << sum(2, 3) << endl; // 5
return 0;
}
用 functor 來做排序。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class smallFirst {
public:
bool operator()(const int &a, const int &b)
{
return a<b;
}
};
class bigFirst {
public:
bool operator()(const int &a, const int &b)
{
return a>b;
}
};
int main()
{
vector<int> v = {1, 3, 5, 6, 4, 2};
// 小的排前面
sort(v.begin(), v.end(), smallFirst());
for(int i: v) {
cout << i << " ";
}
cout << endl;
// 大的排前面
sort(v.begin(), v.end(), bigFirst());
for(int i: v) {
cout << i << " ";
}
cout << endl;
return 0;
}
如果希望它可以用在多種型別的排序，可以結合 template 來使用。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
template<typename T>
class smallFirst {
public:
bool operator()(const T &a, const T &b)
{
return a<b;
}
};
template<typename T>
class bigFirst {
public:
bool operator()(const T &a, const T &b)
{
return a>b;
}
};
int main()
{
vector<int> v = {1, 3, 5, 6, 4, 2};
// 小的排前面
sort(v.begin(), v.end(), smallFirst<int>());
for(int i: v) {
cout << i << " ";
}
cout << endl;
vector<double> u = {1.4, 3.5, 1.5, 6.5, 4.5, 2.5};
// 大的排前面
sort(u.begin(), u.end(), bigFirst<double>());
for(double i: u) {
cout << i << " ";
}
cout << endl;
return 0;
}
三、 Predicate
Predicate 和 Compare 一樣是一個用來被別人呼叫並回傳 bool 值的函數(或 functor)。只是語意上有差異而已。
例如:我們要刪除 vector 裡所有的奇數，我們可以這樣做。
1. 使用 function
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool odd(const int &a)
{
return (a%2==1);
}
int main()
{
vector<int> v = {2, 3, 5, 6, 4, 1};
auto new_end = remove_if(v.begin(), v.end(), odd);
v.erase(new_end, v.end()); // 記得把尾巴刪掉
for(int i: v) {
cout << i << " ";
}
cout << endl;
return 0;
}
2. 使用 lambda function
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
vector<int> v = {2, 3, 5, 6, 4, 1};
auto new_end = remove_if(v.begin(), v.end(),
[] (const int &a)->bool
{
return (a%2==1);
}
);
v.erase(new_end, v.end()); // 記得把尾巴刪掉
for(int i: v) {
cout << i << " ";
}
cout << endl;
return 0;
}
3. 使用 functor
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class odd {
public:
bool operator()(const int &a) {
return (a%2==1);
}
};
int main()
{
vector<int> v = {2, 3, 5, 6, 4, 1};
auto new_end = remove_if(v.begin(), v.end(), odd());
v.erase(new_end, v.end()); // 記得把尾巴刪掉
for(int i: v) {
cout << i << " ";
}
cout << endl;
return 0;
}
四、練習題
使用自訂排序規則來解以下幾題有關排序的問題