快捷導(dǎo)航

C++ STL中一些常用算法總結(jié)

更新時(shí)間：2024年02月09日 13:00:21 作者：思想覺(jué)悟

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

引言

都說(shuō)STL是數(shù)據(jù)容器與算法的高度組合。在前面的文章中我們介紹了常見(jiàn)的幾種容器，vector、list、map、deque等。今天我們?cè)賮?lái)介紹下STL中常用的一些算法。

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ù)的寫法:

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需要確保容器類型對(duì)待查詢的值類型有合適的比較操作符（通常是operator==），如果是自定義類型，可能需要重載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)榇髮懀銜?huì)怎么寫呢？此時(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)榇髮?，然后重新保存在變量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í)在寫代碼的過(guò)程中，如果我們需要用到一個(gè)算法，盡量不要自己寫，首先要看看STL是否已經(jīng)有寫好的算法模型，如果有的話我們直接使用STL中的即可，因?yàn)镾TL中的算法基本都是集思廣益，結(jié)合了很多精華的結(jié)果，我們個(gè)人寫的很難在性能上與之媲美。

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

您可能感興趣的文章: