STL算法库总结

小灰灰 2022-06-02 10:57 200阅读 0赞

## 写在前面： ##

STL算法库是经常需要用到的，对于一些给定的算法使用起来比自己写要方便，当然对于每一种算法的原理是要清楚的，当然更要熟练使用了。  
下面就对STL算法库中的算法做一个总结。

**算法库提供大量用途的函数（例如查找、排序、计数、操作），它们在元素范围上操作。注意范围定义为 \[first, last) ，其中 last 指代要查询或修改的最后元素的后一个元素。**  
定义于头文件 < algorithm >

## 第一大类：不修改序列的操作 ##

这些算法不会改变容器内元素的顺序和元素的值

all_of  检查一元谓词 p 是否对范围 [first, last) 中所有元素返回 true 。
    any_of  检查一元谓词 p 是否对范围 [first, last) 中至少一个元素返回 true 。
    none_of 检查一元谓词 p 是否不对范围 [first, last) 中任何元素返回 true 。
    bool isone(const int& x) {
        return x==1;
    }
    int main() {
        vector<int> v{
       1,1,1,1};
        cout<< all_of(v.begin(),v.end(),isone) <<endl;
        return 0;
    }

这个对应的第三个参数为自己定义的谓动词 用于检测是不是 有没有某种属性  
这个函数一般都是is开头的去描述 参数是对应操作的迭代器中的元素类型的引用  
bool pred(const Type &a); 不改变元素的值所以是常引用

for_each 按顺序应用给定的函数对象 f 到解引用范围 [first, last) 中每个迭代器的结果
    template< class InputIt, class UnaryFunction >
    UnaryFunction for_each( InputIt first, InputIt last, UnaryFunction f );

这个函数对于给定范围的迭代器指向的元素做同样的函数操作  
所有容器适用  
for\_each(b,e,p)  
1、使用for\_each()算法遍历数据  
2、使用for\_each()和函数对象修改数据  
3、使用for\_each()的返回值

返回值为函数对象 Function Object  
一个函数对象，即一个**重载了括号操作符“（）”的对象**。当用该对象调用此操作符时，其表现形式**如同普通函数**调用一般，因此取名叫**函数对象**。

既然用函数对象与调用普通函数有相同的效果，为什么还有搞这么麻烦定义一个类来使用函数对象？主要在于函数对象有以下的优势：
     1. 函数对象可以有自己的状态。我们可以在类中定义 状态变量，这样一个函数对象在多次的调用中可以共享这个状态。但是函数调用没这种优势，除非它使用全局变量来保存状态。
    面向对象的编程就应该避免全局变量的使用。
    
     2. 函数对象有自己特有的类型，而普通函数无类型可言。这种特性对于使用C++标准库来说是至关重要的。这样我们在使用STL中的函数时，可以传递相应的类型作为参数来实例化相应的模板，从而实现我们自己定义的规则。比如自定义容器的排序规则。

#include <vector>
    #include <algorithm>
    #include <iostream>
    
    struct Sum
    {
        Sum(): sum{
       0} { }
        void operator()(int n) { sum += n; }//重载了圆括号操作符 
        int sum;
    };
    
    int main()
    {
        std::vector<int> nums{
       3, 4, 2, 8, 15, 267};
    
        auto print = [](const int& n) { std::cout << " " << n; };//没有捕获参数的lambda表达式 也就是匿名函数 输出n
    
        std::cout << "before:";
        std::for_each(nums.begin(), nums.end(), print);//对于区间内的每一个元素作用print函数
        std::cout << '\n';
    
        std::for_each(nums.begin(), nums.end(), [](int &n){ n++; });//注意这个lambda表达式的参数不是常引用 是会改变容器内的元素内容
    
        // 对每个数调用 Sum::operator()
        Sum s = std::for_each(nums.begin(), nums.end(), Sum());
        //这里Sum()构造了一个临时的无名对象
        //返回值也是一个函数对象 使用拷贝构造的形式 赋值给s
        std::cout << "after: ";
        std::for_each(nums.begin(), nums.end(), print);
        std::cout << '\n';
        std::cout << "sum: " << s.sum << '\n';
    }

产生一个临时对象一个临时变量的做法其实很常用，都是临时的所以可以无名。

template<class InputIt, class UnaryFunction>
    UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
    {
        for (; first != last; ++first) {
            f(*first);
        }
        return f;
    }

这里传入临时对象 传值的方式 形参会  
真的看编译器，编译器没优化的话，会调用拷贝构造函数构造一个临时量；没优化的话，调用赋值构造函数。  
这里gcc编译器作了优化 [http://blog.csdn.net/sxhelijian/article/details/50977946][http_blog.csdn.net_sxhelijian_article_details_50977946]

lambda 表达式 构造的是匿名函数对象 目的是简化编程  
[https://www.cnblogs.com/coderland/p/5902903.html][https_www.cnblogs.com_coderland_p_5902903.html]

nth\_element（）

[http_blog.csdn.net_sxhelijian_article_details_50977946]: http://blog.csdn.net/sxhelijian/article/details/50977946
[https_www.cnblogs.com_coderland_p_5902903.html]: https://www.cnblogs.com/coderland/p/5902903.html