STL算法库总结

写在前面：

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;
}
1
2
3
4
5
6
7
8
9
10
11

这个对应的第三个参数为自己定义的谓动词 用于检测是不是 有没有某种属性
这个函数一般都是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 );
1
2
3

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

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

既然用函数对象与调用普通函数有相同的效果，为什么还有搞这么麻烦定义一个类来使用函数对象？主要在于函数对象有以下的优势：
 1. 函数对象可以有自己的状态。我们可以在类中定义 状态变量，这样一个函数对象在多次的调用中可以共享这个状态。但是函数调用没这种优势，除非它使用全局变量来保存状态。
面向对象的编程就应该避免全局变量的使用。

 2. 函数对象有自己特有的类型，而普通函数无类型可言。这种特性对于使用C++标准库来说是至关重要的。这样我们在使用STL中的函数时，可以传递相应的类型作为参数来实例化相应的模板，从而实现我们自己定义的规则。比如自定义容器的排序规则。
1
2
3
4
5

#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';
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

template<class InputIt, class UnaryFunction>
UnaryFunction for_each(InputIt first, InputIt last, UnaryFunction f)
{
    for (; first != last; ++first) {
        f(*first);
    }
    return f;
}
1
2
3
4
5
6
7
8
9

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

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

nth_element（）