C++ STL中一些常用算法总结

目录

• 引言
• 遍历
• 排序
• 查找
• 统计
• 删除
• 变换
• 集合计算

引言

都说STL是数据容器与算法的高度组合。在前面的文章中我们介绍了常见的几种容器，vector、list、map、deque等。今天我们再来介绍下STL中常用的一些算法。

STL算法基本都是android通过模板的方式实现的，只是为我们提供一个统一的算法模型，有点像js中鸭子模型，在这个模型中具体实现什么样的功能是由我们通过函数对象或回调函数的方式来实现的。

下面我们通过一些常用的例子来学习一下STL中的常用算法...

遍历

对于STL中的容器遍历问题，平时我们用得最多的就是auto for循环遍历，其实对于容器的遍历，STL中还给我提供了另外一个函数std::for_each。 这个函数特别适合哪些需要在遍历的过程中对每个元素进行复杂操作的场景。

intpython main() {
    std::vector<int> vec;
    for (int i = 0; i < 10; ++i) {
        vec.emplace_bazaGyCEck(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)android;
    }
    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());是很有必要的。

集合计算

所谓集合计算，一般www.devze.com是针对多个容器而言的。

例如我们要求两个容器之间的交集，则可以使用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中的算法基本都是 集思广益，结合了很多精华的结果，我们个人写的很难在性能上与之媲美。

以上就是C++ STL中常用的算法总结的详细内容，更多关于C++ STL算法的资料请关注编程客栈(www.devze.com)其它相关文章！