C++STL之常見算法
STL算法基本都是通過模板的方式實現的，只是為我們提供一個統一的算法模型，有點像JS中鴨子模型，在這個模型中具體實現什么樣的功能是由我們通過函數對象或回調函數的方式來實現的。
下面我們通過一些常用的例子來學習一下STL中的常用算法...
遍歷
對于STL中的容器遍歷問題，平時我們用得最多的就是auto for循環遍歷，其實對于容器的遍歷，STL中還給我提供了另外一個函數std::for_each。 這個函數特別適合哪些需要在遍歷的過程中對每個元素進行復雜操作的場景。
int main() {
std::vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.emplace_back(i);
}
std::for_each(vec.begin(), vec.end(), [](const int &value){
std::cout << "value:" << value << std::endl;
});
return 0;
}當然，如果你不喜歡使用lambda表達式，也可以使用回調函數的寫法:
void myFun(const int &val){
std::cout << "value:" << val << std::endl;
}
int main() {
std::vector<int> vec;
for (int i = 0; i < 10; ++i) {
vec.emplace_back(i);
}
std::for_each(vec.begin(), vec.end(), myFun);
return 0;
}排序
在STL中最常用的排序應該就是std::sort，它默認是升序排序，如果需要實現降序排序可以通過修改std::sort的第三個參數實現：
int main() {
std::vector<int> vec{2, 1, 5, 9, 4,0};
// 默認升序排序
// std::sort(vec.begin(),vec.end());
// 改成降序排序
std::sort(vec.begin(),vec.end(),std::greater<int>());
std::for_each(vec.begin(),vec.end(),[](const int &va){
std::cout << "va:" << va << std::endl;
});
return 0;
}在STL中排序還可以使用函數std::stable_sort實現，那么為什么會有兩個排序函數呢？std::stable_sort和std::sort的區別是什么呢？
這里就要提一下std::sort的穩定性了，在C++標準中，std::sort并不保證穩定性。這意味著當容器中存在有相同鍵值的元素時，經過std::sort排序后，相等元素的相對位置可能會改變。換句話說，相同鍵值的元素在排序后可能會改變原來的相對順序。 而std::stable_sort則是可以保證排序的穩定性的，因此如果有穩定性需求的話可以使用std::stable_sort代替std::sort。
查找
在標準庫中我們可以通過函數std::find實現查找。std::find需要確保容器類型對待查詢的值類型有合適的比較操作符（通常是operator==），如果是自定義類型，可能需要重載operator==來定義相等性比較。
int main() {
std::vector<int> vec{1,3,5,7,9};
auto pos = std::find(vec.begin(),vec.end(),1);
if(pos != vec.end()){
std::cout << "找到匹配的" << std::endl;
} else{
std::cout << "沒有找到匹配的" << std::endl;
}
return 0;
}另外我們還可以使用函數find_if實現條件查找：
int main() {
std::vector<int> vec{1,3,5,7,9,9,9};
// 查找是否有9的元素
auto result = std::find_if(vec.begin(),vec.end(),[](const int val){
return val == 9;
});
return 0;
}假如我們想找出一個容器中的最大值或者最小值，可以嘗試下使用max_element和min_element
int main() {
std::vector<int> vec{1,3,5,7,9,9,9};
auto max = std::max_element(vec.begin(),vec.end());
auto min = std::min_element(vec.begin(),vec.end());
std::cout << "max:" << *max << std::endl;
std::cout << "min:" << *min << std::endl;
return 0;
}統計
對于容器中某個元素個數的統計，我們可以使用count和count_if實現，它們的用法和上面的std::find和find_if用法一個，帶if的是按照條件統計。
int main() {
std::vector<int> vec{1,3,5,7,9,9,9};
auto result = std::count(vec.begin(),vec.end(),9);
std::cout << "個數:" << result << std::endl;
result = std::count_if(vec.begin(),vec.end(),[](const int &val){
return val == 2;
});
std::cout << "個數:" << result << std::endl;
return 0;
}刪除
對于容器元素的刪除，大部分使用容器內部的刪除函數即可，一般是erase，但是針對std::list也可以使用內部的remove函數進行刪除。 一般我們遵循以下幾條原則就行：
- 如果容器是vector、string或deque，使用erase-remove慣用法。
// 所有為9的元素都會被刪除
int main() {
std::vector<int> vec{9,3,5,7,9,2,9};
vec.erase(std::remove(vec.begin(),vec.end(),9),vec.end());
for (const auto val:vec) {
std::cout << "val:" << val << std::endl;
}
return 0;
}- 如果容器是list，使用list.remove
- 如果容器是標準關聯容器，使用它的erase成員函數即可。
變換
假如這么一個需求，需要將std::string中的字符全部變為大寫，你會怎么寫呢？此時std::transform就很適合你。
std::transform它用于對一個迭代器內的元素進行轉換操作，并將結果存儲在另一個迭代器中。
std::transform有兩個重載方法，一個是對應于一元操作，一個是對應于二元操作。
我們先來看看一元操作：
int main() {
std::string s("Hello");
std::transform(s.begin(),s.end(),s.begin(),[](unsigned char c) { return std::toupper(c); });
std::cout << s << std::endl;
return 0;
}上述代碼的意思就是遍歷字符串變量s，將其字符變為大寫，然后重新保存在變量s中。
下面我們再來看看std::transform的二元操作：
int main() {
// 注意兩個容器的size并不一定相等
std::vector<int> input1 = {1, 2, 3, 4, 5,10};
std::vector<int> input2 = {5, 4, 3, 2, 1};
std::vector<int> output;
// resize 開辟足夠的空間
output.resize(input1.size());
// 對input1和input2中對應位置的元素進行相加操作，并將結果存儲到output
std::transform(input1.begin(), input1.end(), input2.begin(), output.begin(), std::plus<int>());
// 輸出結果
for (const auto& value : output) {
std::cout << value << " ";
}
return 0;
}上面代碼的意思是將容器input1的變量和容器input2的變量逐個相加，然后輸出到目標容器output中。其中std::plus就是數相加的模板。最終的輸出結果是:
6 6 6 6 6 10需要注意的一點是輸出目標容器必須提前開辟足夠的空間，否則可能會無法正常完成轉換。因此上面實例代碼中的output.resize(input1.size());是很有必要的。
集合計算
所謂集合計算，一般是針對多個容器而言的。
例如我們要求兩個容器之間的交集，則可以使用set_intersection，求并集則使用set_union，求差集則使用set_difference。
int main() {
std::vector<int> vec1{1,3,5,7,9};
std::vector<int> vec2{1,2,3,6,8};
std::vector<int> out;
// 分配足夠的空間
out.resize(vec1.size() + vec2.size());
// vec1中有的，vec2也有的
// auto end = std::set_intersection(vec1.begin(),vec1.end(),vec2.begin(),vec2.end(),out.begin());
// std::for_each(out.begin(),end,[](const int &val){
// std::cout << "交集：" << val << std::endl;
// });
// vec1中有的，而vec2沒有的
// auto end = std::set_difference(vec1.begin(),vec1.end(),vec2.begin(),vec2.end(),out.begin());
// std::for_each(out.begin(),end,[](const int &val){
// std::cout << "差集：" << val << std::endl;
// });
// vec1和vec2去重后的合并結合
auto end = std::set_union(vec1.begin(),vec1.end(),vec2.begin(),vec2.end(),out.begin());
std::for_each(out.begin(),end,[](const int &val){
std::cout << "并集：" << val << std::endl;
});
return 0;
}平時在寫代碼的過程中，如果我們需要用到一個算法，盡量不要自己寫，首先要看看STL是否已經有寫好的算法模型，如果有的話我們直接使用STL中的即可，因為STL中的算法基本都是 集思廣益，結合了很多精華的結果，我們個人寫的很難在性能上與之媲美。
