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