C++ STL中一些常用算法總結

更新時間：2024年02月09日 13:00:21 作者：思想覺悟

都說STL是數(shù)據(jù)容器與算法的高度組合,在前面的文章中我們介紹了常見的幾種容器,vector、list、map、deque等,今天我們再來介紹下STL中常用的一些算法,需要的朋友可以參考下

引言

都說STL是數(shù)據(jù)容器與算法的高度組合。在前面的文章中我們介紹了常見的幾種容器，vector、list、map、deque等。今天我們再來介紹下STL中常用的一些算法。

STL算法基本都是通過模板的方式實現(xiàn)的，只是為我們提供一個統(tǒng)一的算法模型，有點像JS中鴨子模型，在這個模型中具體實現(xiàn)什么樣的功能是由我們通過函數(shù)對象或回調(diào)函數(shù)的方式來實現(xiàn)的。

下面我們通過一些常用的例子來學習一下STL中的常用算法...

遍歷

對于STL中的容器遍歷問題，平時我們用得最多的就是auto for循環(huán)遍歷，其實對于容器的遍歷，STL中還給我提供了另外一個函數(shù)std::for_each。這個函數(shù)特別適合哪些需要在遍歷的過程中對每個元素進行復雜操作的場景。

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表達式，也可以使用回調(diào)函數(shù)的寫法:

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，它默認是升序排序，如果需要實現(xiàn)降序排序可以通過修改std::sort的第三個參數(shù)實現(xiàn)：

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中排序還可以使用函數(shù)std::stable_sort實現(xiàn)，那么為什么會有兩個排序函數(shù)呢？std::stable_sort和std::sort的區(qū)別是什么呢？

這里就要提一下std::sort的穩(wěn)定性了，在C++標準中，std::sort并不保證穩(wěn)定性。這意味著當容器中存在有相同鍵值的元素時，經(jīng)過std::sort排序后，相等元素的相對位置可能會改變。換句話說，相同鍵值的元素在排序后可能會改變原來的相對順序。而std::stable_sort則是可以保證排序的穩(wěn)定性的，因此如果有穩(wěn)定性需求的話可以使用std::stable_sort代替std::sort。

查找

在標準庫中我們可以通過函數(shù)std::find實現(xiàn)查找。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;
}

另外我們還可以使用函數(shù)find_if實現(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;
}

假如我們想找出一個容器中的最大值或者最小值，可以嘗試下使用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)計

對于容器中某個元素個數(shù)的統(tǒng)計，我們可以使用count和count_if實現(xiàn)，它們的用法和上面的std::find和find_if用法一個，帶if的是按照條件統(tǒng)計。

int main() {
    std::vector<int> vec{1,3,5,7,9,9,9};
    auto result = std::count(vec.begin(),vec.end(),9);
    std::cout << "個數(shù):" << result << std::endl;
    result = std::count_if(vec.begin(),vec.end(),[](const int &val){
        return val == 2;
    });
    std::cout << "個數(shù):" << result << std::endl;
    return 0;
}

刪除

對于容器元素的刪除，大部分使用容器內(nèi)部的刪除函數(shù)即可，一般是erase，但是針對std::list也可以使用內(nèi)部的remove函數(shù)進行刪除。一般我們遵循以下幾條原則就行：

如果容器是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
如果容器是標準關聯(lián)容器，使用它的erase成員函數(shù)即可。

變換

假如這么一個需求，需要將std::string中的字符全部變?yōu)榇髮懀銜趺磳懩?？此時std::transform就很適合你。

std::transform它用于對一個迭代器內(nèi)的元素進行轉換操作，并將結果存儲在另一個迭代器中。

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，將其字符變?yōu)榇髮懀缓笾匦卤４嬖谧兞縮中。

下面我們再來看看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就是數(shù)相加的模板。最終的輸出結果是:

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是否已經(jīng)有寫好的算法模型，如果有的話我們直接使用STL中的即可，因為STL中的算法基本都是集思廣益，結合了很多精華的結果，我們個人寫的很難在性能上與之媲美。

以上就是C++ STL中常用的算法總結的詳細內(nèi)容，更多關于C++ STL算法的資料請關注腳本之家其它相關文章！

您可能感興趣的文章: